C++ Program to Implement Red Black Tree

«
»
This C++ Program demonstrates the implementation of Red Black Tree.

Here is source code of the C++ Program to demonstrate the implementation of Red Black Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Red Black Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cassert>
  12. #define INDENT_STEP  4
  13. using namespace std;
  14. enum color { RED, BLACK };
  15. /*
  16.  * Node RBTree Declaration
  17.  */
  18. typedef struct rbtree_node
  19. {
  20.     enum color color;
  21.     void *key;
  22.     void *value;
  23.     rbtree_node *left, *right, *parent;
  24. }*node;
  25.  
  26. typedef struct rbtree_t
  27. {
  28.     node root;
  29. }*rbtree;
  30.  
  31. /*
  32.  * Class RBTree Declaration
  33.  */
  34. class RBTree
  35. {
  36.     public:
  37.         typedef int (*compare_func)(void* left, void* right);
  38.         rbtree rbtree_create();
  39.         void* rbtree_lookup(rbtree t, void* , compare_func compare);
  40.         void rbtree_insert(rbtree t, void* , void* , compare_func compare);
  41.         void rbtree_delete(rbtree t, void* , compare_func compare);
  42.         node grandparent(node n);
  43.         node sibling(node n);
  44.         node uncle(node n);
  45.         void verify_properties(rbtree t);
  46.         void verify_property_1(node root);
  47.         void verify_property_2(node root);
  48.         color node_color(node n);
  49.         void verify_property_4(node root);
  50.         void verify_property_5(node root);
  51.         void verify_property_5_helper(node n, int , int*);
  52.         node new_node(void* key, void* , color , node , node);
  53.         node lookup_node(rbtree t, void* , compare_func compare);
  54.         void rotate_left(rbtree t, node n);
  55.         void rotate_right(rbtree t, node n);
  56.         void replace_node(rbtree t, node oldn, node newn);
  57.         void insert_case1(rbtree t, node n);
  58.         void insert_case2(rbtree t, node n);
  59.         void insert_case3(rbtree t, node n);
  60.         void insert_case4(rbtree t, node n);
  61.         void insert_case5(rbtree t, node n);
  62.         node maximum_node(node root);
  63.         void delete_case1(rbtree t, node n);
  64.         void delete_case2(rbtree t, node n);
  65.         void delete_case3(rbtree t, node n);
  66.         void delete_case4(rbtree t, node n);
  67.         void delete_case5(rbtree t, node n);
  68.         void delete_case6(rbtree t, node n);
  69. };
  70. /*
  71.  * Return Grandparent of Node 
  72.  */
  73. node RBTree::grandparent(node n)
  74. {
  75.     assert (n != NULL);
  76.     assert (n->parent != NULL);
  77.     assert (n->parent->parent != NULL);
  78.     return n->parent->parent;
  79. }
  80.  
  81. /*
  82.  * Return Sibling of Node 
  83.  */
  84. node RBTree::sibling(node n)
  85. {
  86.     assert (n != NULL);
  87.     assert (n->parent != NULL);
  88.     if (n == n->parent->left)
  89.         return n->parent->right;
  90.     else
  91.         return n->parent->left;
  92. }
  93.  
  94. /*
  95.  * Return Uncle of Node 
  96.  */
  97. node RBTree::uncle(node n)
  98. {
  99.     assert (n != NULL);
  100.     assert (n->parent != NULL);
  101.     assert (n->parent->parent != NULL);
  102.     return sibling(n->parent);
  103. }
  104.  
  105. /*
  106.  * Verifying Properties of Red black Tree
  107.  */
  108. void RBTree::verify_properties(rbtree t)
  109. {
  110.     verify_property_1 (t->root);
  111.     verify_property_2 (t->root);
  112.     verify_property_4 (t->root);
  113.     verify_property_5 (t->root);
  114. }
  115. /*
  116.  * Verifying Property 1
  117.  */
  118. void RBTree::verify_property_1(node n)
  119. {
  120.     assert (node_color(n) == RED || node_color(n) == BLACK);
  121.     if (n == NULL)
  122.         return;
  123.     verify_property_1(n->left);
  124.     verify_property_1(n->right);
  125. }
  126. /*
  127.  * Verifying Property 2
  128.  */
  129. void RBTree::verify_property_2(node root)
  130. {
  131.     assert (node_color(root) == BLACK);
  132. }
  133. /*
  134.  * Returns color of a node
  135.  */
  136. color RBTree::node_color(node n)
  137. {
  138.     return n == NULL ? BLACK : n->color;
  139. }
  140. /*
  141.  * Verifying Property 4
  142.  */
  143. void RBTree::verify_property_4(node n)
  144. {
  145.     if (node_color(n) == RED)
  146.     {
  147.         assert (node_color(n->left) == BLACK);
  148.         assert (node_color(n->right) == BLACK);
  149.         assert (node_color(n->parent) == BLACK);
  150.     }
  151.     if (n == NULL)
  152.         return;
  153.     verify_property_4(n->left);
  154.     verify_property_4(n->right);
  155. }
  156. /*
  157.  * Verifying Property 5
  158.  */
  159. void RBTree::verify_property_5(node root)
  160. {
  161.     int black_count_path = -1;
  162.     verify_property_5_helper(root, 0, &black_count_path);
  163. }
  164.  
  165. void RBTree::verify_property_5_helper(node n, int black_count, int* path_black_count)
  166. {
  167.     if (node_color(n) == BLACK)
  168.     {
  169.         black_count++;
  170.     }
  171.     if (n == NULL)
  172.     {
  173.         if (*path_black_count == -1)
  174.         {
  175.             *path_black_count = black_count;
  176.         }
  177.         else
  178.         {
  179.             assert (black_count == *path_black_count);
  180.         }
  181.         return;
  182.     }
  183.     verify_property_5_helper(n->left,  black_count, path_black_count);
  184.     verify_property_5_helper(n->right, black_count, path_black_count);
  185. }
  186.  
  187. /*
  188.  * Create Red Black Tree 
  189.  */
  190. rbtree RBTree::rbtree_create()
  191. {
  192.     rbtree t = new rbtree_t;
  193.     t->root = NULL;
  194.     verify_properties(t);
  195.     return t;
  196. }
  197.  
  198. /*
  199.  * Creating New Node of Reb Black Tree
  200.  */
  201. node RBTree::new_node(void* k, void* v, color n_color, node left, node right)
  202. {
  203.     node result = new rbtree_node;
  204.     result->key = k;
  205.     result->value = v;
  206.     result->color = n_color;
  207.     result->left = left;
  208.     result->right = right;
  209.     if (left  != NULL)
  210.         left->parent = result;
  211.     if (right != NULL)
  212.         right->parent = result;
  213.     result->parent = NULL;
  214.     return result;
  215. }
  216. /*
  217.  * Look Up through Node
  218.  */
  219. node RBTree::lookup_node(rbtree t, void* key, compare_func compare)
  220. {
  221.     node n = t->root;
  222.     while (n != NULL)
  223.     {
  224.         int comp_result = compare(key, n->key);
  225.         if (comp_result == 0)
  226.         {
  227.             return n;
  228.         }
  229.         else if (comp_result < 0)
  230.         {
  231.             n = n->left;
  232.         }
  233.         else
  234.         {
  235.             assert(comp_result > 0);
  236.             n = n->right;
  237.         }
  238.     }
  239.     return n;
  240. }
  241. /*
  242.  * RbTree Look Up
  243.  */
  244. void* RBTree::rbtree_lookup(rbtree t, void* key, compare_func compare)
  245. {
  246.     node n = lookup_node(t, key, compare);
  247.     return n == NULL ? NULL : n->value;
  248. }
  249.  
  250. /*
  251.  * Rotate left
  252.  */
  253. void RBTree::rotate_left(rbtree t, node n)
  254. {
  255.     node r = n->right;
  256.     replace_node(t, n, r);
  257.     n->right = r->left;
  258.     if (r->left != NULL)
  259.     {
  260.         r->left->parent = n;
  261.     }
  262.     r->left = n;
  263.     n->parent = r;
  264. }
  265. /*
  266.  * Rotate right
  267.  */
  268. void RBTree::rotate_right(rbtree t, node n)
  269. {
  270.     node L = n->left;
  271.     replace_node(t, n, L);
  272.     n->left = L->right;
  273.     if (L->right != NULL)
  274.     {
  275.         L->right->parent = n;
  276.     }
  277.     L->right = n;
  278.     n->parent = L;
  279. }
  280. /*
  281.  * Replace a node
  282.  */
  283. void RBTree::replace_node(rbtree t, node oldn, node newn)
  284. {
  285.     if (oldn->parent == NULL)
  286.     {
  287.         t->root = newn;
  288.     }
  289.     else
  290.     {
  291.         if (oldn == oldn->parent->left)
  292.             oldn->parent->left = newn;
  293.         else
  294.             oldn->parent->right = newn;
  295.     }
  296.     if (newn != NULL)
  297.     {
  298.         newn->parent = oldn->parent;
  299.     }
  300. }
  301. /*
  302.  * Insert node into RBTree
  303.  */
  304. void RBTree::rbtree_insert(rbtree t, void* key, void* value, compare_func compare)
  305. {
  306.     node inserted_node = new_node(key, value, RED, NULL, NULL);
  307.     if (t->root == NULL)
  308.     {
  309.         t->root = inserted_node;
  310.     }
  311.     else
  312.     {
  313.         node n = t->root;
  314.         while (1)
  315.         {
  316.             int comp_result = compare(key, n->key);
  317.             if (comp_result == 0)
  318.             {
  319.                 n->value = value;
  320.                 return;
  321.             }
  322.             else if (comp_result < 0)
  323.             {
  324.                 if (n->left == NULL)
  325.                 {
  326.                     n->left = inserted_node;
  327.                     break;
  328.                 }
  329.                 else
  330.                 {
  331.                     n = n->left;
  332.                 }
  333.             }
  334.             else
  335.             {
  336.                 assert (comp_result > 0);
  337.                 if (n->right == NULL)
  338.                 {
  339.                     n->right = inserted_node;
  340.                     break;
  341.                 }
  342.                 else
  343.                 {
  344.                     n = n->right;
  345.                 }
  346.             }
  347.         }
  348.         inserted_node->parent = n;
  349.     }
  350.     insert_case1(t, inserted_node);
  351.     verify_properties(t);
  352. }
  353.  
  354. /*
  355.  * Inserting Case 1
  356.  */
  357. void RBTree::insert_case1(rbtree t, node n)
  358. {
  359.     if (n->parent == NULL)
  360.         n->color = BLACK;
  361.     else
  362.         insert_case2(t, n);
  363. }
  364.  
  365. /*
  366.  * Inserting Case 2
  367.  */
  368. void RBTree::insert_case2(rbtree t, node n)
  369. {
  370.     if (node_color(n->parent) == BLACK)
  371.         return;
  372.     else
  373.         insert_case3(t, n);
  374. }
  375.  
  376. /*
  377.  * Inserting Case 3
  378.  */
  379. void RBTree::insert_case3(rbtree t, node n)
  380. {
  381.     if (node_color(uncle(n)) == RED)
  382.     {
  383.         n->parent->color = BLACK;
  384.         uncle(n)->color = BLACK;
  385.         grandparent(n)->color = RED;
  386.         insert_case1(t, grandparent(n));
  387.     }
  388.     else
  389.     {
  390.         insert_case4(t, n);
  391.     }
  392. }
  393.  
  394. /*
  395.  * Inserting Case 4
  396.  */
  397. void RBTree::insert_case4(rbtree t, node n)
  398. {
  399.     if (n == n->parent->right && n->parent == grandparent(n)->left)
  400.     {
  401.         rotate_left(t, n->parent);
  402.         n = n->left;
  403.     }
  404.     else if (n == n->parent->left && n->parent == grandparent(n)->right)
  405.     {
  406.         rotate_right(t, n->parent);
  407.         n = n->right;
  408.     }
  409.     insert_case5(t, n);
  410. }
  411.  
  412. /*
  413.  * Inserting Case 5
  414.  */
  415. void RBTree::insert_case5(rbtree t, node n)
  416. {
  417.     n->parent->color = BLACK;
  418.     grandparent(n)->color = RED;
  419.     if (n == n->parent->left && n->parent == grandparent(n)->left)
  420.     {
  421.         rotate_right(t, grandparent(n));
  422.     }
  423.     else
  424.     {
  425.         assert (n == n->parent->right && n->parent == grandparent(n)->right);
  426.         rotate_left(t, grandparent(n));
  427.     }
  428. }
  429.  
  430. /*
  431.  * Delete Node from RBTree
  432.  */
  433. void RBTree::rbtree_delete(rbtree t, void* key, compare_func compare)
  434. {
  435.     node child;
  436.     node n = lookup_node(t, key, compare);
  437.     if (n == NULL)
  438.         return;
  439.     if (n->left != NULL && n->right != NULL)
  440.     {
  441.         node pred = maximum_node(n->left);
  442.         n->key   = pred->key;
  443.         n->value = pred->value;
  444.         n = pred;
  445.     }
  446.     assert(n->left == NULL || n->right == NULL);
  447.     child = n->right == NULL ? n->left  : n->right;
  448.     if (node_color(n) == BLACK)
  449.     {
  450.         n->color = node_color(child);
  451.         delete_case1(t, n);
  452.     }
  453.     replace_node(t, n, child);
  454.     free(n);
  455.     verify_properties(t);
  456. }
  457.  
  458. /*
  459.  * Returns Maximum node
  460.  */
  461. node RBTree::maximum_node(node n)
  462. {
  463.     assert (n != NULL);
  464.     while (n->right != NULL)
  465.     {
  466.         n = n->right;
  467.     }
  468.     return n;
  469. }
  470.  
  471. /*
  472.  * Deleting Case 1
  473.  */
  474. void RBTree::delete_case1(rbtree t, node n)
  475. {
  476.     if (n->parent == NULL)
  477.         return;
  478.     else
  479.         delete_case2(t, n);
  480. }
  481.  
  482. /*
  483.  * Deleting Case 2
  484.  */
  485. void RBTree::delete_case2(rbtree t, node n)
  486. {
  487.     if (node_color(sibling(n)) == RED)
  488.     {
  489.         n->parent->color = RED;
  490.         sibling(n)->color = BLACK;
  491.         if (n == n->parent->left)
  492.             rotate_left(t, n->parent);
  493.         else
  494.             rotate_right(t, n->parent);
  495.     }
  496.     delete_case3(t, n);
  497. }
  498.  
  499. /*
  500.  * Deleting Case 3
  501.  */
  502. void RBTree::delete_case3(rbtree t, node n)
  503. {
  504.     if (node_color(n->parent) == BLACK && node_color(sibling(n)) == BLACK &&
  505.         node_color(sibling(n)->left) == BLACK && node_color(sibling(n)->right) == BLACK)
  506.     {
  507.         sibling(n)->color = RED;
  508.         delete_case1(t, n->parent);
  509.     }
  510.     else
  511.         delete_case4(t, n);
  512. }
  513.  
  514. /*
  515.  * Deleting Case 4
  516.  */
  517. void RBTree::delete_case4(rbtree t, node n)
  518. {
  519.     if (node_color(n->parent) == RED && node_color(sibling(n)) == BLACK &&
  520.         node_color(sibling(n)->left) == BLACK && node_color(sibling(n)->right) == BLACK)
  521.     {
  522.         sibling(n)->color = RED;
  523.         n->parent->color = BLACK;
  524.     }
  525.     else
  526.         delete_case5(t, n);
  527. }
  528.  
  529. /*
  530.  * Deleting Case 5
  531.  */
  532. void RBTree::delete_case5(rbtree t, node n)
  533. {
  534.     if (n == n->parent->left && node_color(sibling(n)) == BLACK &&
  535.         node_color(sibling(n)->left) == RED && node_color(sibling(n)->right) == BLACK)
  536.     {
  537.         sibling(n)->color = RED;
  538.         sibling(n)->left->color = BLACK;
  539.         rotate_right(t, sibling(n));
  540.     }
  541.     else if (n == n->parent->right && node_color(sibling(n)) == BLACK &&
  542.              node_color(sibling(n)->right) == RED && node_color(sibling(n)->left) == BLACK)
  543.     {
  544.         sibling(n)->color = RED;
  545.         sibling(n)->right->color = BLACK;
  546.         rotate_left(t, sibling(n));
  547.     }
  548.     delete_case6(t, n);
  549. }
  550.  
  551. /*
  552.  * Deleting Case 6
  553.  */
  554. void RBTree::delete_case6(rbtree t, node n)
  555. {
  556.     sibling(n)->color = node_color(n->parent);
  557.     n->parent->color = BLACK;
  558.     if (n == n->parent->left)
  559.     {
  560.         assert (node_color(sibling(n)->right) == RED);
  561.         sibling(n)->right->color = BLACK;
  562.         rotate_left(t, n->parent);
  563.     }
  564.     else
  565.     {
  566.         assert (node_color(sibling(n)->left) == RED);
  567.         sibling(n)->left->color = BLACK;
  568.         rotate_right(t, n->parent);
  569.     }
  570. }
  571.  
  572. /*
  573.  * Compare two nodes
  574.  */
  575. int compare_int(void* leftp, void* rightp)
  576. {
  577.     int left = (int)leftp;
  578.     int right = (int)rightp;
  579.     if (left < right)
  580.         return -1;
  581.     else if (left > right)
  582.         return 1;
  583.     else
  584.     {
  585.         assert (left == right);
  586.         return 0;
  587.     }
  588. }
  589. /*
  590.  * Print RBTRee
  591.  */
  592. void print_tree_helper(node n, int indent)
  593. {
  594.     int i;
  595.     if (n == NULL)
  596.     {
  597.         fputs("<empty tree>", stdout);
  598.         return;
  599.     }
  600.     if (n->right != NULL)
  601.     {
  602.         print_tree_helper(n->right, indent + INDENT_STEP);
  603.     }
  604.     for(i = 0; i < indent; i++)
  605.         fputs(" ", stdout);
  606.     if (n->color == BLACK)
  607.         cout<<(int)n->key<<endl;
  608.     else
  609.         cout<<"<"<<(int)n->key<<">"<<endl;
  610.     if (n->left != NULL)
  611.     {
  612.         print_tree_helper(n->left, indent + INDENT_STEP);
  613.     }
  614. }
  615.  
  616. void print_tree(rbtree t)
  617. {
  618.     print_tree_helper(t->root, 0);
  619.     puts("");
  620. }
  621.  
  622. /*
  623.  * Main Contains Menu
  624.  */
  625. int main()
  626. {
  627.     int i;
  628.     RBTree rbt;
  629.     rbtree t = rbt.rbtree_create();
  630.     for (i = 0; i < 12; i++)
  631.     {
  632.         int x = rand() % 10;
  633.         int y = rand() % 10;
  634.         print_tree(t);
  635.         cout<<"Inserting "<<x<<" -> "<<y<<endl<<endl;
  636.         rbt.rbtree_insert(t, (void*)x, (void*)y, compare_int);
  637.         assert(rbt.rbtree_lookup(t, (void*)x, compare_int) == (void*)y);
  638.     }
  639.     for (i = 0; i < 15; i++)
  640.     {
  641.         int x = rand() % 10;
  642.         print_tree(t);
  643.         cout<<"Deleting key "<<x<<endl<<endl;
  644.         rbt.rbtree_delete(t, (void*)x, compare_int);
  645.     }
  646.     return 0;
  647. }

advertisement
$ g++ rbtree.cpp
$ a.out
 
<empty tree>
Inserting 1 -> 7
 
1
 
Inserting 4 -> 0
 
    <4>
1
 
Inserting 9 -> 4
 
    <9>
4
    <1>
 
Inserting 8 -> 8
 
    9
        <8>
4
    1
 
Inserting 2 -> 4
 
    9
        <8>
4
        <2>
    1
 
Inserting 5 -> 5
 
        <9>
    8
        <5>
4
        <2>
    1
 
Inserting 1 -> 7
 
        <9>
    8
        <5>
4
        <2>
    1
 
Inserting 1 -> 1
 
        <9>
    8
        <5>
4
        <2>
    1
 
Inserting 5 -> 2
 
        <9>
    8
        <5>
4
        <2>
    1
 
Inserting 7 -> 6
 
        9
    <8>
            <7>
        5
4
        <2>
    1
 
Inserting 1 -> 4
 
        9
    <8>
            <7>
        5
4
        <2>
    1
 
Inserting 2 -> 3
 
        9
    <8>
            <7>
        5
4
        <2>
    1
 
Deleting key 2
 
        9
    <8>
            <7>
        5
4
    1
 
Deleting key 2
 
        9
    <8>
            <7>
        5
4
    1
 
Deleting key 1
 
    9
8
        7
    <5>
        4
 
Deleting key 6
 
    9
8
        7
    <5>
        4
 
Deleting key 8
 
    9
7
    5
        <4>
 
Deleting key 5
 
    <9>
7
    <4>
 
Deleting key 7
 
    <9>
4
 
Deleting key 6
 
    <9>
4
 
Deleting key 1
 
    <9>
4
 
Deleting key 8
 
    <9>
4
 
Deleting key 9
 
4
 
Deleting key 2
 
4
 
Deleting key 7
 
4
 
Deleting key 9
 
4
 
Deleting key 5
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn