Add

1 files changed, 50 insertions, 11 deletions

diff --git a/Year_2/Algorithms/RB.cc b/Year_2/Algorithms/RB.cc
index 9569fe0..eac3f07 100644
--- a/Year_2/Algorithms/RB.cc
+++ b/Year_2/Algorithms/RB.cc
@@ -97,6 +97,11 @@ public:
     {
     }
 
+    ~RBtree()
+    {
+        destructor(root_);
+    }
+
     RBtree<H>*
     insert(H key)
     {
@@ -178,23 +183,57 @@ private:
     Node<H>* root_ { nullptr };
 
     Node<H>*
+    minimum(Node<H>* x)
+    {
+        if (!x)
+            return x;
+
+        while (x->left())
+            x = x->left();
+
+        return x;
+    }
+
+    Node<H>*
+    successor(Node<H>* x)
+    {
+        if (!x)
+            return x;
+
+        if (x->right()) {
+            return minimum(x->right());
+        }
+
+        auto y = x->parent();
+        while (y && x == y->right()) {
+            x = y;
+            y = y->parent();
+        }
+
+        return y;
+    }
+
+    void
+    destructor(Node<H>* x)
+    {
+        if (!x)
+            return;
+
+        destructor(x->left());
+        destructor(x->right());
+        delete x;
+    }
+
+    Node<H>*
     search(H key)
     {
         auto t = this->root();
 
-        while (t != nullptr && key != t->key()) {
+        while (t && key != t->key()) {
             if (key < t->key()) {
-                if (t->left()) {
-                    t = t->left();
-                } else {
-                    break;
-                }
+                t = t->left();
             } else {
-                if (t->right()) {
-                    t = t->right();
-                } else {
-                    break;
-                }
+                t = t->right();
             }
         }