Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 15th, 2012  |  syntax: C++  |  size: 12.09 KB  |  hits: 20  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #pragma once
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstdlib>
  5. template <class KeyType, class T>
  6. class RBTree
  7. {
  8. private:
  9.         int _size;
  10.         class Node
  11.         {
  12.         public:
  13.                 KeyType key;
  14.                 T value;
  15.                 Node *Left, *Right, *Parent;
  16.                 bool color; // black = false
  17.         };
  18.         void rotateLeft (Node* x)
  19.                 {
  20.                         if (x->Right == NULL)
  21.                         {
  22.                                 return;
  23.                         }
  24.                         Node* y = x->Right;
  25.                         x->Right = y->Left;
  26.                         if (x->Right != NULL)
  27.                         {
  28.                                 x->Right->Parent = x;
  29.                         }
  30.                         y->Parent = x->Parent;
  31.                         if (x->Parent == NULL)
  32.                         {
  33.                                 Root = y;
  34.                         }
  35.                         else
  36.                         {
  37.                                 if (x == x->Parent->Left)
  38.                                 {
  39.                                         x->Parent->Left = y;
  40.                                 }
  41.                                 else
  42.                                 {
  43.                                         x->Parent->Right = y;
  44.                                 }
  45.                         }
  46.         y->Left = x;
  47.         x->Parent = y;
  48.     }
  49.     void rotateRight (Node* x)
  50.         {
  51.         if (x->Left == NULL) {
  52.             return;
  53.         }
  54.         Node* y = x->Left;
  55.         x->Left = y->Right;
  56.         if (x->Left != NULL) {
  57.             x->Left->Parent = x;
  58.         }
  59.         y->Parent = x->Parent;
  60.         if (x->Parent == NULL) {
  61.             Root = y;
  62.         }
  63.         else {
  64.             if (x == x->Parent->Left) {
  65.                 x->Parent->Left = y;
  66.             }
  67.             else {
  68.                 x->Parent->Right = y;
  69.             }
  70.         }
  71.         y->Right = x;
  72.         x->Parent = y;
  73.         }
  74.         void insertFixup(Node *x)
  75.         {
  76.                 while (x != Root && x->Parent->color == true)
  77.                 {
  78.                         if (x->Parent == x->Parent->Parent->Left)
  79.                         {
  80.                                 Node *y = NULL;
  81.                                 if (x->Parent->Parent->Right!=NULL)
  82.                                         y = x->Parent->Parent->Right;
  83.                                 if ((y!=NULL) && (y->color == true))
  84.                                 {
  85.                                         x->Parent->color = false;
  86.                                         y->color = false;
  87.                                         x->Parent->Parent->color = true;
  88.                                         x = x->Parent->Parent;
  89.                                 }
  90.                                 else
  91.                                 {
  92.                                         if (x == x->Parent->Right)
  93.                                         {
  94.                                                 x = x->Parent;
  95.                                                 rotateLeft(x);
  96.                                         }
  97.  
  98.                                         x->Parent->color = false;
  99.                                         x->Parent->Parent->color = true;
  100.                                         rotateRight(x->Parent->Parent);
  101.                                 }
  102.                         }
  103.                         else
  104.                         {
  105.                                 Node *y = NULL;
  106.                                 if (x->Parent->Parent->Left!=NULL)
  107.                                         y = x->Parent->Parent->Left;
  108.                                 //Node *y = x->Parent->Parent->Left;
  109.                                 if ((y!=NULL) && (y->color == true))
  110.                                 {
  111.  
  112.                                         x->Parent->color = false;
  113.                                         y->color = false;
  114.                                         x->Parent->Parent->color = true;
  115.                                         x = x->Parent->Parent;
  116.                                 }
  117.                                 else
  118.                                 {
  119.  
  120.                                         if (x == x->Parent->Left)
  121.                                         {
  122.                                                 x = x->Parent;
  123.                                                 rotateRight(x);
  124.                                         }
  125.                                         x->Parent->color = false;
  126.                                         x->Parent->Parent->color = true;
  127.                                         rotateLeft(x->Parent->Parent);
  128.                                 }
  129.                         }
  130.                 }
  131.                 Root->color = false;
  132.         }
  133.         void deleteFixup(Node *x)
  134.         {
  135.  
  136.                 while (x != Root && x->color == false)
  137.                 {
  138.                         if (x == x->Parent->Left)
  139.                         {
  140.                                 Node *w = x->Parent->Right;
  141.                                 if (w->color == true)
  142.                                 {
  143.                                         w->color = false;
  144.                                         x->Parent->color = true;
  145.                                         rotateLeft (x->Parent);
  146.                                         w = x->Parent->Right;
  147.                                 }
  148.                                 if (w->Left->color == false && w->Right->color == false)
  149.                                 {
  150.                                         w->color = true;
  151.                                         x = x->Parent;
  152.                                 }
  153.                                 else
  154.                                 {
  155.                                         if (w->Right->color == false)
  156.                                         {
  157.                                                 w->Left->color = false;
  158.                                                 w->color = true;
  159.                                                 rotateRight (w);
  160.                                                 w = x->Parent->Right;
  161.                                         }
  162.                                         w->color = x->Parent->color;
  163.                                         x->Parent->color = false;
  164.                                         w->Right->color = false;
  165.                                         rotateLeft (x->Parent);
  166.                                         x = Root;
  167.                                 }
  168.                         }
  169.                         else
  170.                         {
  171.                                 Node *w = x->Parent->Left;
  172.                                 if (w->color == true)
  173.                                 {
  174.                                         w->color = false;
  175.                                         x->Parent->color = true;
  176.                                         rotateRight (x->Parent);
  177.                                         w = x->Parent->Left;
  178.                                 }
  179.                                 if (w->Right->color == false && w->Left->color == false)
  180.                                 {
  181.                                         w->color = true;
  182.                                         x = x->Parent;
  183.                                 }
  184.                                 else
  185.                                 {
  186.                                         if (w->Left->color == false)
  187.                                         {
  188.                                                 w->Right->color = false;
  189.                                                 w->color = true;
  190.                                                 rotateLeft (w);
  191.                                                 w = x->Parent->Left;
  192.                                         }
  193.                                         w->color = x->Parent->color;
  194.                                         x->Parent->color = false;
  195.                                         w->Left->color = false;
  196.                                         rotateRight (x->Parent);
  197.                                         x = Root;
  198.                                 }
  199.                         }
  200.                 }
  201.                 x->color = false;
  202.         }
  203.         Node *findNode(KeyType key)
  204.         {
  205.                 Node *current = Root;
  206.                 while(current != NULL)
  207.                         if(key == current->key)
  208.                                 return (current);
  209.                         else
  210.                                 current = (key < current->key) ?
  211.                                         current->Left : current->Right;
  212.                 return(0);
  213.         }
  214. public:
  215.         class Iterator
  216.         {
  217.         friend class RBTree;
  218.         private:
  219.                 Node* node;
  220.                 RBTree* t;
  221.         public:
  222.                 bool isEnd;
  223.                 bool isBeg;
  224.                 Iterator(Node* a=NULL)
  225.                 {
  226.                        
  227.                         node = a;
  228.                         t = NULL;
  229.                         isEnd = false;
  230.                         isBeg = false;
  231.                 }
  232.                 void inc()
  233.                 {
  234.                         if (node->Right!=NULL)
  235.                         {
  236.                 node = node->Right;
  237.                 while (node->Left!=NULL)
  238.                                 {
  239.                     node = node->Left;
  240.                 }
  241.             }
  242.             else
  243.                         {
  244.                                         while (node!=NULL && node->Parent!=NULL && node == node->Parent->Right)
  245.                                         {
  246.                                                 node = node->Parent;
  247.                                         }
  248.                                         if (node->Parent!=NULL)
  249.                                                 node = node->Parent;
  250.                                         else
  251.                                         {
  252.                                                 node = NULL;
  253.                                                 isEnd = true;
  254.                                                 return ;
  255.                                         }
  256.             }
  257.                         value() = node->value;
  258.         }
  259.                 void dec()
  260.                 {
  261.                         if (isEnd)
  262.                         {
  263.                                 node = t->Root;
  264.                                 while (node->Right!=NULL)
  265.                                         node = node->Right;
  266.                                 isEnd = false;
  267.                                 value() = node->value;
  268.                         }
  269.                         else
  270.                         {
  271.                                 if (node->Left!=NULL)
  272.                                 {
  273.                                         node = node->Left;
  274.                                         while (node->Right!=NULL)
  275.                                         {
  276.                                                 node = node->Right;
  277.                                         }
  278.                                 }
  279.                                 else
  280.                                 {
  281.                                         if (node==node->Parent->Right)
  282.                                         {
  283.                                                 node = node->Parent;
  284.                                         }
  285.                                         else
  286.                                         {
  287.                                                 if (node->Parent->Parent!=NULL && node->Parent->Parent->Right==node->Parent)
  288.                                                 {
  289.                                                         node = node->Parent;
  290.                                                         while(node!=NULL && node->Parent!=NULL && node == node->Parent->Right)
  291.                                                                 node = node->Parent;
  292.                                                 }
  293.                                                 else
  294.                                                 if (node->Parent!=NULL)
  295.                                                 {
  296.                                                         node = NULL;
  297.                                                         isBeg = true;
  298.                                                         return ;
  299.                                                 }
  300.                                         }
  301.                                 }
  302.                                 value() = node->value;
  303.                                 //key() = node->key;
  304.                         }
  305.                         }
  306.                 const KeyType& key() const
  307.                 {
  308.                         return node->key;
  309.                 }
  310.                 T& value()
  311.                 {
  312.                         return node->value;
  313.                 }
  314.                 bool operator==(Iterator& a)
  315.                 {
  316.                         if ((a.isEnd) && (isEnd))
  317.                                 return true;
  318.                         else
  319.                         {
  320.                                 if ((a.isEnd) && !(isEnd))
  321.                                 {
  322.                                         return false;
  323.                                 }
  324.                                 else
  325.                                 {
  326.                                         if (!(a.isEnd) && (isEnd))
  327.                                                 return false;
  328.                                         else
  329.                                                 return (key() == a.key());
  330.                                 }
  331.                         }
  332.                 }
  333.                 bool operator!=(Iterator& a)
  334.                 {
  335.                         if ((a.isEnd) && (isEnd))
  336.                                 return false;
  337.                         else
  338.                         {
  339.                                 if ((a.isEnd) && !(isEnd))
  340.                                 {
  341.                                         return true;
  342.                                 }
  343.                                 else
  344.                                 {
  345.                                         if (!(a.isEnd) && (isEnd))
  346.                                                 return true;
  347.                                         else
  348.                                                 return (key() != a.key());
  349.                                 }
  350.                         }
  351.                 }
  352.         };
  353.  
  354.         class constIterator
  355.                 {
  356.         friend class RBTree;
  357.         private:
  358.                 Node* node;
  359.                 const RBTree* t;
  360.         public:
  361.                 bool isEnd;
  362.                 bool isBeg;
  363.                 constIterator(Node* a=NULL)
  364.                 {
  365.                         node = a;
  366.                         t = NULL;
  367.                         isEnd = false;
  368.                         isBeg = false;
  369.                 }
  370.                 void inc()
  371.                 {
  372.                         if (node->Right!=NULL)
  373.                         {
  374.                 node = node->Right;
  375.                 while (node->Left!=NULL)
  376.                                 {
  377.                     node = node->Left;
  378.                 }
  379.             }
  380.             else
  381.                         {
  382.                                         while (node!=NULL && node->Parent!=NULL && node == node->Parent->Right)
  383.                                         {
  384.                                                 node = node->Parent;
  385.                                         }
  386.                                         if (node->Parent!=NULL)
  387.                                                 node = node->Parent;
  388.                                         else
  389.                                         {
  390.                                                 node = NULL;
  391.                                                 isEnd = true;
  392.                                                 return ;
  393.                                         }
  394.             }
  395.                         //value() = node->value;
  396.         }
  397.                 void dec()
  398.                 {
  399.                         if (isEnd)
  400.                         {
  401.                                 node = t->Root;
  402.                                 while (node->Right!=NULL)
  403.                                         node = node->Right;
  404.                                 isEnd = false;
  405.                                 value() = node->value;
  406.                         }
  407.                         else
  408.                         {
  409.                                 if (node->Left!=NULL)
  410.                                 {
  411.                                         node = node->Left;
  412.                                         while (node->Right!=NULL)
  413.                                         {
  414.                                                 node = node->Right;
  415.                                         }
  416.                                 }
  417.                                 else
  418.                                 {
  419.                                         if (node==node->Parent->Right)
  420.                                         {
  421.                                                 node = node->Parent;
  422.                                         }
  423.                                         else
  424.                                         {
  425.                                                 if (node->Parent->Parent!=NULL && node->Parent->Parent->Right==node->Parent)
  426.                                                 {
  427.                                                         node = node->Parent;
  428.                                                         while(node!=NULL && node->Parent!=NULL && node == node->Parent->Right)
  429.                                                                 node = node->Parent;
  430.                                                 }
  431.                                                 else
  432.                                                 if (node->Parent!=NULL)
  433.                                                 {
  434.                                                         node = NULL;
  435.                                                         isBeg = true;
  436.                                                         return ;
  437.                                                 }
  438.                                         }
  439.                                 }
  440.                                 value() = node->value;
  441.                                 //key() = node->key;
  442.                         }
  443.                         }
  444.                 const KeyType& key() const
  445.                 {
  446.                         return node->key;
  447.                 }
  448.                 const T& value() const
  449.                 {
  450.                         return node->value;
  451.                 }
  452.                 bool operator==(constIterator& a)
  453.                 {
  454.                         if ((a.isEnd) && (isEnd))
  455.                                 return true;
  456.                         else
  457.                         {
  458.                                 if ((a.isEnd) && !(isEnd))
  459.                                 {
  460.                                         return false;
  461.                                 }
  462.                                 else
  463.                                 {
  464.                                         if (!(a.isEnd) && (isEnd))
  465.                                                 return false;
  466.                                         else
  467.                                                 return (key() == a.key());
  468.                                 }
  469.                         }
  470.                 }
  471.                 bool operator!=(constIterator& a)
  472.                 {
  473.                         if ((a.isEnd) && (isEnd))
  474.                                 return false;
  475.                         else
  476.                         {
  477.                                 if ((a.isEnd) && !(isEnd))
  478.                                 {
  479.                                         return true;
  480.                                 }
  481.                                 else
  482.                                 {
  483.                                         if (!(a.isEnd) && (isEnd))
  484.                                                 return true;
  485.                                         else
  486.                                                 return (key() != a.key());
  487.                                 }
  488.                         }
  489.                 }
  490.         };
  491.         Node* Root;
  492.         void erase(Iterator it)
  493.         {
  494.                 Node* t;
  495.                 t = findNode(it.key());
  496.                 if (t!=NULL)
  497.                         deleteNode(t);
  498.         }
  499.         int count(KeyType k) const
  500.         {
  501.                 if (findNode(k)==NULL)
  502.                         return 0;
  503.                 else
  504.                         return 1;
  505.         }
  506.         int size() const
  507.         {
  508.                 return _size;
  509.         }
  510.         bool empty() const
  511.         {
  512.                 return (_size==0);
  513.         }
  514.         Iterator begin()
  515.         {
  516.                 Node* tmp = Root;
  517.                 if (tmp==NULL)
  518.                 {
  519.                         Iterator x(tmp);
  520.                         x.isEnd = true;
  521.                         x.t = this;
  522.                         return x;
  523.                 }
  524.                 while (tmp->Left!=NULL)
  525.                         tmp = tmp->Left;
  526.                 Iterator x(tmp);
  527.                 x.value() = tmp->value;
  528.                 x.t = this;
  529.                 return x;
  530.         }
  531.         Iterator end()
  532.         {
  533.                 Node* tmp =NULL;
  534.                 Iterator x(tmp);
  535.                 x.isEnd = true;
  536.                 return x;
  537.         }
  538.         constIterator begin() const
  539.                 {
  540.                         Node* tmp = this->Root;
  541.                         if (tmp==NULL)
  542.                         {
  543.                                 constIterator x(tmp);
  544.                                 x.isEnd = true;
  545.                                 x.t = this;
  546.                                 return x;
  547.                         }
  548.                         while (tmp->Left!=NULL)
  549.                                 tmp = tmp->Left;
  550.                         constIterator x(tmp);
  551.                         //x.value() = tmp->value;
  552.                         x.t = this;
  553.                         return x;
  554.         }
  555.         constIterator end() const
  556.         {
  557.                 Node* tmp =NULL;
  558.                 constIterator x(tmp);
  559.                 x.isEnd = true;
  560.                 return x;
  561.         }
  562.         Iterator rbegin()
  563.         {
  564.                 Node* tmp = Root;
  565.                 while (tmp->Right!=NULL)
  566.                         tmp = tmp->Right;
  567.                 Iterator x(tmp);
  568.                 x.value = tmp->value;
  569.                 return x;
  570.         }
  571.         Iterator rend()
  572.         {
  573.                 Node* tmp = NULL;
  574.                 Iterator x(tmp);
  575.                 x.isBeg = true;
  576.                 return x;
  577.         }
  578.         Iterator find(KeyType key)
  579.         {
  580.                 Node* t = findNode(key);
  581.                 if (t==NULL)
  582.                 {
  583.                         Iterator x(t);
  584.                         x.isEnd = true;
  585.                         return x;
  586.                 }
  587.                 else
  588.                 {
  589.                         Iterator x(t);
  590.                         return x;
  591.                 }
  592.         }
  593.         T& operator[](KeyType key)
  594.         {
  595.                 Node* t;
  596.                 if ((t=findNode(key))!=NULL)
  597.                         return t->value;
  598.                 else
  599.                 {
  600.                         return (insertNode(key, T()))->value;
  601.                 }
  602.         }
  603.         RBTree()
  604.         {
  605.                 _size = 0;
  606.                 Root = NULL;
  607.         }
  608.         Node *insertNode(KeyType key, T value)
  609.         {
  610.                 Node* f;
  611.                 if ((f=findNode(key))!=NULL)
  612.                         return f;
  613.                 Node *current, *Parent, *x;
  614.                 current = Root;
  615.                 Parent = 0;
  616.                 while (current != NULL)
  617.                 {
  618.                         if (key == current->key)
  619.                                 return (current);
  620.                         Parent = current;
  621.                         current = (key< current->key) ?
  622.                                 current->Left : current->Right;
  623.                 }
  624.                 x = new RBTree<KeyType, T>::Node;
  625.                 _size++;
  626.                 x->value = value;
  627.                 x->key = key;
  628.                 x->Parent = Parent;
  629.                 x->Left = NULL;
  630.                 x->Right = NULL;
  631.                 x->color = true;
  632.                 if(Parent!=NULL)
  633.                 {
  634.                         if(key<Parent->key)
  635.                                 Parent->Left = x;
  636.                         else
  637.                                 Parent->Right = x;
  638.                 }
  639.                 else
  640.                 {
  641.                         Root = x;
  642.                 }
  643.                 insertFixup(x);
  644.                 return(x);
  645.         }
  646.         void deleteNode(Node *z)
  647.         {
  648.                 Node *x, *y;
  649.  
  650.                 if (z == NULL)
  651.                         return;
  652.                 if (z->Left == NULL || z->Right == NULL)
  653.                 {
  654.  
  655.                         y = z;
  656.                 }
  657.                 else
  658.                 {
  659.                         y = z->Right;
  660.                         while (y->Left != NULL) y = y->Left;
  661.                 }
  662.                 if (y->Left != NULL)
  663.                         x = y->Left;
  664.                 else
  665.                         x = y->Right;
  666.  
  667.                 if (x!=NULL)
  668.                         x->Parent = y->Parent;
  669.                 if (y->Parent!=NULL)
  670.                         if (y == y->Parent->Left)
  671.                                 y->Parent->Left = x;
  672.                         else
  673.                                 y->Parent->Right = x;
  674.                 else
  675.                         Root = x;
  676.  
  677.                 if (y != z)
  678.                 {
  679.                         z->value = y->value;
  680.                         x->key = y->key;
  681.                 }
  682.                 if ((y->color == false) && (x!=NULL))
  683.                         deleteFixup (x);
  684.                 _size--;
  685.                 delete y;
  686.         }
  687.         ~RBTree()
  688.         {
  689.                 for (Iterator it = begin(); it!=end();)
  690.                 {
  691.                         KeyType k = it.key();
  692.                         Node* t = findNode(k);
  693.                         it.inc();
  694.                         deleteNode(t);
  695.                 }
  696.         }
  697. };
create a new version of this paste RAW Paste Data