-: 0:Source:red_black_tree.c -: 0:Programs:4 -: 1:#include "red_black_tree.h" -: 2: -: 3:/***********************************************************************/ -: 4:/* FUNCTION: RBTreeCreate */ -: 5:/**/ -: 6:/* INPUTS: All the inputs are names of functions. CompFunc takes to */ -: 7:/* void pointers to keys and returns 1 if the first arguement is */ -: 8:/* "greater than" the second. DestFunc takes a pointer to a key and */ -: 9:/* destroys it in the appropriate manner when the node containing that */ -: 10:/* key is deleted. InfoDestFunc is similiar to DestFunc except it */ -: 11:/* recieves a pointer to the info of a node and destroys it. */ -: 12:/* PrintFunc recieves a pointer to the key of a node and prints it. */ -: 13:/* PrintInfo recieves a pointer to the info of a node and prints it. */ -: 14:/* If RBTreePrint is never called the print functions don't have to be */ -: 15:/* defined and NullFunction can be used. */ -: 16:/**/ -: 17:/* OUTPUT: This function returns a pointer to the newly created */ -: 18:/* red-black tree. */ -: 19:/**/ -: 20:/* Modifies Input: none */ -: 21:/***********************************************************************/ -: 22: 1: 23:rb_red_blk_tree* RBTreeCreate( int (*CompFunc) (const void*,const void*), -: 24: void (*DestFunc) (void*), -: 25: void (*InfoDestFunc) (void*), -: 26: void (*PrintFunc) (const void*), -: 27: void (*PrintInfo)(void*)) { -: 28: rb_red_blk_tree* newTree; -: 29: rb_red_blk_node* temp; -: 30: 1: 31: newTree=(rb_red_blk_tree*) SafeMalloc(sizeof(rb_red_blk_tree)); 1: 32: newTree->Compare= CompFunc; 1: 33: newTree->DestroyKey= DestFunc; 1: 34: newTree->PrintKey= PrintFunc; 1: 35: newTree->PrintInfo= PrintInfo; 1: 36: newTree->DestroyInfo= InfoDestFunc; -: 37: -: 38: /* see the comment in the rb_red_blk_tree structure in red_black_tree.h */ -: 39: /* for information on nil and root */ 1: 40: temp=newTree->nil= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node)); 1: 41: temp->parent=temp->left=temp->right=temp; 1: 42: temp->red=0; 1: 43: temp->key=0; 1: 44: temp=newTree->root= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node)); 1: 45: temp->parent=temp->left=temp->right=newTree->nil; 1: 46: temp->key=0; 1: 47: temp->red=0; 1: 48: return(newTree); -: 49:} -: 50: -: 51:/***********************************************************************/ -: 52:/* FUNCTION: LeftRotate */ -: 53:/**/ -: 54:/* INPUTS: This takes a tree so that it can access the appropriate */ -: 55:/* root and nil pointers, and the node to rotate on. */ -: 56:/**/ -: 57:/* OUTPUT: None */ -: 58:/**/ -: 59:/* Modifies Input: tree, x */ -: 60:/**/ -: 61:/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ -: 62:/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ -: 63:/* makes the parent of x be to the left of x, x the parent of */ -: 64:/* its parent before the rotation and fixes other pointers */ -: 65:/* accordingly. */ -: 66:/***********************************************************************/ -: 67: 4: 68:void LeftRotate(rb_red_blk_tree* tree, rb_red_blk_node* x) { -: 69: rb_red_blk_node* y; 4: 70: rb_red_blk_node* nil=tree->nil; -: 71: -: 72: /* I originally wrote this function to use the sentinel for */ -: 73: /* nil to avoid checking for nil. However this introduces a */ -: 74: /* very subtle bug because sometimes this function modifies */ -: 75: /* the parent pointer of nil. This can be a problem if a */ -: 76: /* function which calls LeftRotate also uses the nil sentinel */ -: 77: /* and expects the nil sentinel's parent pointer to be unchanged */ -: 78: /* after calling this function. For example, when RBDeleteFixUP */ -: 79: /* calls LeftRotate it expects the parent pointer of nil to be */ -: 80: /* unchanged. */ -: 81: 4: 82: y=x->right; 4: 83: x->right=y->left; -: 84: 4: 85: if (y->left != nil) y->left->parent=x; /* used to use sentinel here */ -: 86: /* and do an unconditional assignment instead of testing for nil */ -: 87: 4: 88: y->parent=x->parent; -: 89: -: 90: /* instead of checking if x->parent is the root as in the book, we */ -: 91: /* count on the root sentinel to implicitly take care of this case */ 4: 92: if( x == x->parent->left) { 1: 93: x->parent->left=y; -: 94: } else { 3: 95: x->parent->right=y; -: 96: } 4: 97: y->left=x; 4: 98: x->parent=y; -: 99: -: 100:#ifdef DEBUG_ASSERT 4: 101: Assert(!tree->nil->red,"nil not red in LeftRotate"); -: 102:#endif 4: 103:} -: 104: -: 105: -: 106:/***********************************************************************/ -: 107:/* FUNCTION: RighttRotate */ -: 108:/**/ -: 109:/* INPUTS: This takes a tree so that it can access the appropriate */ -: 110:/* root and nil pointers, and the node to rotate on. */ -: 111:/**/ -: 112:/* OUTPUT: None */ -: 113:/**/ -: 114:/* Modifies Input?: tree, y */ -: 115:/**/ -: 116:/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ -: 117:/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ -: 118:/* makes the parent of x be to the left of x, x the parent of */ -: 119:/* its parent before the rotation and fixes other pointers */ -: 120:/* accordingly. */ -: 121:/***********************************************************************/ -: 122: #####: 123:void RightRotate(rb_red_blk_tree* tree, rb_red_blk_node* y) { -: 124: rb_red_blk_node* x; #####: 125: rb_red_blk_node* nil=tree->nil; -: 126: -: 127: /* I originally wrote this function to use the sentinel for */ -: 128: /* nil to avoid checking for nil. However this introduces a */ -: 129: /* very subtle bug because sometimes this function modifies */ -: 130: /* the parent pointer of nil. This can be a problem if a */ -: 131: /* function which calls LeftRotate also uses the nil sentinel */ -: 132: /* and expects the nil sentinel's parent pointer to be unchanged */ -: 133: /* after calling this function. For example, when RBDeleteFixUP */ -: 134: /* calls LeftRotate it expects the parent pointer of nil to be */ -: 135: /* unchanged. */ -: 136: #####: 137: x=y->left; #####: 138: y->left=x->right; -: 139: #####: 140: if (nil != x->right) x->right->parent=y; /*used to use sentinel here */ -: 141: /* and do an unconditional assignment instead of testing for nil */ -: 142: -: 143: /* instead of checking if x->parent is the root as in the book, we */ -: 144: /* count on the root sentinel to implicitly take care of this case */ #####: 145: x->parent=y->parent; #####: 146: if( y == y->parent->left) { #####: 147: y->parent->left=x; -: 148: } else { #####: 149: y->parent->right=x; -: 150: } #####: 151: x->right=y; #####: 152: y->parent=x; -: 153: -: 154:#ifdef DEBUG_ASSERT #####: 155: Assert(!tree->nil->red,"nil not red in RightRotate"); -: 156:#endif #####: 157:} -: 158: -: 159:/***********************************************************************/ -: 160:/* FUNCTION: TreeInsertHelp */ -: 161:/**/ -: 162:/* INPUTS: tree is the tree to insert into and z is the node to insert */ -: 163:/**/ -: 164:/* OUTPUT: none */ -: 165:/**/ -: 166:/* Modifies Input: tree, z */ -: 167:/**/ -: 168:/* EFFECTS: Inserts z into the tree as if it were a regular binary tree */ -: 169:/* using the algorithm described in _Introduction_To_Algorithms_ */ -: 170:/* by Cormen et al. This funciton is only intended to be called */ -: 171:/* by the RBTreeInsert function and not by the user */ -: 172:/***********************************************************************/ -: 173: 8: 174:void TreeInsertHelp(rb_red_blk_tree* tree, rb_red_blk_node* z) { -: 175: /* This function should only be called by InsertRBTree (see above) */ -: 176: rb_red_blk_node* x; -: 177: rb_red_blk_node* y; 8: 178: rb_red_blk_node* nil=tree->nil; -: 179: 8: 180: z->left=z->right=nil; 8: 181: y=tree->root; 8: 182: x=tree->root->left; 33: 183: while( x != nil) { 17: 184: y=x; 17: 185: if (1 == tree->Compare(x->key,z->key)) { /* x.key > z.key */ 2: 186: x=x->left; -: 187: } else { /* x,key <= z.key */ 15: 188: x=x->right; -: 189: } -: 190: } 8: 191: z->parent=y; 15: 192: if ( (y == tree->root) || 7: 193: (1 == tree->Compare(y->key,z->key))) { /* y.key > z.key */ 2: 194: y->left=z; -: 195: } else { 6: 196: y->right=z; -: 197: } -: 198: -: 199:#ifdef DEBUG_ASSERT 8: 200: Assert(!tree->nil->red,"nil not red in TreeInsertHelp"); -: 201:#endif 8: 202:} -: 203: -: 204:/* Before calling Insert RBTree the node x should have its key set */ -: 205: -: 206:/***********************************************************************/ -: 207:/* FUNCTION: RBTreeInsert */ -: 208:/**/ -: 209:/* INPUTS: tree is the red-black tree to insert a node which has a key */ -: 210:/* pointed to by key and info pointed to by info. */ -: 211:/**/ -: 212:/* OUTPUT: This function returns a pointer to the newly inserted node */ -: 213:/* which is guarunteed to be valid until this node is deleted. */ -: 214:/* What this means is if another data structure stores this */ -: 215:/* pointer then the tree does not need to be searched when this */ -: 216:/* is to be deleted. */ -: 217:/**/ -: 218:/* Modifies Input: tree */ -: 219:/**/ -: 220:/* EFFECTS: Creates a node node which contains the appropriate key and */ -: 221:/* info pointers and inserts it into the tree. */ -: 222:/***********************************************************************/ -: 223: 8: 224:rb_red_blk_node * RBTreeInsert(rb_red_blk_tree* tree, void* key, void* info) { -: 225: rb_red_blk_node * y; -: 226: rb_red_blk_node * x; -: 227: rb_red_blk_node * newNode; -: 228: 8: 229: x=(rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node)); 8: 230: x->key=key; 8: 231: x->info=info; -: 232: 8: 233: TreeInsertHelp(tree,x); 8: 234: newNode=x; 8: 235: x->red=1; 21: 236: while(x->parent->red) { /* use sentinel instead of checking for root */ 5: 237: if (x->parent == x->parent->parent->left) { #####: 238: y=x->parent->parent->right; #####: 239: if (y->red) { #####: 240: x->parent->red=0; #####: 241: y->red=0; #####: 242: x->parent->parent->red=1; #####: 243: x=x->parent->parent; -: 244: } else { #####: 245: if (x == x->parent->right) { #####: 246: x=x->parent; #####: 247: LeftRotate(tree,x); -: 248: } #####: 249: x->parent->red=0; #####: 250: x->parent->parent->red=1; #####: 251: RightRotate(tree,x->parent->parent); -: 252: } -: 253: } else { /* case for x->parent == x->parent->parent->right */ 5: 254: y=x->parent->parent->left; 5: 255: if (y->red) { 2: 256: x->parent->red=0; 2: 257: y->red=0; 2: 258: x->parent->parent->red=1; 2: 259: x=x->parent->parent; -: 260: } else { 3: 261: if (x == x->parent->left) { #####: 262: x=x->parent; #####: 263: RightRotate(tree,x); -: 264: } 3: 265: x->parent->red=0; 3: 266: x->parent->parent->red=1; 3: 267: LeftRotate(tree,x->parent->parent); -: 268: } -: 269: } -: 270: } 8: 271: tree->root->left->red=0; 8: 272: return(newNode); -: 273: -: 274:#ifdef DEBUG_ASSERT -: 275: Assert(!tree->nil->red,"nil not red in RBTreeInsert"); -: 276: Assert(!tree->root->red,"root not red in RBTreeInsert"); -: 277:#endif -: 278:} -: 279: -: 280:/***********************************************************************/ -: 281:/* FUNCTION: TreeSuccessor */ -: 282:/**/ -: 283:/* INPUTS: tree is the tree in question, and x is the node we want the */ -: 284:/* the successor of. */ -: 285:/**/ -: 286:/* OUTPUT: This function returns the successor of x or NULL if no */ -: 287:/* successor exists. */ -: 288:/**/ -: 289:/* Modifies Input: none */ -: 290:/**/ -: 291:/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ -: 292:/***********************************************************************/ -: 293: 3: 294:rb_red_blk_node* TreeSuccessor(rb_red_blk_tree* tree,rb_red_blk_node* x) { -: 295: rb_red_blk_node* y; 3: 296: rb_red_blk_node* nil=tree->nil; 3: 297: rb_red_blk_node* root=tree->root; -: 298: 3: 299: if (nil != (y = x->right)) { /* assignment to y is intentional */ 6: 300: while(y->left != nil) { /* returns the minium of the right subtree of x */ 2: 301: y=y->left; -: 302: } 2: 303: return(y); -: 304: } else { 1: 305: y=x->parent; 2: 306: while(x == y->right) { /* sentinel used instead of checking for nil */ #####: 307: x=y; #####: 308: y=y->parent; -: 309: } 1: 310: if (y == root) return(nil); 1: 311: return(y); -: 312: } -: 313:} -: 314: -: 315:/***********************************************************************/ -: 316:/* FUNCTION: Treepredecessor */ -: 317:/**/ -: 318:/* INPUTS: tree is the tree in question, and x is the node we want the */ -: 319:/* the predecessor of. */ -: 320:/**/ -: 321:/* OUTPUT: This function returns the predecessor of x or NULL if no */ -: 322:/* predecessor exists. */ -: 323:/**/ -: 324:/* Modifies Input: none */ -: 325:/**/ -: 326:/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ -: 327:/***********************************************************************/ -: 328: 7: 329:rb_red_blk_node* TreePredecessor(rb_red_blk_tree* tree, rb_red_blk_node* x) { -: 330: rb_red_blk_node* y; 7: 331: rb_red_blk_node* nil=tree->nil; 7: 332: rb_red_blk_node* root=tree->root; -: 333: 7: 334: if (nil != (y = x->left)) { /* assignment to y is intentional */ 8: 335: while(y->right != nil) { /* returns the maximum of the left subtree of x */ #####: 336: y=y->right; -: 337: } 4: 338: return(y); -: 339: } else { 3: 340: y=x->parent; 9: 341: while(x == y->left) { 3: 342: if (y == root) return(nil); 3: 343: x=y; 3: 344: y=y->parent; -: 345: } 3: 346: return(y); -: 347: } -: 348:} -: 349: -: 350:/***********************************************************************/ -: 351:/* FUNCTION: InorderTreePrint */ -: 352:/**/ -: 353:/* INPUTS: tree is the tree to print and x is the current inorder node */ -: 354:/**/ -: 355:/* OUTPUT: none */ -: 356:/**/ -: 357:/* EFFECTS: This function recursively prints the nodes of the tree */ -: 358:/* inorder using the PrintKey and PrintInfo functions. */ -: 359:/**/ -: 360:/* Modifies Input: none */ -: 361:/**/ -: 362:/* Note: This function should only be called from RBTreePrint */ -: 363:/***********************************************************************/ -: 364: 24: 365:void InorderTreePrint(rb_red_blk_tree* tree, rb_red_blk_node* x) { 24: 366: rb_red_blk_node* nil=tree->nil; 24: 367: rb_red_blk_node* root=tree->root; 24: 368: if (x != tree->nil) { 11: 369: InorderTreePrint(tree,x->left); 11: 370: printf("info="); 11: 371: tree->PrintInfo(x->info); 11: 372: printf(" key="); 11: 373: tree->PrintKey(x->key); 11: 374: printf(" l->key="); 11: 375: if( x->left == nil) printf("NULL"); else tree->PrintKey(x->left->key); 11: 376: printf(" r->key="); 11: 377: if( x->right == nil) printf("NULL"); else tree->PrintKey(x->right->key); 11: 378: printf(" p->key="); 11: 379: if( x->parent == root) printf("NULL"); else tree->PrintKey(x->parent->key); 11: 380: printf(" red=%i\n",x->red); 11: 381: InorderTreePrint(tree,x->right); -: 382: } 24: 383:} -: 384: -: 385: -: 386:/***********************************************************************/ -: 387:/* FUNCTION: TreeDestHelper */ -: 388:/**/ -: 389:/* INPUTS: tree is the tree to destroy and x is the current node */ -: 390:/**/ -: 391:/* OUTPUT: none */ -: 392:/**/ -: 393:/* EFFECTS: This function recursively destroys the nodes of the tree */ -: 394:/* postorder using the DestroyKey and DestroyInfo functions. */ -: 395:/**/ -: 396:/* Modifies Input: tree, x */ -: 397:/**/ -: 398:/* Note: This function should only be called by RBTreeDestroy */ -: 399:/***********************************************************************/ -: 400: 13: 401:void TreeDestHelper(rb_red_blk_tree* tree, rb_red_blk_node* x) { 13: 402: rb_red_blk_node* nil=tree->nil; 13: 403: if (x != nil) { 6: 404: TreeDestHelper(tree,x->left); 6: 405: TreeDestHelper(tree,x->right); 6: 406: tree->DestroyKey(x->key); 6: 407: tree->DestroyInfo(x->info); 6: 408: free(x); -: 409: } 13: 410:} -: 411: -: 412: -: 413:/***********************************************************************/ -: 414:/* FUNCTION: RBTreeDestroy */ -: 415:/**/ -: 416:/* INPUTS: tree is the tree to destroy */ -: 417:/**/ -: 418:/* OUTPUT: none */ -: 419:/**/ -: 420:/* EFFECT: Destroys the key and frees memory */ -: 421:/**/ -: 422:/* Modifies Input: tree */ -: 423:/**/ -: 424:/***********************************************************************/ -: 425: 1: 426:void RBTreeDestroy(rb_red_blk_tree* tree) { 1: 427: TreeDestHelper(tree,tree->root->left); 1: 428: free(tree->root); 1: 429: free(tree->nil); 1: 430: free(tree); 1: 431:} -: 432: -: 433: -: 434:/***********************************************************************/ -: 435:/* FUNCTION: RBTreePrint */ -: 436:/**/ -: 437:/* INPUTS: tree is the tree to print */ -: 438:/**/ -: 439:/* OUTPUT: none */ -: 440:/**/ -: 441:/* EFFECT: This function recursively prints the nodes of the tree */ -: 442:/* inorder using the PrintKey and PrintInfo functions. */ -: 443:/**/ -: 444:/* Modifies Input: none */ -: 445:/**/ -: 446:/***********************************************************************/ -: 447: 2: 448:void RBTreePrint(rb_red_blk_tree* tree) { 2: 449: InorderTreePrint(tree,tree->root->left); 2: 450:} -: 451: -: 452: -: 453:/***********************************************************************/ -: 454:/* FUNCTION: RBExactQuery */ -: 455:/**/ -: 456:/* INPUTS: tree is the tree to print and q is a pointer to the key */ -: 457:/* we are searching for */ -: 458:/**/ -: 459:/* OUTPUT: returns the a node with key equal to q. If there are */ -: 460:/* multiple nodes with key equal to q this function returns */ -: 461:/* the one highest in the tree */ -: 462:/**/ -: 463:/* Modifies Input: none */ -: 464:/**/ -: 465:/***********************************************************************/ -: 466: 10: 467:rb_red_blk_node* RBExactQuery(rb_red_blk_tree* tree, void* q) { 10: 468: rb_red_blk_node* x=tree->root->left; 10: 469: rb_red_blk_node* nil=tree->nil; -: 470: int compVal; 10: 471: if (x == nil) return(0); 10: 472: compVal=tree->Compare(x->key,(int*) q); 39: 473: while(0 != compVal) {/*assignemnt*/ 23: 474: if (1 == compVal) { /* x->key > q */ 7: 475: x=x->left; -: 476: } else { 16: 477: x=x->right; -: 478: } 23: 479: if ( x == nil) return(0); 19: 480: compVal=tree->Compare(x->key,(int*) q); -: 481: } 6: 482: return(x); -: 483:} -: 484: -: 485: -: 486:/***********************************************************************/ -: 487:/* FUNCTION: RBDeleteFixUp */ -: 488:/**/ -: 489:/* INPUTS: tree is the tree to fix and x is the child of the spliced */ -: 490:/* out node in RBTreeDelete. */ -: 491:/**/ -: 492:/* OUTPUT: none */ -: 493:/**/ -: 494:/* EFFECT: Performs rotations and changes colors to restore red-black */ -: 495:/* properties after a node is deleted */ -: 496:/**/ -: 497:/* Modifies Input: tree, x */ -: 498:/**/ -: 499:/* The algorithm from this function is from _Introduction_To_Algorithms_ */ -: 500:/***********************************************************************/ -: 501: 2: 502:void RBDeleteFixUp(rb_red_blk_tree* tree, rb_red_blk_node* x) { 2: 503: rb_red_blk_node* root=tree->root->left; -: 504: rb_red_blk_node* w; -: 505: 5: 506: while( (!x->red) && (root != x)) { 1: 507: if (x == x->parent->left) { 1: 508: w=x->parent->right; 1: 509: if (w->red) { #####: 510: w->red=0; #####: 511: x->parent->red=1; #####: 512: LeftRotate(tree,x->parent); #####: 513: w=x->parent->right; -: 514: } 1: 515: if ( (!w->right->red) && (!w->left->red) ) { #####: 516: w->red=1; #####: 517: x=x->parent; -: 518: } else { 1: 519: if (!w->right->red) { #####: 520: w->left->red=0; #####: 521: w->red=1; #####: 522: RightRotate(tree,w); #####: 523: w=x->parent->right; -: 524: } 1: 525: w->red=x->parent->red; 1: 526: x->parent->red=0; 1: 527: w->right->red=0; 1: 528: LeftRotate(tree,x->parent); 1: 529: x=root; /* this is to exit while loop */ -: 530: } -: 531: } else { /* the code below is has left and right switched from above */ #####: 532: w=x->parent->left; #####: 533: if (w->red) { #####: 534: w->red=0; #####: 535: x->parent->red=1; #####: 536: RightRotate(tree,x->parent); #####: 537: w=x->parent->left; -: 538: } #####: 539: if ( (!w->right->red) && (!w->left->red) ) { #####: 540: w->red=1; #####: 541: x=x->parent; -: 542: } else { #####: 543: if (!w->left->red) { #####: 544: w->right->red=0; #####: 545: w->red=1; #####: 546: LeftRotate(tree,w); #####: 547: w=x->parent->left; -: 548: } #####: 549: w->red=x->parent->red; #####: 550: x->parent->red=0; #####: 551: w->left->red=0; #####: 552: RightRotate(tree,x->parent); #####: 553: x=root; /* this is to exit while loop */ -: 554: } -: 555: } -: 556: } 2: 557: x->red=0; -: 558: -: 559:#ifdef DEBUG_ASSERT 2: 560: Assert(!tree->nil->red,"nil not black in RBDeleteFixUp"); -: 561:#endif 2: 562:} -: 563: -: 564: -: 565:/***********************************************************************/ -: 566:/* FUNCTION: RBDelete */ -: 567:/**/ -: 568:/* INPUTS: tree is the tree to delete node z from */ -: 569:/**/ -: 570:/* OUTPUT: none */ -: 571:/**/ -: 572:/* EFFECT: Deletes z from tree and frees the key and info of z */ -: 573:/* using DestoryKey and DestoryInfo. Then calls */ -: 574:/* RBDeleteFixUp to restore red-black properties */ -: 575:/**/ -: 576:/* Modifies Input: tree, z */ -: 577:/**/ -: 578:/* The algorithm from this function is from _Introduction_To_Algorithms_ */ -: 579:/***********************************************************************/ -: 580: 2: 581:void RBDelete(rb_red_blk_tree* tree, rb_red_blk_node* z){ -: 582: rb_red_blk_node* y; -: 583: rb_red_blk_node* x; 2: 584: rb_red_blk_node* nil=tree->nil; 2: 585: rb_red_blk_node* root=tree->root; -: 586: 2: 587: y= ((z->left == nil) || (z->right == nil)) ? z : TreeSuccessor(tree,z); 2: 588: x= (y->left == nil) ? y->right : y->left; 2: 589: if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */ #####: 590: root->left=x; -: 591: } else { 2: 592: if (y == y->parent->left) { 2: 593: y->parent->left=x; -: 594: } else { #####: 595: y->parent->right=x; -: 596: } -: 597: } 2: 598: if (y != z) { /* y should not be nil in this case */ -: 599: -: 600:#ifdef DEBUG_ASSERT 1: 601: Assert( (y!=tree->nil),"y is nil in RBDelete\n"); -: 602:#endif -: 603: /* y is the node to splice out and x is its child */ -: 604: 1: 605: if (!(y->red)) RBDeleteFixUp(tree,x); -: 606: 1: 607: tree->DestroyKey(z->key); 1: 608: tree->DestroyInfo(z->info); 1: 609: y->left=z->left; 1: 610: y->right=z->right; 1: 611: y->parent=z->parent; 1: 612: y->red=z->red; 1: 613: z->left->parent=z->right->parent=y; 1: 614: if (z == z->parent->left) { 1: 615: z->parent->left=y; -: 616: } else { #####: 617: z->parent->right=y; -: 618: } 1: 619: free(z); -: 620: } else { 1: 621: tree->DestroyKey(y->key); 1: 622: tree->DestroyInfo(y->info); 1: 623: if (!(y->red)) RBDeleteFixUp(tree,x); 1: 624: free(y); -: 625: } -: 626: -: 627:#ifdef DEBUG_ASSERT 2: 628: Assert(!tree->nil->red,"nil not black in RBDelete"); -: 629:#endif 2: 630:} -: 631: -: 632: -: 633:/***********************************************************************/ -: 634:/* FUNCTION: RBDEnumerate */ -: 635:/**/ -: 636:/* INPUTS: tree is the tree to look for keys >= low */ -: 637:/* and <= high with respect to the Compare function */ -: 638:/**/ -: 639:/* OUTPUT: stack containing pointers to the nodes between [low,high] */ -: 640:/**/ -: 641:/* Modifies Input: none */ -: 642:/***********************************************************************/ -: 643: 1: 644:stk_stack* RBEnumerate(rb_red_blk_tree* tree, void* low, void* high) { -: 645: stk_stack* enumResultStack; 1: 646: rb_red_blk_node* nil=tree->nil; 1: 647: rb_red_blk_node* x=tree->root->left; 1: 648: rb_red_blk_node* lastBest=nil; -: 649: 1: 650: enumResultStack=StackCreate(); 6: 651: while(nil != x) { 4: 652: if ( 1 == (tree->Compare(x->key,high)) ) { /* x->key > high */ 1: 653: x=x->left; -: 654: } else { 3: 655: lastBest=x; 3: 656: x=x->right; -: 657: } -: 658: } 8: 659: while ( (lastBest != nil) && (1 != tree->Compare(low,lastBest->key))) { 6: 660: StackPush(enumResultStack,lastBest); 6: 661: lastBest=TreePredecessor(tree,lastBest); -: 662: } 1: 663: return(enumResultStack); -: 664:} -: 665: -: 666: -: 667: -: 668: -: 669: -: 670: -: 671: