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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.