1 /* 2 * Copyright (c) International Business Machines Corp., 2001-2004 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See 12 * the GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 #include <stdio.h> 19 #include <stdlib.h> 20 #include <assert.h> 21 #include "rbt.h" 22 23 /* 24 * *********************************************** 25 * 26 * D.H. IBM, S. Rao 27 * 28 * Module: Operations executed on red-black struct 29 * 30 * *********************************************** 31 */ 32 33 /* Construct a red-black tree node */ 34 rbnode_construct(datatype object,rb_color color)35 rb_node *rbnode_construct(datatype object, rb_color color) 36 { 37 rb_node *node = (rb_node *) malloc(sizeof(rb_node)); 38 if (!node) { 39 fprintf(stderr, "Memory Shortage - No Execution Possible\n"); 40 return NULL; 41 } 42 node->object = object; 43 node->color = color; 44 node->parent = node->right = node->left = NULL; 45 return node; 46 } 47 48 /* Destructor of a red-black tree node */ 49 rbnode_destruct(rb_node * node,destructor d)50 void rbnode_destruct(rb_node * node, destructor d) 51 { 52 if (!node) 53 return; 54 if (d != NULL) 55 d(node->object); 56 rbnode_destruct(node->right, d); 57 rbnode_destruct(node->left, d); 58 free(node); 59 } 60 61 /* Determine the depth of the subtree spanned by a given node */ 62 rbnode_depth(rb_node * node)63 int rbnode_depth(rb_node * node) 64 { 65 /* Recursively determine the depth of the left and right 66 * subtrees 67 */ 68 int irightdepth = (node->right) ? rbnode_depth(node->right) : 0; 69 int ileftdepth = (node->left) ? rbnode_depth(node->left) : 0; 70 71 /* Return the maximal child depth + 1 (the current node) */ 72 return ((irightdepth > 73 ileftdepth) ? (irightdepth + 1) : (ileftdepth + 1)); 74 } 75 76 /* Return the leftmost leaf in the tree */ 77 rbnode_minimum(rb_node * node)78 rb_node *rbnode_minimum(rb_node * node) 79 { 80 while (node->left) 81 node = node->left; 82 return node; 83 } 84 85 /* Return the rightmost leaf in the tree */ 86 rbnode_maximum(rb_node * node)87 rb_node *rbnode_maximum(rb_node * node) 88 { 89 while (node->right) 90 node = node->right; 91 return node; 92 } 93 94 /* Replace an object */ 95 rbnode_replace(rb_node * node,datatype object)96 void rbnode_replace(rb_node * node, datatype object) 97 { 98 /* Make sure the replacement does not violate the tree order 99 * Replace the object at the node 100 */ 101 node->object = object; 102 } 103 104 /* Get the next node in the tree (according to the tree order) */ 105 rbnode_successor(rb_node * node)106 rb_node *rbnode_successor(rb_node * node) 107 { 108 rb_node *succ_node; 109 110 if (node->right) { 111 112 /* If there is a right child, the successor is the 113 * minimal object in the sub-tree spanned by this 114 * child. 115 */ 116 117 succ_node = node->right; 118 while (succ_node->left) 119 succ_node = succ_node->left; 120 } else { 121 122 /* Otherwise, go up the tree until reaching the parent 123 * from the left direction. 124 */ 125 126 rb_node *prev_node = node; 127 succ_node = node->parent; 128 while (succ_node && prev_node == succ_node->right) { 129 prev_node = succ_node; 130 succ_node = succ_node->parent; 131 } 132 } 133 134 return (succ_node); 135 } 136 137 /* Get the previous node in the tree (according to the tree order) */ 138 rbnode_predecessor(rb_node * node)139 rb_node *rbnode_predecessor(rb_node * node) 140 { 141 rb_node *pred_node; 142 143 if (node->left) { 144 145 /* If there is a left child, the predecessor is the 146 * maximal object in the sub-tree spanned by this 147 * child. 148 */ 149 150 pred_node = node->left; 151 while (pred_node->right) 152 pred_node = pred_node->right; 153 } else { 154 155 /* Otherwise, go up the tree until reaching the parent 156 * from the right direction. 157 */ 158 159 rb_node *prev_node = node; 160 pred_node = node->parent; 161 while (pred_node && prev_node == pred_node->left) { 162 prev_node = pred_node; 163 pred_node = pred_node->parent; 164 } 165 } 166 167 return (pred_node); 168 } 169 170 /* Return a pointer to a duplication of the given node */ 171 rbnode_duplicate(rb_node * node)172 rb_node *rbnode_duplicate(rb_node * node) 173 { 174 /* Create a node of the same color, containing the same 175 * object 176 */ 177 rb_node *dup_node = rbnode_construct(node->object, node->color); 178 if (!dup_node) 179 return NULL; 180 181 /* Duplicate the children recursively */ 182 if (node->right) { 183 dup_node->right = rbnode_duplicate(node->right); 184 dup_node->right->parent = dup_node; 185 } else { 186 dup_node->right = NULL; 187 } 188 189 if (node->left) { 190 dup_node->left = rbnode_duplicate(node->left); 191 dup_node->left->parent = dup_node; 192 } else { 193 dup_node->left = NULL; 194 } 195 196 return dup_node; /* Return the duplicated node */ 197 } 198 199 /* Traverse a red-black subtree */ 200 rbnode_traverse(rb_node * node,opr * op)201 void rbnode_traverse(rb_node * node, opr * op) 202 { 203 if (!node) 204 return; 205 rbnode_traverse(node->left, op); 206 op(node->object); 207 rbnode_traverse(node->right, op); 208 } 209 210 /* 211 * *********************************** 212 * 213 * Operations on rb_tree struct 214 * 215 * *********************************** 216 */ 217 218 /* Intialize a tree */ rbtree_init(rb_tree * tree)219 void rbtree_init(rb_tree * tree) 220 { 221 /* tree->comp = comp; */ 222 tree->isize = 0; 223 tree->root = NULL; 224 } 225 226 /* Construct a tree given a comparison function */ 227 rbtree_construct()228 rb_tree *rbtree_construct() 229 { 230 rb_tree *tree = (rb_tree *) malloc(sizeof(rb_tree)); 231 if (!tree) { 232 fprintf(stderr, "Memory Issue - Shortge Exists!\n"); 233 return NULL; 234 } 235 rbtree_init(tree); 236 return tree; 237 } 238 239 /* Remove all objects from a black-red tree */ 240 rbtree_clean(rb_tree * tree,destructor d)241 void rbtree_clean(rb_tree * tree, destructor d) 242 { 243 if (tree->root) 244 rbnode_destruct(tree->root, d); 245 tree->root = NULL; 246 tree->isize = 0; 247 } 248 249 /* Destruct a red-black tree */ 250 rbtree_destruct(rb_tree * tree,destructor d)251 void rbtree_destruct(rb_tree * tree, destructor d) 252 { 253 rbtree_clean(tree, d); 254 free(tree); 255 } 256 257 /* Returns the size of the tree */ 258 rbtree_size(rb_tree * tree)259 int rbtree_size(rb_tree * tree) 260 { 261 return tree->isize; 262 } 263 264 /* Returns the depth of the tree */ 265 rbtree_depth(rb_tree * tree)266 int rbtree_depth(rb_tree * tree) 267 { 268 if (!(tree->root)) 269 return 0; 270 return rbnode_depth(tree->root); 271 } 272 273 /* Check whether the tree contains a certain object */ 274 rbtree_contains(rb_tree * tree,datatype object)275 int rbtree_contains(rb_tree * tree, datatype object) 276 { 277 return (rbtree_find(tree, object) != NULL); 278 } 279 280 /* Insert an object into the rb-tree */ 281 rbtree_insert(rb_tree * tree,datatype object)282 rb_node *rbtree_insert(rb_tree * tree, datatype object) 283 { 284 rb_node *cur_node; 285 rb_node *new_node; 286 int comp_result = 0; 287 288 if (!(tree->root)) { 289 /* Assign a new root node (the root is always 290 * black) 291 */ 292 new_node = rbnode_construct(object, black); 293 if (!new_node) 294 return NULL; 295 tree->root = new_node; 296 tree->isize = 1; 297 return new_node; 298 } 299 300 /* Find a spot for the new object, insert the object as a red 301 * leaf 302 */ 303 304 cur_node = tree->root; 305 new_node = rbnode_construct(object, red); 306 if (!new_node) 307 return NULL; 308 309 while (cur_node) { 310 /* Compare inserted object with the object stored in 311 * the current node 312 */ 313 comp_result = COMP_NODES(object, cur_node->object); 314 if (comp_result == 0) { 315 printf 316 ("Attempted to insert duplicate node, aborting\n"); 317 free(new_node); 318 return NULL; 319 } 320 if (comp_result > 0) { 321 if (!(cur_node->left)) { 322 /* Insert the new leaf as the left 323 * child of the current node 324 */ 325 cur_node->left = new_node; 326 new_node->parent = cur_node; 327 cur_node = NULL; /* Terminate the while loop */ 328 } else { 329 /* Go to the left subtree */ 330 cur_node = cur_node->left; 331 } 332 } else { 333 if (!(cur_node->right)) { 334 /* Insert the new leaf as the right 335 * child of the current node 336 */ 337 cur_node->right = new_node; 338 new_node->parent = cur_node; 339 cur_node = NULL; /* Terminate the while loop */ 340 } else { 341 /* Go to the right subtree */ 342 cur_node = cur_node->right; 343 } 344 } 345 } 346 347 /* Mark the fact that a new node was added */ 348 tree->isize++; 349 350 /* Fix the tree properties */ 351 rbtree_insert_fixup(tree, new_node); 352 353 return new_node; 354 } 355 356 /* Insert a new object to the tree as the a successor of a given 357 * node 358 */ 359 insert_successor_at(rb_tree * tree,rb_node * at_node,datatype object)360 rb_node *insert_successor_at(rb_tree * tree, rb_node * at_node, datatype object) 361 { 362 rb_node *parent; 363 rb_node *new_node; 364 365 if (!(tree->root)) { 366 /* Assign a new root node (the root is always 367 * black) 368 */ 369 new_node = rbnode_construct(object, black); 370 if (!new_node) 371 return NULL; 372 tree->root = new_node; 373 tree->isize = 1; 374 return new_node; 375 } 376 377 /* Insert the new object as a red leaf, being the successor of 378 * node 379 */ 380 new_node = rbnode_construct(object, red); 381 if (!new_node) 382 return NULL; 383 384 if (!at_node) { 385 /* The new node should become the tree's minimum Place 386 * is as the left child of the current minimal leaf 387 */ 388 parent = rbnode_minimum(tree->root); 389 parent->left = new_node; 390 } else { 391 /* Make sure the insertion does not violate the tree 392 * order In case given node has no right child, place 393 * the new node as its right child. Otherwise, place 394 * it at the leftmost position at the sub-tree rooted 395 * at its right side. 396 */ 397 if (!at_node->right) { 398 parent = at_node; 399 parent->right = new_node; 400 } else { 401 parent = rbnode_minimum(at_node->right); 402 parent->left = new_node; 403 } 404 } 405 406 new_node->parent = parent; 407 408 /* Mark that a new node was added */ 409 tree->isize++; 410 411 /* Fix the tree properties */ 412 rbtree_insert_fixup(tree, new_node); 413 414 return new_node; 415 } 416 417 /* Insert a new object to the tree as the a predecessor of a given node */ 418 insert_predecessor_at(rb_tree * tree,rb_node * at_node,datatype object)419 rb_node *insert_predecessor_at(rb_tree * tree, rb_node * at_node, 420 datatype object) 421 { 422 rb_node *parent; 423 rb_node *new_node; 424 425 if (!(tree->root)) { 426 /* Assign a new root node (the root is always 427 * black) 428 */ 429 new_node = rbnode_construct(object, black); 430 if (!new_node) 431 return NULL; 432 tree->root = new_node; 433 tree->isize = 1; 434 return new_node; 435 } 436 437 /* Insert the new object as a red leaf, being the predecessor 438 * of at_node 439 */ 440 new_node = rbnode_construct(object, red); 441 if (!new_node) 442 return NULL; 443 444 if (!at_node) { 445 /* The new node should become the tree maximum. Place 446 * is as the right child of the current maximal leaf 447 */ 448 parent = rbnode_maximum(tree->root); 449 parent->right = new_node; 450 } else { 451 /* Make sure the insertion does not violate the tree 452 * order In case given node has no left child, place 453 * the new node as its left child. Otherwise, place it 454 * at the rightmost position at the sub-tree rooted at 455 * its left side. 456 */ 457 if (!(at_node->left)) { 458 parent = at_node; 459 parent->left = new_node; 460 } else { 461 parent = rbnode_maximum(at_node->left); 462 parent->right = new_node; 463 } 464 } 465 466 new_node->parent = parent; 467 468 /* Mark that a new node was added */ 469 tree->isize++; 470 471 /* Fix the tree properties */ 472 rbtree_insert_fixup(tree, new_node); 473 474 return new_node; 475 } 476 477 /* Remove an object from the tree */ 478 rbtree_remove(rb_tree * tree,datatype object,destructor d)479 void rbtree_remove(rb_tree * tree, datatype object, destructor d) 480 { 481 rb_node *node = rbtree_find(tree, object); /* Find the node */ 482 rbtree_remove_at(tree, node, d); /* Remove the node */ 483 } 484 485 /* Remove the object pointed by the given node. */ 486 rbtree_remove_at(rb_tree * tree,rb_node * node,destructor d)487 void rbtree_remove_at(rb_tree * tree, rb_node * node, destructor d) 488 { 489 rb_node *child = NULL; 490 491 /* In case of deleting the single object stored in the tree, 492 * free the root, thus emptying the tree 493 */ 494 if (tree->isize == 1) { 495 rbnode_destruct(tree->root, d); 496 tree->root = NULL; 497 tree->isize = 0; 498 return; 499 } 500 501 /* Remove the given node from the tree */ 502 if (node->left && node->right) { 503 /* If the node we want to remove has two children, 504 * find its successor, which is the leftmost child in 505 * its right sub-tree and has at most one child (it 506 * may have a right child). 507 */ 508 rb_node *succ_node = rbnode_minimum(node->right); 509 510 /* Now physically swap node and its successor. Notice 511 * this may temporarily violate the tree properties, 512 * but we are going to remove node anyway. This way 513 * we have moved node to a position were it is more 514 * convinient to delete it. 515 */ 516 int immediate_succ = (node->right == succ_node); 517 rb_node *succ_parent = succ_node->parent; 518 rb_node *succ_left = succ_node->left; 519 rb_node *succ_right = succ_node->right; 520 rb_color succ_color = succ_node->color; 521 522 succ_node->parent = node->parent; 523 succ_node->left = node->left; 524 succ_node->right = immediate_succ ? node : node->right; 525 succ_node->color = node->color; 526 527 node->parent = immediate_succ ? succ_node : succ_parent; 528 node->left = succ_left; 529 node->right = succ_right; 530 node->color = succ_color; 531 532 if (!immediate_succ) { 533 if (succ_node == node->parent->left) 534 node->parent->left = node; 535 else 536 node->parent->right = node; 537 } 538 539 if (node->left) 540 node->left->parent = node; 541 if (node->right) 542 node->right->parent = node; 543 544 if (succ_node->parent) { 545 if (node == succ_node->parent->left) 546 succ_node->parent->left = succ_node; 547 else 548 succ_node->parent->right = succ_node; 549 } else { 550 tree->root = succ_node; 551 } 552 553 if (succ_node->left) 554 succ_node->left->parent = succ_node; 555 if (succ_node->right) 556 succ_node->right->parent = succ_node; 557 } 558 559 /* At this stage, the node we are going to remove has at most 560 * one child 561 */ 562 child = (node->left) ? node->left : node->right; 563 564 /* Splice out the node to be removed, by linking its parent 565 * straight to the removed node's single child. 566 */ 567 if (child) 568 child->parent = node->parent; 569 570 if (!(node->parent)) { 571 /* If we are deleting the root, make the child the new 572 * tree node 573 */ 574 tree->root = child; 575 } else { 576 /* Link the removed node parent to its child */ 577 if (node == node->parent->left) 578 node->parent->left = child; 579 else 580 node->parent->right = child; 581 } 582 583 /* Fix-up the red-black properties that may have been damaged: 584 * If we have just removed a black node, the black-depth 585 * property is no longer valid 586 */ 587 if (node->color == black && child) 588 rbtree_remove_fixup(tree, child); 589 590 /* Delete the un-necessary node (nullify both its children 591 * because the node's destructor is recursive). 592 */ 593 node->left = NULL; 594 node->right = NULL; 595 free(node); 596 597 /* Decrease the number of objects in the tree */ 598 tree->isize--; 599 } 600 601 /* Get the tree minimum */ 602 rbtree_minimum(rb_tree * tree)603 rb_node *rbtree_minimum(rb_tree * tree) 604 { 605 if (!(tree->root)) 606 return NULL; 607 608 /* Return the leftmost leaf in the tree */ 609 return rbnode_minimum(tree->root); 610 } 611 612 /* Get the tree maximum */ 613 rbtree_maximum(rb_tree * tree)614 rb_node *rbtree_maximum(rb_tree * tree) 615 { 616 if (!(tree->root)) 617 return NULL; 618 619 /* Return the rightmost leaf in the tree */ 620 return rbnode_maximum(tree->root); 621 } 622 623 /* Return a pointer to the node containing the given object */ 624 rbtree_find(rb_tree * tree,datatype object)625 rb_node *rbtree_find(rb_tree * tree, datatype object) 626 { 627 rb_node *cur_node = tree->root; 628 int comp_result; 629 630 while (cur_node) { 631 comp_result = COMP_NODES(object, cur_node->object); 632 /* In case of equality, we can return the current 633 * node. 634 */ 635 if (comp_result == 0) 636 return cur_node; 637 /* Go down to the left or right child. */ 638 cur_node = (comp_result > 0) ? cur_node->left : cur_node->right; 639 } 640 641 /* If we get here, the object is not in the tree */ 642 return NULL; 643 } 644 rbtree_rotate_left(rb_tree * tree,rb_node * x_node)645 void rbtree_rotate_left(rb_tree * tree, rb_node * x_node) 646 { 647 /* Get the right child of the node */ 648 rb_node *y_node = x_node->right; 649 650 /* Change its left subtree (T2) to x's right subtree */ 651 x_node->right = y_node->left; 652 653 /* Link T2 to its new parent x */ 654 if (y_node->left != NULL) 655 y_node->left->parent = x_node; 656 657 /* Assign x's parent to be y's parent */ 658 y_node->parent = x_node->parent; 659 660 if (!(x_node->parent)) { 661 /* Make y the new tree root */ 662 tree->root = y_node; 663 } else { 664 /* Assign a pointer to y from x's parent */ 665 if (x_node == x_node->parent->left) 666 x_node->parent->left = y_node; 667 else 668 x_node->parent->right = y_node; 669 } 670 671 /* Assign x to be y's left child */ 672 y_node->left = x_node; 673 x_node->parent = y_node; 674 } 675 676 /* Right-rotate the sub-tree spanned by the given node */ 677 rbtree_rotate_right(rb_tree * tree,rb_node * y_node)678 void rbtree_rotate_right(rb_tree * tree, rb_node * y_node) 679 { 680 /* Get the left child of the node */ 681 rb_node *x_node = y_node->left; 682 683 /* Change its right subtree (T2) to y's left subtree */ 684 y_node->left = x_node->right; 685 686 /* Link T2 to its new parent y */ 687 if (x_node->right != NULL) 688 x_node->right->parent = y_node; 689 690 /* Assign y's parent to be x's parent */ 691 x_node->parent = y_node->parent; 692 693 if (!(y_node->parent)) { 694 /* Make x the new tree root */ 695 tree->root = x_node; 696 } else { 697 /* Assign a pointer to x from y's parent */ 698 if (y_node == y_node->parent->left) 699 y_node->parent->left = x_node; 700 else 701 y_node->parent->right = x_node; 702 } 703 704 /* Assign y to be x's right child */ 705 x_node->right = y_node; 706 y_node->parent = x_node; 707 } 708 709 /* Fix the tree so it maintains the red-black properties after an insert */ 710 rbtree_insert_fixup(rb_tree * tree,rb_node * node)711 void rbtree_insert_fixup(rb_tree * tree, rb_node * node) 712 { 713 /* Fix the red-black propreties. We may have inserted a red 714 * leaf as the child of a red parent - so we have to fix the 715 * coloring of the parent recursively. 716 */ 717 rb_node *curr_node = node; 718 rb_node *grandparent; 719 rb_node *uncle; 720 721 assert(node && node->color == red); 722 723 while (curr_node != tree->root && curr_node->parent->color == red) { 724 /* Get a pointer to the current node's grandparent 725 * (the root is always black, so the red parent must 726 * have a parent). 727 */ 728 729 grandparent = curr_node->parent->parent; 730 731 if (curr_node->parent == grandparent->left) { 732 /* If the red parent is a left child, the 733 * uncle is the right child of the grandparent. 734 */ 735 uncle = grandparent->right; 736 737 if (uncle && uncle->color == red) { 738 739 /* If both parent and uncle are red, 740 * color them black and color the 741 * grandparent red. In case of a NULL 742 * uncle, treat it as a black node 743 */ 744 curr_node->parent->color = black; 745 uncle->color = black; 746 grandparent->color = red; 747 748 /* Move to the grandparent */ 749 curr_node = grandparent; 750 } else { 751 /* Make sure the current node is a 752 * right child. If not, left-rotate the 753 * parent's sub-tree so the parent 754 * becomes the right child of the 755 * current node (see _rotate_left). 756 */ 757 if (curr_node == curr_node->parent->right) { 758 curr_node = curr_node->parent; 759 rbtree_rotate_left(tree, curr_node); 760 } 761 762 /* Color the parent black and the 763 * grandparent red 764 */ 765 curr_node->parent->color = black; 766 grandparent->color = red; 767 768 /* Right-rotate the grandparent's 769 * sub-tree 770 */ 771 rbtree_rotate_right(tree, grandparent); 772 } 773 } else { 774 /* If the red parent is a right child, the 775 * uncle is the left child of the grandparent. 776 */ 777 uncle = grandparent->left; 778 779 if (uncle && uncle->color == red) { 780 /* If both parent and uncle are red, 781 * color them black and color the 782 * grandparent red. In case of a NULL 783 * uncle, treat it as a black node 784 */ 785 curr_node->parent->color = black; 786 uncle->color = black; 787 grandparent->color = red; 788 789 /* Move to the grandparent */ 790 curr_node = grandparent; 791 } else { 792 /* Make sure the current node is a 793 * left child. If not, right-rotate 794 * the parent's sub-tree so the parent 795 * becomes the left child of the 796 * current node. 797 */ 798 if (curr_node == curr_node->parent->left) { 799 curr_node = curr_node->parent; 800 rbtree_rotate_right(tree, curr_node); 801 } 802 803 /* Color the parent black and the 804 * grandparent red 805 */ 806 curr_node->parent->color = black; 807 grandparent->color = red; 808 809 /* Left-rotate the grandparent's 810 * sub-tree 811 */ 812 rbtree_rotate_left(tree, grandparent); 813 } 814 } 815 } 816 817 /* Make sure that the root is black */ 818 tree->root->color = black; 819 } 820 rbtree_remove_fixup(rb_tree * tree,rb_node * node)821 void rbtree_remove_fixup(rb_tree * tree, rb_node * node) 822 { 823 rb_node *curr_node = node; 824 rb_node *sibling; 825 826 while (curr_node != tree->root && curr_node->color == black) { 827 /* Get a pointer to the current node's sibling (notice 828 * that the node's parent must exist, since the node 829 * is not the root). 830 */ 831 if (curr_node == curr_node->parent->left) { 832 /* If the current node is a left child, its 833 * sibling is the right child of the parent. 834 */ 835 sibling = curr_node->parent->right; 836 837 /* Check the sibling's color. Notice that NULL 838 * nodes are treated as if they are colored 839 * black. 840 */ 841 if (sibling && sibling->color == red) { 842 /* In case the sibling is red, color 843 * it black and rotate. Then color 844 * the parent red (the grandparent is 845 * now black) 846 */ 847 sibling->color = black; 848 curr_node->parent->color = red; 849 rbtree_rotate_left(tree, curr_node->parent); 850 sibling = curr_node->parent->right; 851 } 852 853 if (sibling && 854 (!(sibling->left) || sibling->left->color == black) 855 && (!(sibling->right) 856 || sibling->right->color == black)) { 857 /* If the sibling has two black 858 * children, color it red 859 */ 860 sibling->color = red; 861 if (curr_node->parent->color == red) { 862 /* If the parent is red, we 863 * can safely color it black 864 * and terminate the fix 865 * process. 866 */ 867 curr_node->parent->color = black; 868 /* In order to stop the while loop */ 869 curr_node = tree->root; 870 } else { 871 /* The black depth of the 872 * entire sub-tree rooted at 873 * the parent is now too small 874 * - fix it up recursively. 875 */ 876 curr_node = curr_node->parent; 877 } 878 } else { 879 if (!sibling) { 880 /* Take special care of the 881 * case of a NULL sibling 882 */ 883 if (curr_node->parent->color == red) { 884 curr_node->parent->color = 885 black; 886 /* In order to stop 887 * the while loop */ 888 curr_node = tree->root; 889 } else { 890 curr_node = curr_node->parent; 891 } 892 } else { 893 /* In this case, at least one 894 * of the sibling's children 895 * is red. It is therfore 896 * obvious that the sibling 897 * itself is black. 898 */ 899 if (sibling->right 900 && sibling->right->color == red) { 901 /* If the right child 902 * of the sibling is 903 * red, color it black 904 * and rotate around 905 * the current parent. 906 */ 907 sibling->right->color = black; 908 rbtree_rotate_left(tree, 909 curr_node-> 910 parent); 911 } else { 912 /* If the left child 913 * of the sibling is 914 * red, rotate around 915 * the sibling, then 916 * rotate around the 917 * new sibling of our 918 * current node. 919 */ 920 rbtree_rotate_right(tree, 921 sibling); 922 sibling = 923 curr_node->parent->right; 924 rbtree_rotate_left(tree, 925 sibling); 926 } 927 928 /* It is now safe to color the 929 * parent black and to 930 * terminate the fix process. 931 */ 932 if (curr_node->parent->parent) 933 curr_node->parent->parent-> 934 color = 935 curr_node->parent->color; 936 curr_node->parent->color = black; 937 /* In order to stop the while loop */ 938 curr_node = tree->root; 939 } 940 } 941 } else { 942 /* If the current node is a right child, its 943 * sibling is the left child of the parent. 944 */ 945 sibling = curr_node->parent->left; 946 947 /* Check the sibling's color. Notice that NULL 948 * nodes are treated as if they are colored 949 * black. 950 */ 951 if (sibling && sibling->color == red) { 952 /* In case the sibling is red, color 953 * it black and rotate. Then color 954 * the parent red (the grandparent is 955 * now black). 956 */ 957 sibling->color = black; 958 curr_node->parent->color = red; 959 rbtree_rotate_right(tree, curr_node->parent); 960 961 sibling = curr_node->parent->left; 962 } 963 964 if (sibling && 965 (!(sibling->left) || sibling->left->color == black) 966 && (!(sibling->right) 967 || sibling->right->color == black)) { 968 /* If the sibling has two black children, color it red */ 969 sibling->color = red; 970 if (curr_node->parent->color == red) { 971 /* If the parent is red, we 972 * can safely color it black 973 * and terminate the fix-up 974 * process. 975 */ 976 curr_node->parent->color = black; 977 /* In order to stop the while 978 * loop 979 */ 980 curr_node = tree->root; 981 } else { 982 /* The black depth of the 983 * entire sub-tree rooted at 984 * the parent is now too small 985 * - fix it up recursively. 986 */ 987 curr_node = curr_node->parent; 988 } 989 } else { 990 if (!sibling) { 991 /* Take special care of the 992 * case of a NULL sibling */ 993 if (curr_node->parent->color == red) { 994 curr_node->parent->color = 995 black; 996 /* In order to stop 997 * the while loop */ 998 curr_node = tree->root; 999 } else { 1000 curr_node = curr_node->parent; 1001 } 1002 } else { 1003 /* In this case, at least one 1004 * of the sibling's children is 1005 * red. It is therfore obvious 1006 * that the sibling itself is 1007 * black. 1008 */ 1009 if (sibling->left 1010 && sibling->left->color == red) { 1011 /* If the left child 1012 * of the sibling is 1013 * red, color it black 1014 * and rotate around 1015 * the current parent 1016 */ 1017 sibling->left->color = black; 1018 rbtree_rotate_right(tree, 1019 curr_node-> 1020 parent); 1021 } else { 1022 /* If the right child 1023 * of the sibling is 1024 * red, rotate around 1025 * the sibling, then 1026 * rotate around the 1027 * new sibling of our 1028 * current node 1029 */ 1030 rbtree_rotate_left(tree, 1031 sibling); 1032 sibling = 1033 curr_node->parent->left; 1034 rbtree_rotate_right(tree, 1035 sibling); 1036 } 1037 1038 /* It is now safe to color the 1039 * parent black and to 1040 * terminate the fix process. 1041 */ 1042 if (curr_node->parent->parent) 1043 curr_node->parent->parent-> 1044 color = 1045 curr_node->parent->color; 1046 curr_node->parent->color = black; 1047 /* In order to stop the while loop */ 1048 curr_node = tree->root; 1049 } 1050 } 1051 } 1052 } 1053 1054 /* The root can always be colored black */ 1055 curr_node->color = black; 1056 } 1057 1058 /* Traverse a red-black tree */ 1059 rbtree_traverse(rb_tree * tree,opr * op)1060 void rbtree_traverse(rb_tree * tree, opr * op) 1061 { 1062 rbnode_traverse(tree->root, op); 1063 } 1064