From d703960951d838ce92687a4947581bc09a160f60 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Wed, 18 Jan 2023 12:46:40 +0100
Subject: Add

---
 Year_2/Algorithms/RB.cc | 61 ++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 50 insertions(+), 11 deletions(-)

(limited to 'Year_2/Algorithms/RB.cc')

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)
     {
@@ -177,24 +182,58 @@ public:
 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();
             }
         }
 
-- 
cgit v1.2.3-18-g5258