1 /// \file RBTree.d 2 3 module tagion.betterC.utils.RBTree; 4 /* 5 * [PROG] : Red Black Tree 6 * [AUTHOR] : Ashfaqur Rahman <sajib.finix@gmail.com> 7 * [PURPOSE] : Red-Black tree is an algorithm for creating a balanced 8 * binary search tree data structure. Implementing a red-balck tree 9 * data structure is the purpose of this program. 10 * 11 * [DESCRIPTION] : Its almost like the normal binary search tree data structure. But 12 * for keeping the tree balanced an extra color field is introduced to each node. 13 * This tree will mantain bellow properties. 14 * 1. Nodes can be either RED or BLACK. 15 * 2. root is BLACK. 16 * 3. Leaves of this tree are null nodes. Here null is represented bya special node null. 17 * Each null nodes are BLACK. So each leave is BLACK. 18 * 4. Each RED node's parent is BLACK 19 * 5. Each simple path taken from a node to descendent leaf has same number of black height. 20 * That means each path contains same number of BLACK nodes. 21 22 */ 23 24 @nogc: 25 import tagion.betterC.utils.Memory; 26 import tagion.betterC.utils.Stack; 27 28 //import hibon.HiBONBase : Key; 29 import std.traits : isPointer; 30 31 //import core.stdc.stdio; 32 33 RBTreeT!(K) RBTree(K)(const bool owns = true) { 34 RBTreeT!(K) result; 35 with (result) { 36 nill = &NILL; 37 root = nill; 38 } 39 result.owns = owns; 40 return result; 41 } 42 43 struct RBTreeT(K) { 44 @nogc: 45 enum Color { 46 RED, 47 BLACK 48 } 49 50 static this() { 51 NILL.color = Color.BLACK; 52 } 53 54 struct Node { 55 @nogc: 56 K item; 57 Color color; 58 Node* parent; 59 Node* left; 60 Node* right; 61 } 62 63 private { 64 static Node NILL; 65 Node* nill; 66 Node* root; 67 bool owns; 68 } 69 70 RBTreeT expropriate() { 71 auto result = RBTree!K(owns); 72 result.root = root; 73 root = nill; 74 return result; 75 } 76 77 void surrender() { 78 root = nill; 79 owns = false; 80 } 81 82 ~this() { 83 dispose; 84 } 85 86 void dispose() { 87 void _dispose(Node* current) { 88 if (current !is nill) { 89 _dispose(current.left); 90 _dispose(current.right); 91 if (owns) { 92 static if (isPointer!K) { 93 94 95 96 .dispose(current.item); 97 } 98 else static if (__traits(compiles, current.item.dispose)) { 99 current.item.dispose; 100 } 101 } 102 current.dispose; 103 } 104 } 105 106 _dispose(root); 107 root = nill; 108 } 109 110 /* Print tree items by inorder tree walk */ 111 112 @property empty() const pure { 113 return root is nill; 114 } 115 116 protected Node* _search(const(K) item) { 117 Node* x = root; 118 while ((x !is nill) && (compare(x.item, item) != 0)) { 119 if (compare(x.item, item) > 0) { 120 x = x.left; 121 } 122 else { 123 x = x.right; 124 } 125 } 126 return x; 127 } 128 129 static int compare(K)(scope const(K) a, scope const(K) b) pure { 130 static if (__traits(compiles, a.opCmp(b))) { 131 return a.opCmp(b); 132 } 133 else { 134 if (a < b) { 135 return -1; 136 } 137 else if (a == b) { 138 return 0; 139 } 140 return 1; 141 } 142 } 143 144 version (WebAssembly) { 145 void dump(int iter_max = 20) const { 146 // empty 147 } 148 } 149 else { 150 void dump(int iter_max = 20) const { 151 import core.stdc.stdio; 152 153 const(char[4]) INDENT = " ->"; 154 void _dump(const(Node*) current, const uint level = 1) @nogc { 155 if (current !is nill) { 156 _dump(current.left, level + 1); 157 foreach (i; 0 .. level) { 158 printf("%s", INDENT.ptr); 159 } 160 printf("%p\n", current); 161 iter_max--; 162 assert(iter_max > 0); 163 _dump(current.right, level + 1); 164 } 165 } 166 167 printf("DUMP %p %p\n", root, nill); 168 _dump(root); 169 } 170 } 171 172 const(Node*) search(const(K) item) const pure { 173 const(Node*) _search(const(Node*) current) pure { 174 if (current !is nill) { 175 import std.traits; 176 177 const cmp = compare(current.item, item); 178 if (cmp == 0) { 179 return current; 180 } 181 else if (cmp > 0) { 182 return _search(current.left); 183 } 184 else { 185 return _search(current.right); 186 } 187 } 188 return nill; 189 } 190 191 auto result = _search(root); 192 if (result !is nill) { 193 return result; 194 } 195 return null; 196 } 197 198 bool exists(K item) const { 199 // const result=search(item); 200 return search(item) !is null; 201 } 202 203 @property size_t length() const { 204 size_t count; 205 foreach (m; this[]) { 206 count++; 207 } 208 return count; 209 } 210 211 protected Node* tree_minimum(Node* x) { 212 while (x.left !is nill) { 213 x = x.left; 214 } 215 return x; 216 } 217 218 /* 219 * Insertion is done by the same procedure for BST Insert. Except new node is colored 220 * RED. As it is coloured RED it may violate property 2 or 4. For this reason an 221 * auxilary procedure called insert_fixup is called to fix these violation. 222 */ 223 224 bool insert(K item) { 225 bool result; 226 Node* z = create!Node; 227 scope (exit) { 228 if (!result) { 229 z.dispose; 230 } 231 } 232 z.item = item; 233 return result = insert(z); 234 } 235 236 const(K) get(const(K) item) const { 237 alias _K = const(K); 238 auto result = search(item); 239 if (result !is null) { 240 return result.item; 241 } 242 return K.init; 243 } 244 245 private bool insert(Node* z) { 246 Node* x, y; 247 z.color = Color.RED; 248 z.left = nill; 249 z.right = nill; 250 251 x = root; 252 y = nill; 253 254 /* 255 * Go through the tree untill a leaf(null) is reached. y is used for keeping 256 * track of the last non-null node which will be z's parent. 257 */ 258 while (x !is nill) { 259 y = x; 260 const cmp = compare(z.item, x.item); 261 if (cmp < 0) { 262 x = x.left; 263 } 264 else if (cmp == 0) { 265 // Item already exists 266 return false; 267 } 268 else { 269 x = x.right; 270 } 271 } 272 273 if (y is nill) { 274 root = z; 275 } 276 else if (compare(z.item, y.item) <= 0) { 277 y.left = z; 278 } 279 else { 280 y.right = z; 281 } 282 283 z.parent = y; 284 285 insert_fixup(z); 286 return true; 287 } 288 289 /* 290 * Here is the psudocode for fixing violations. 291 * 292 * while (z's parent is RED) 293 * if (z's parent is z's grand parent's left child) then 294 * if (z's right uncle or grand parent's right child is RED) then 295 * make z's parent and uncle BLACK 296 * make z's grand parent RED 297 * make z's grand parent new z as it may violate property 2 & 4 298 * (so while loop will contineue) 299 * 300 * else(z's right uncle is not RED) 301 * if (z is z's parents right child) then 302 * make z's parent z 303 * left rotate z 304 * make z's parent's color BLACK 305 * make z's grand parent's color RED 306 * right rotate z's grand parent 307 * ( while loop won't pass next iteration as no violation) 308 * 309 * else(z's parent is z's grand parent's right child) 310 * do exact same thing above just swap left with right and vice-varsa 311 * 312 * At this point only property 2 can be violated so make root BLACK 313 */ 314 315 protected void insert_fixup(Node* z) { 316 while (z.parent.color is Color.RED) { 317 318 /* z's parent is left child of z's grand parent*/ 319 if (z.parent is z.parent.parent.left) { 320 321 /* z's grand parent's right child is RED */ 322 if ((z.parent.parent.right !is nill) && (z.parent.parent.right.color is Color.RED)) { 323 z.parent.color = Color.BLACK; 324 z.parent.parent.right.color = Color.BLACK; 325 z.parent.parent.color = Color.RED; 326 z = z.parent.parent; 327 } 328 329 /* z's grand parent's right child is not RED */ 330 else { 331 332 /* z is z's parent's right child */ 333 if (z is z.parent.right) { 334 z = z.parent; 335 left_rotate(z); 336 } 337 338 z.parent.color = Color.BLACK; 339 z.parent.parent.color = Color.RED; 340 right_rotate(z.parent.parent); 341 } 342 } 343 344 /* z's parent is z's grand parent's right child */ 345 else { 346 347 /* z's left uncle or z's grand parent's left child is also RED */ 348 if (z.parent.parent.left.color is Color.RED) { 349 z.parent.color = Color.BLACK; 350 z.parent.parent.left.color = Color.BLACK; 351 z.parent.parent.color = Color.RED; 352 z = z.parent.parent; 353 } 354 355 /* z's left uncle is not RED */ 356 else { 357 /* z is z's parents left child */ 358 if (z is z.parent.left) { 359 z = z.parent; 360 right_rotate(z); 361 } 362 363 z.parent.color = Color.BLACK; 364 z.parent.parent.color = Color.RED; 365 left_rotate(z.parent.parent); 366 } 367 } 368 } 369 370 root.color = Color.BLACK; 371 } 372 373 /* 374 * Lets say y is x's right child. Left rotate x by making y, x's parent and x, y's 375 * left child. y's left child becomes x's right child. 376 * 377 * x y 378 * / \ / \ 379 * STA y -----------> x STC 380 * / \ / \ 381 * STB STC STA STB 382 */ 383 384 void left_rotate(Node* x) { 385 Node* y; 386 387 /* Make y's left child x's right child */ 388 y = x.right; 389 x.right = y.left; 390 if (y.left !is nill) { 391 y.left.parent = x; 392 } 393 394 /* Make x's parent y's parent and y, x's parent's child */ 395 y.parent = x.parent; 396 if (y.parent is nill) { 397 root = y; 398 } 399 else if (x is x.parent.left) { 400 x.parent.left = y; 401 } 402 else { 403 x.parent.right = y; 404 } 405 406 /* Make x, y's left child & y, x's parent */ 407 y.left = x; 408 x.parent = y; 409 } 410 411 /* 412 * Lets say y is x's left child. Right rotate x by making x, y's right child and y 413 * x's parent. y's right child becomes x's left child. 414 * 415 * | | 416 * y 417 * / \ / \ 418 * y STA ----------------> STB x 419 * / \ / \ 420 * STB STC STC STA 421 */ 422 423 protected void right_rotate(Node* x) { 424 Node* y; 425 426 /* Make y's right child x's left child */ 427 y = x.left; 428 x.left = y.right; 429 if (y.right !is nill) { 430 y.right.parent = x; 431 } 432 433 /* Make x's parent y's parent and y, x's parent's child */ 434 y.parent = x.parent; 435 if (y.parent is nill) { 436 root = y; 437 } 438 else if (x is x.parent.left) { 439 x.parent.left = y; 440 } 441 else { 442 x.parent.right = y; 443 } 444 445 /* Make y, x's parent and x, y's child */ 446 y.right = x; 447 x.parent = y; 448 } 449 450 /* 451 * Deletion is done by the same mechanism as BST deletion. If z has no child, z is 452 * removed. If z has single child, z is replaced by its child. Else z is replaced by 453 * its successor. If successor is not z's own child, successor is replaced by its 454 * own child first. then z is replaced by the successor. 455 * 456 * A pointer y is used to keep track. In first two case y is z. 3rd case y is z's 457 * successor. So in first two case y is removed. In 3rd case y is moved. 458 * 459 *Another pointer x is used to keep track of the node which replace y. 460 * 461 * As removing or moving y can harm red-black tree properties a variable 462 * yOriginalColor is used to keep track of the original colour. If its BLACK then 463 * removing or moving y harm red-black tree properties. In that case an auxilary 464 * procedure remove_fixup(x) is called to recover this. 465 */ 466 467 bool remove(K item) { 468 auto remove_node = _search(item); 469 if (remove_node !is nill) { 470 remove(remove_node); 471 return true; 472 } 473 return false; 474 } 475 476 protected void remove(ref Node* z) { 477 scope (exit) { 478 if (owns) { 479 static if (isPointer!K) { 480 481 482 483 .dispose(z.item); 484 } 485 else static if (__traits(compiles, z.item.dispose)) { 486 z.item.dispose; 487 } 488 } 489 z.dispose; 490 } 491 Node* y, x; 492 Color yOriginalColor; 493 494 y = z; 495 yOriginalColor = y.color; 496 497 if (z.left is nill) { 498 x = z.right; 499 transplant(z, z.right); 500 } 501 else if (z.right is nill) { 502 x = z.left; 503 transplant(z, z.left); 504 } 505 else { 506 y = tree_minimum(z.right); 507 yOriginalColor = y.color; 508 509 x = y.right; 510 511 if (y.parent == z) { 512 x.parent = y; 513 } 514 else { 515 transplant(y, y.right); 516 y.right = z.right; 517 y.right.parent = y; 518 } 519 520 transplant(z, y); 521 y.left = z.left; 522 y.left.parent = y; 523 y.color = z.color; 524 } 525 526 if (yOriginalColor is Color.BLACK) { 527 remove_fixup(x); 528 } 529 } 530 531 /* 532 * As y was black and removed x gains y's extra blackness. 533 * Move the extra blackness of x until 534 * 1. x becomes root. In that case just remove extra blackness 535 * 2. x becomes a RED and BLACK node. in that case just make x BLACK 536 * 537 * First check if x is x's parents left or right child. Say x is left child 538 * 539 * There are 4 cases. 540 * 541 * Case 1: x's sibling w is red. transform case 1 into case 2 by recoloring 542 * w and x's parent. Then left rotate x's parent. 543 * 544 * Case 2: x's sibling w is black, w's both children is black. Move x and w's 545 * blackness to x's parent by coloring w to RED and x's parent to BLACK. 546 * Make x's parent new x.Notice if case 2 come through case 1 x's parent becomes 547 * RED and BLACK as it became RED in case 1. So loop will stop in next iteration. 548 * 549 * Case 3: w is black, w's left child is red and right child is black. Transform 550 * case 3 into case 4 by recoloring w and w's left child, then right rotate w. 551 * 552 * Case 4: w is black, w's right child is red. recolor w with x's parent's color. 553 * make x's parent BLACK, w's right child black. Now left rotate x's parent. Make x 554 * point to root. So loop will be stopped in next iteration. 555 * 556 * If x is right child of it's parent do exact same thing swapping left<->right 557 */ 558 559 protected void remove_fixup(Node* x) { 560 Node* w; 561 562 while (x !is root && x.color is Color.BLACK) { 563 if (x is x.parent.left) { 564 w = x.parent.right; 565 566 if (w.color is Color.RED) { 567 w.color = Color.BLACK; 568 x.parent.color = Color.RED; 569 left_rotate(x.parent); 570 w = x.parent.right; 571 } 572 573 if (w.left.color is Color.BLACK && w.right.color is Color.BLACK) { 574 w.color = Color.RED; 575 x.parent.color = Color.BLACK; 576 x = x.parent; 577 } 578 else { 579 580 if (w.right.color is Color.BLACK) { 581 w.color = Color.RED; 582 w.left.color = Color.BLACK; 583 right_rotate(w); 584 w = x.parent.right; 585 } 586 587 w.color = x.parent.color; 588 x.parent.color = Color.BLACK; 589 x.right.color = Color.BLACK; 590 left_rotate(x.parent); 591 x = root; 592 593 } 594 595 } 596 else { 597 w = x.parent.left; 598 599 if (w.color is Color.RED) { 600 w.color = Color.BLACK; 601 x.parent.color = Color.BLACK; 602 right_rotate(x.parent); 603 w = x.parent.left; 604 } 605 606 if (w.left.color is Color.BLACK && w.right.color is Color.BLACK) { 607 w.color = Color.RED; 608 x.parent.color = Color.BLACK; 609 x = x.parent; 610 } 611 else { 612 613 if (w.left.color is Color.BLACK) { 614 w.color = Color.RED; 615 w.right.color = Color.BLACK; 616 left_rotate(w); 617 w = x.parent.left; 618 } 619 620 w.color = x.parent.color; 621 x.parent.color = Color.BLACK; 622 w.left.color = Color.BLACK; 623 right_rotate(x.parent); 624 x = root; 625 626 } 627 } 628 629 } 630 631 x.color = Color.BLACK; 632 } 633 634 /* replace node u with node v */ 635 protected void transplant(Node* u, Node* v) { 636 if (u.parent is nill) { 637 root = v; 638 } 639 else if (u is u.parent.left) { 640 u.parent.left = v; 641 } 642 else { 643 u.parent.right = v; 644 } 645 646 v.parent = u.parent; 647 } 648 649 Range opSlice() const { 650 // In betterC the descructor of RBTree is call if the argument is passed to the Range struct 651 // This is the reason why the pointer to RBTree is used 652 auto range = Range(root); 653 return range; 654 } 655 656 struct Range { 657 import std.traits; 658 659 private { 660 Node* nill; 661 Node* current; 662 Node* walker; 663 Stack!(Node*) stack; 664 } 665 666 this(const(Node*) root) { 667 this.nill = &RBTreeT.NILL; 668 walker = current = cast(Node*) root; 669 popFront; 670 } 671 672 ~this() { 673 dispose; 674 } 675 676 void dispose() { 677 stack.dispose; 678 walker = current = null; 679 } 680 681 private void push(Node* node) { 682 stack.push(node); 683 } 684 685 private Node* pop() { 686 if (stack.empty) { 687 return nill; 688 } 689 return stack.pop; 690 } 691 692 @property bool empty() const pure { 693 return (current is nill); 694 } 695 696 @property const(K) front() const pure { 697 if (current is nill) { 698 return K.init; 699 } 700 return current.item; 701 } 702 703 void popFront() { 704 while (walker !is nill) { 705 push(walker); 706 walker = walker.left; 707 } 708 709 if (!stack.empty) { 710 walker = current = pop; 711 walker = walker.right; 712 } 713 else { 714 current = nill; 715 } 716 } 717 } 718 } 719 720 unittest { 721 722 enum tcase = [ 723 60, 140, 20, 130, 30, 160, 110, 170, 40, 120, 50, 70, 100, 10, 150, 80, 724 90 725 ]; 726 const(int[17]) result = [ 727 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170 728 ]; 729 730 assert(tcase.length == result.length); 731 732 auto tree = RBTree!int(false); 733 734 foreach (item; tcase) { 735 tree.insert(item); 736 } 737 738 // Check that all the elements has been added 739 uint count; 740 741 foreach (n; tree[]) { 742 const item = result[count++]; 743 assert(n == item); 744 } 745 746 // Check the size of the check lists 747 assert(tcase.length == count); 748 749 enum indices = [5, 3, 14, 0, tcase.length - 1]; 750 751 // Check exists 752 foreach (i; indices) { 753 const item = result[i]; 754 assert(tree.exists(item)); 755 } 756 757 // Check search 758 foreach (i; indices) { 759 const item = result[i]; 760 const n = tree.search(item); 761 assert(n !is null); 762 assert(item == n.item); 763 } 764 765 // Check remove 766 foreach (i; indices) { 767 const item = result[i]; 768 const n_exists = tree.search(item); 769 assert(n_exists !is null); 770 tree.remove(item); 771 assert(!tree.exists(item)); 772 const n = tree.search(item); 773 assert(n is null); 774 count--; 775 assert(tree.length == count); 776 } 777 } 778 779 // unittest { 780 // import hibon.HiBON; 781 // auto tree=RBTree!(char[])(true); 782 // import std.typecons : Tuple; 783 // Tuple!(char[2], char[2], char[2], char[1], char[1], char[1]) check_list=[ 784 // "07", "17", "42", "a", "b", "c" 785 // ]; 786 787 // char[][check_list.length] key_list; 788 // foreach(i, k; check_list) { 789 // create(key_list[i], k); 790 // } 791 792 // tree.insert(key_list[4]); 793 // tree.insert(key_list[1]); 794 // tree.insert(key_list[2]); 795 // tree.insert(key_list[3]); 796 // tree.insert(key_list[0]); 797 // tree.insert(key_list[5]); 798 799 // { 800 // auto range=tree[]; 801 // foreach(k; check_list) { 802 // assert(k == range.front); 803 // range.popFront; 804 // } 805 // } 806 807 // tree.remove(key_list[2]); 808 809 // { 810 // auto range=tree[]; 811 // foreach(i, k; check_list) { 812 // if (i !is 2) { 813 // assert(k == range.front); 814 // range.popFront; 815 // } 816 // } 817 // } 818 // } 819 820 unittest { 821 auto tree = RBTree!int(false); 822 tree.insert(42); 823 assert(tree.length is 1); 824 tree.insert(42); 825 assert(tree.length is 1); 826 // assert(0); 827 }