codebin.org

Untitled

From Gray Peccary, 1 Year ago, written in C++, viewed 248 times.
URL http://codebin.org/view/71d27e43 Embed
Download Paste or View Raw
  1. // Implementing Red-Black Tree in C++
  2.  
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. struct Node {
  7.   int data;
  8.   Node *parent;
  9.   Node *left;
  10.   Node *right;
  11.   int color;
  12. };
  13.  
  14. typedef Node *NodePtr;
  15.  
  16. class RedBlackTree {
  17.    private:
  18.   NodePtr root;
  19.   NodePtr TNULL;
  20.  
  21.   void initializeNULLNode(NodePtr node, NodePtr parent) {
  22.     node->data = 0;
  23.     node->parent = parent;
  24.     node->left = nullptr;
  25.     node->right = nullptr;
  26.     node->color = 0;
  27.   }
  28.  
  29.   // Preorder
  30.   void preOrderHelper(NodePtr node) {
  31.     if (node != TNULL) {
  32.       cout << node->data << " ";
  33.       preOrderHelper(node->left);
  34.       preOrderHelper(node->right);
  35.     }
  36.   }
  37.  
  38.   // Inorder
  39.   void inOrderHelper(NodePtr node) {
  40.     if (node != TNULL) {
  41.       inOrderHelper(node->left);
  42.       cout << node->data << " ";
  43.       inOrderHelper(node->right);
  44.     }
  45.   }
  46.  
  47.   // Post order
  48.   void postOrderHelper(NodePtr node) {
  49.     if (node != TNULL) {
  50.       postOrderHelper(node->left);
  51.       postOrderHelper(node->right);
  52.       cout << node->data << " ";
  53.     }
  54.   }
  55.  
  56.   NodePtr searchTreeHelper(NodePtr node, int key) {
  57.     if (node == TNULL || key == node->data) {
  58.       return node;
  59.     }
  60.  
  61.     if (key < node->data) {
  62.       return searchTreeHelper(node->left, key);
  63.     }
  64.     return searchTreeHelper(node->right, key);
  65.   }
  66.  
  67.   // For balancing the tree after deletion
  68.   void deleteFix(NodePtr x) {
  69.     NodePtr s;
  70.     while (x != root && x->color == 0) {
  71.       if (x == x->parent->left) {
  72.         s = x->parent->right;
  73.         if (s->color == 1) {
  74.           s->color = 0;
  75.           x->parent->color = 1;
  76.           leftRotate(x->parent);
  77.           s = x->parent->right;
  78.         }
  79.  
  80.         if (s->left->color == 0 && s->right->color == 0) {
  81.           s->color = 1;
  82.           x = x->parent;
  83.         } else {
  84.           if (s->right->color == 0) {
  85.             s->left->color = 0;
  86.             s->color = 1;
  87.             rightRotate(s);
  88.             s = x->parent->right;
  89.           }
  90.  
  91.           s->color = x->parent->color;
  92.           x->parent->color = 0;
  93.           s->right->color = 0;
  94.           leftRotate(x->parent);
  95.           x = root;
  96.         }
  97.       } else {
  98.         s = x->parent->left;
  99.         if (s->color == 1) {
  100.           s->color = 0;
  101.           x->parent->color = 1;
  102.           rightRotate(x->parent);
  103.           s = x->parent->left;
  104.         }
  105.  
  106.         if (s->right->color == 0 && s->right->color == 0) {
  107.           s->color = 1;
  108.           x = x->parent;
  109.         } else {
  110.           if (s->left->color == 0) {
  111.             s->right->color = 0;
  112.             s->color = 1;
  113.             leftRotate(s);
  114.             s = x->parent->left;
  115.           }
  116.  
  117.           s->color = x->parent->color;
  118.           x->parent->color = 0;
  119.           s->left->color = 0;
  120.           rightRotate(x->parent);
  121.           x = root;
  122.         }
  123.       }
  124.     }
  125.     x->color = 0;
  126.   }
  127.  
  128.   void rbTransplant(NodePtr u, NodePtr v) {
  129.     if (u->parent == nullptr) {
  130.       root = v;
  131.     } else if (u == u->parent->left) {
  132.       u->parent->left = v;
  133.     } else {
  134.       u->parent->right = v;
  135.     }
  136.     v->parent = u->parent;
  137.   }
  138.  
  139.   void deleteNodeHelper(NodePtr node, int key) {
  140.     NodePtr z = TNULL;
  141.     NodePtr x, y;
  142.     while (node != TNULL) {
  143.       if (node->data == key) {
  144.         z = node;
  145.       }
  146.  
  147.       if (node->data <= key) {
  148.         node = node->right;
  149.       } else {
  150.         node = node->left;
  151.       }
  152.     }
  153.  
  154.     if (z == TNULL) {
  155.       cout << "Key not found in the tree" << endl;
  156.       return;
  157.     }
  158.  
  159.     y = z;
  160.     int y_original_color = y->color;
  161.     if (z->left == TNULL) {
  162.       x = z->right;
  163.       rbTransplant(z, z->right);
  164.     } else if (z->right == TNULL) {
  165.       x = z->left;
  166.       rbTransplant(z, z->left);
  167.     } else {
  168.       y = minimum(z->right);
  169.       y_original_color = y->color;
  170.       x = y->right;
  171.       if (y->parent == z) {
  172.         x->parent = y;
  173.       } else {
  174.         rbTransplant(y, y->right);
  175.         y->right = z->right;
  176.         y->right->parent = y;
  177.       }
  178.  
  179.       rbTransplant(z, y);
  180.       y->left = z->left;
  181.       y->left->parent = y;
  182.       y->color = z->color;
  183.     }
  184.     delete z;
  185.     if (y_original_color == 0) {
  186.       deleteFix(x);
  187.     }
  188.   }
  189.  
  190.   // For balancing the tree after insertion
  191.   void insertFix(NodePtr k) {
  192.     NodePtr u;
  193.     while (k->parent->color == 1) {
  194.       if (k->parent == k->parent->parent->right) {
  195.         u = k->parent->parent->left;
  196.         if (u->color == 1) {
  197.           u->color = 0;
  198.           k->parent->color = 0;
  199.           k->parent->parent->color = 1;
  200.           k = k->parent->parent;
  201.         } else {
  202.           if (k == k->parent->left) {
  203.             k = k->parent;
  204.             rightRotate(k);
  205.           }
  206.           k->parent->color = 0;
  207.           k->parent->parent->color = 1;
  208.           leftRotate(k->parent->parent);
  209.         }
  210.       } else {
  211.         u = k->parent->parent->right;
  212.  
  213.         if (u->color == 1) {
  214.           u->color = 0;
  215.           k->parent->color = 0;
  216.           k->parent->parent->color = 1;
  217.           k = k->parent->parent;
  218.         } else {
  219.           if (k == k->parent->right) {
  220.             k = k->parent;
  221.             leftRotate(k);
  222.           }
  223.           k->parent->color = 0;
  224.           k->parent->parent->color = 1;
  225.           rightRotate(k->parent->parent);
  226.         }
  227.       }
  228.       if (k == root) {
  229.         break;
  230.       }
  231.     }
  232.     root->color = 0;
  233.   }
  234.  
  235.   void printHelper(NodePtr root, string indent, bool last) {
  236.     if (root != TNULL) {
  237.       cout << indent;
  238.       if (last) {
  239.         cout << "R----";
  240.         indent += "   ";
  241.       } else {
  242.         cout << "L----";
  243.         indent += "|  ";
  244.       }
  245.  
  246.       string sColor = root->color ? "RED" : "BLACK";
  247.       cout << root->data << "(" << sColor << ")" << endl;
  248.       printHelper(root->left, indent, false);
  249.       printHelper(root->right, indent, true);
  250.     }
  251.   }
  252.  
  253.    public:
  254.   RedBlackTree() {
  255.     TNULL = new Node;
  256.     TNULL->color = 0;
  257.     TNULL->left = nullptr;
  258.     TNULL->right = nullptr;
  259.     root = TNULL;
  260.   }
  261.  
  262.   void preorder() {
  263.     preOrderHelper(this->root);
  264.   }
  265.  
  266.   void inorder() {
  267.     inOrderHelper(this->root);
  268.   }
  269.  
  270.   void postorder() {
  271.     postOrderHelper(this->root);
  272.   }
  273.  
  274.   NodePtr searchTree(int k) {
  275.     return searchTreeHelper(this->root, k);
  276.   }
  277.  
  278.   NodePtr minimum(NodePtr node) {
  279.     while (node->left != TNULL) {
  280.       node = node->left;
  281.     }
  282.     return node;
  283.   }
  284.  
  285.   NodePtr maximum(NodePtr node) {
  286.     while (node->right != TNULL) {
  287.       node = node->right;
  288.     }
  289.     return node;
  290.   }
  291.  
  292.   NodePtr successor(NodePtr x) {
  293.     if (x->right != TNULL) {
  294.       return minimum(x->right);
  295.     }
  296.  
  297.     NodePtr y = x->parent;
  298.     while (y != TNULL && x == y->right) {
  299.       x = y;
  300.       y = y->parent;
  301.     }
  302.     return y;
  303.   }
  304.  
  305.   NodePtr predecessor(NodePtr x) {
  306.     if (x->left != TNULL) {
  307.       return maximum(x->left);
  308.     }
  309.  
  310.     NodePtr y = x->parent;
  311.     while (y != TNULL && x == y->left) {
  312.       x = y;
  313.       y = y->parent;
  314.     }
  315.  
  316.     return y;
  317.   }
  318.  
  319.   void leftRotate(NodePtr x) {
  320.     NodePtr y = x->right;
  321.     x->right = y->left;
  322.     if (y->left != TNULL) {
  323.       y->left->parent = x;
  324.     }
  325.     y->parent = x->parent;
  326.     if (x->parent == nullptr) {
  327.       this->root = y;
  328.     } else if (x == x->parent->left) {
  329.       x->parent->left = y;
  330.     } else {
  331.       x->parent->right = y;
  332.     }
  333.     y->left = x;
  334.     x->parent = y;
  335.   }
  336.  
  337.   void rightRotate(NodePtr x) {
  338.     NodePtr y = x->left;
  339.     x->left = y->right;
  340.     if (y->right != TNULL) {
  341.       y->right->parent = x;
  342.     }
  343.     y->parent = x->parent;
  344.     if (x->parent == nullptr) {
  345.       this->root = y;
  346.     } else if (x == x->parent->right) {
  347.       x->parent->right = y;
  348.     } else {
  349.       x->parent->left = y;
  350.     }
  351.     y->right = x;
  352.     x->parent = y;
  353.   }
  354.  
  355.   // Inserting a node
  356.   void insert(int key) {
  357.     NodePtr node = new Node;
  358.     node->parent = nullptr;
  359.     node->data = key;
  360.     node->left = TNULL;
  361.     node->right = TNULL;
  362.     node->color = 1;
  363.  
  364.     NodePtr y = nullptr;
  365.     NodePtr x = this->root;
  366.  
  367.     while (x != TNULL) {
  368.       y = x;
  369.       if (node->data < x->data) {
  370.         x = x->left;
  371.       } else {
  372.         x = x->right;
  373.       }
  374.     }
  375.  
  376.     node->parent = y;
  377.     if (y == nullptr) {
  378.       root = node;
  379.     } else if (node->data < y->data) {
  380.       y->left = node;
  381.     } else {
  382.       y->right = node;
  383.     }
  384.  
  385.     if (node->parent == nullptr) {
  386.       node->color = 0;
  387.       return;
  388.     }
  389.  
  390.     if (node->parent->parent == nullptr) {
  391.       return;
  392.     }
  393.  
  394.     insertFix(node);
  395.   }
  396.  
  397.   NodePtr getRoot() {
  398.     return this->root;
  399.   }
  400.  
  401.   void deleteNode(int data) {
  402.     deleteNodeHelper(this->root, data);
  403.   }
  404.  
  405.   void printTree() {
  406.     if (root) {
  407.       printHelper(this->root, "", true);
  408.     }
  409.   }
  410. };
  411.  
  412. int main() {
  413.   RedBlackTree bst;
  414.   bst.insert(55);
  415.   bst.insert(40);
  416.   bst.insert(65);
  417.   bst.insert(60);
  418.   bst.insert(75);
  419.   bst.insert(57);
  420.  
  421.   bst.printTree();
  422.   cout << endl
  423.      << "After deleting" << endl;
  424.   bst.deleteNode(40);
  425.   bst.printTree();
  426. }

Reply to "Untitled"

Here you can reply to the paste above

codebin 2012-∞ | can't stop won't stop