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 +++++--
Year_2/Algorithms/altezza-RBTree.cc | 305 ++++++++++++++++++++++++++++++++
Year_2/Algorithms/insert-RBtree.cc | 335 ++++++++++++++++++++++++++++++++++++
3 files changed, 690 insertions(+), 11 deletions(-)
create mode 100644 Year_2/Algorithms/altezza-RBTree.cc
create mode 100644 Year_2/Algorithms/insert-RBtree.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();
}
}
diff --git a/Year_2/Algorithms/altezza-RBTree.cc b/Year_2/Algorithms/altezza-RBTree.cc
new file mode 100644
index 0000000..ed03aec
--- /dev/null
+++ b/Year_2/Algorithms/altezza-RBTree.cc
@@ -0,0 +1,305 @@
+#include <fstream>
+#include <iostream>
+
+using namespace std;
+
+enum class Color {
+ Red,
+ Black
+};
+
+template <typename H>
+class Node {
+public:
+ Node(Color color, H key, Node<H>* parent = nullptr, Node<H>* left = nullptr, Node<H>* right = nullptr)
+ : color_ { color }
+ , key_ { key }
+ , parent_ { parent }
+ , left_ { left }
+ , right_ { right }
+ {
+ }
+
+ const H&
+ key() const
+ {
+ return key_;
+ }
+
+ const Color&
+ color() const
+ {
+ return color_;
+ }
+ Color&
+ color()
+ {
+ return color_;
+ }
+
+ const Node<H>*&
+ parent() const
+ {
+ return parent_;
+ }
+ Node<H>*&
+ parent()
+ {
+ return parent_;
+ }
+
+ const Node<H>*&
+ grandp() const
+ {
+ return parent_->parent();
+ }
+ Node<H>*&
+ grandp()
+ {
+ return parent_->parent();
+ }
+
+ const Node<H>*&
+ left() const
+ {
+ return left_;
+ }
+ Node<H>*&
+ left()
+ {
+ return left_;
+ }
+
+ const Node<H>*&
+ right() const
+ {
+ return right_;
+ }
+ Node<H>*&
+ right()
+ {
+ return right_;
+ }
+
+private:
+ Color color_;
+ H key_;
+ Node<H>* parent_ { nullptr };
+ Node<H>* left_ { nullptr };
+ Node<H>* right_ { nullptr };
+};
+
+template <typename H>
+class RBtree {
+public:
+ RBtree(Node<H>* root = nullptr)
+ : root_ { root }
+ {
+ }
+
+ ~RBtree()
+ {
+ destructor(root_);
+ }
+
+ RBtree<H>*
+ insert(H key)
+ {
+ Node<H>* z = new Node<H>(Color::Red, key);
+
+ Node<H>* y = nullptr;
+ auto x = root_;
+
+ while (x != nullptr) {
+ y = x;
+ if (z->key() < x->key())
+ x = x->left();
+ else
+ x = x->right();
+ }
+
+ z->parent() = y;
+
+ if (y == nullptr) {
+ root_ = z;
+ } else if (z->key() < y->key()) {
+ y->left() = z;
+ } else {
+ y->right() = z;
+ }
+
+ if (!z->parent()) {
+ z->color() = Color::Black;
+ } else if (z->parent()->parent()) {
+ fixup(z);
+ }
+
+ return this;
+ }
+
+ Node<H>*
+ root()
+ {
+ return root_;
+ }
+
+ unsigned long
+ bh(Node<H>* x)
+ {
+ if (!x)
+ return 0;
+
+ return 1 + max(bh(x->left()), bh(x->right()));
+ }
+
+private:
+ Node<H>* root_ { nullptr };
+
+ 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 && key != t->key()) {
+ if (key < t->key()) {
+ t = t->left();
+ } else {
+ t = t->right();
+ }
+ }
+
+ return t;
+ }
+
+ void
+ fixup(Node<H>* z)
+ {
+ while (z->parent()->color() == Color::Red) {
+ if (z->grandp()->right() == z->parent()) {
+ auto y = z->grandp()->left();
+ if (y && y->color() == Color::Red) {
+ z->parent()->color() = Color::Black;
+ y->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ z = z->grandp();
+ } else {
+ if (z == z->parent()->left()) {
+ z = z->parent();
+ rrotate(z);
+ }
+ z->parent()->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ lrotate(z->grandp());
+ }
+ } else {
+ auto y = z->grandp()->right();
+ if (y && y->color() == Color::Red) {
+ z->parent()->color() = Color::Black;
+ y->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ z = z->grandp();
+ } else {
+ if (z == z->parent()->right()) {
+ z = z->parent();
+ lrotate(z);
+ }
+ z->parent()->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ rrotate(z->grandp());
+ }
+ }
+
+ if (z == root_)
+ break;
+ }
+
+ root_->color() = Color::Black;
+ }
+
+ void
+ lrotate(Node<H>* node)
+ {
+ auto y = node->right();
+ node->right() = y->left();
+ if (y->left())
+ y->left()->parent() = node;
+ y->parent() = node->parent();
+
+ if (!node->parent())
+ root_ = y;
+ else if (node == node->parent()->left())
+ node->parent()->left() = y;
+ else
+ node->parent()->right() = y;
+
+ y->left() = node;
+ node->parent() = y;
+ }
+
+ void
+ rrotate(Node<H>* node)
+ {
+ auto y = node->left();
+ node->left() = y->right();
+ if (y->right())
+ y->right()->parent() = node;
+ y->parent() = node->parent();
+
+ if (!node->parent())
+ root_ = y;
+ else if (node == node->parent()->right())
+ node->parent()->right() = y;
+ else
+ node->parent()->left() = y;
+
+ y->right() = node;
+ node->parent() = y;
+ }
+};
+
+int
+main(int argc, char** argv)
+{
+ int n = (argc > 1) ? stoi(argv[1]) : 100;
+ string t;
+ int m;
+ ifstream fin("input.txt");
+ ofstream fout("output.txt");
+
+ for (int i = 0; i < n; ++i) {
+ fin >> t >> m;
+
+ if (t == "int") {
+ RBtree<int>* rb = new RBtree<int>();
+ int k;
+ for (int j = 0; j < m; ++j) {
+ fin >> k;
+ rb->insert(k);
+ }
+ fout << rb->bh(rb->root()) << endl;
+ } else if (t == "double") {
+ RBtree<double>* rb = new RBtree<double>();
+ double k;
+ for (int j = 0; j < m; ++j) {
+ fin >> k;
+ rb->insert(k);
+ }
+ fout << rb->bh(rb->root()) << endl;
+ }
+ }
+
+ fin.close();
+ fout.close();
+ return 0;
+}
diff --git a/Year_2/Algorithms/insert-RBtree.cc b/Year_2/Algorithms/insert-RBtree.cc
new file mode 100644
index 0000000..9569fe0
--- /dev/null
+++ b/Year_2/Algorithms/insert-RBtree.cc
@@ -0,0 +1,335 @@
+#include <fstream>
+#include <iostream>
+
+using namespace std;
+
+enum class Color {
+ Red,
+ Black
+};
+
+template <typename H>
+class Node {
+public:
+ Node(Color color, H key, Node<H>* parent = nullptr, Node<H>* left = nullptr, Node<H>* right = nullptr)
+ : color_ { color }
+ , key_ { key }
+ , parent_ { parent }
+ , left_ { left }
+ , right_ { right }
+ {
+ }
+
+ const H&
+ key() const
+ {
+ return key_;
+ }
+
+ const Color&
+ color() const
+ {
+ return color_;
+ }
+ Color&
+ color()
+ {
+ return color_;
+ }
+
+ const Node<H>*&
+ parent() const
+ {
+ return parent_;
+ }
+ Node<H>*&
+ parent()
+ {
+ return parent_;
+ }
+
+ const Node<H>*&
+ grandp() const
+ {
+ return parent_->parent();
+ }
+ Node<H>*&
+ grandp()
+ {
+ return parent_->parent();
+ }
+
+ const Node<H>*&
+ left() const
+ {
+ return left_;
+ }
+ Node<H>*&
+ left()
+ {
+ return left_;
+ }
+
+ const Node<H>*&
+ right() const
+ {
+ return right_;
+ }
+ Node<H>*&
+ right()
+ {
+ return right_;
+ }
+
+private:
+ Color color_;
+ H key_;
+ Node<H>* parent_ { nullptr };
+ Node<H>* left_ { nullptr };
+ Node<H>* right_ { nullptr };
+};
+
+template <typename H>
+class RBtree {
+public:
+ RBtree(Node<H>* root = nullptr)
+ : root_ { root }
+ {
+ }
+
+ RBtree<H>*
+ insert(H key)
+ {
+ Node<H>* z = new Node<H>(Color::Red, key);
+
+ Node<H>* y = nullptr;
+ auto x = root_;
+
+ while (x != nullptr) {
+ y = x;
+ if (z->key() < x->key())
+ x = x->left();
+ else
+ x = x->right();
+ }
+
+ z->parent() = y;
+
+ if (y == nullptr) {
+ root_ = z;
+ } else if (z->key() < y->key()) {
+ y->left() = z;
+ } else {
+ y->right() = z;
+ }
+
+ if (!z->parent()) {
+ z->color() = Color::Black;
+ } else if (z->parent()->parent()) {
+ fixup(z);
+ }
+
+ return this;
+ }
+
+ Node<H>*
+ root()
+ {
+ return root_;
+ }
+
+ void
+ printPre(Node<H>* node, ostream& out)
+ {
+ if (node == nullptr) {
+ return;
+ }
+
+ out << "(" << node->key() << " " << (node->color() == Color::Red ? 'R' : 'B') << ") ";
+ printPre(node->left(), out);
+ printPre(node->right(), out);
+ }
+
+ void
+ printIn(Node<H>* node, ostream& out)
+ {
+ if (node == nullptr) {
+ return;
+ }
+
+ printIn(node->left(), out);
+ out << "(" << node->key() << " " << (node->color() == Color::Red ? 'R' : 'B') << ") ";
+ printIn(node->right(), out);
+ }
+
+ void
+ printPost(Node<H>* node, ostream& out)
+ {
+ if (node == nullptr) {
+ return;
+ }
+
+ printPost(node->left(), out);
+ printPost(node->right(), out);
+ out << "(" << node->key() << " " << (node->color() == Color::Red ? 'R' : 'B') << ") ";
+ }
+
+private:
+ Node<H>* root_ { nullptr };
+
+ Node<H>*
+ search(H key)
+ {
+ auto t = this->root();
+
+ while (t != nullptr && key != t->key()) {
+ if (key < t->key()) {
+ if (t->left()) {
+ t = t->left();
+ } else {
+ break;
+ }
+ } else {
+ if (t->right()) {
+ t = t->right();
+ } else {
+ break;
+ }
+ }
+ }
+
+ return t;
+ }
+
+ void
+ fixup(Node<H>* z)
+ {
+ while (z->parent()->color() == Color::Red) {
+ if (z->grandp()->right() == z->parent()) {
+ auto y = z->grandp()->left();
+ if (y && y->color() == Color::Red) {
+ z->parent()->color() = Color::Black;
+ y->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ z = z->grandp();
+ } else {
+ if (z == z->parent()->left()) {
+ z = z->parent();
+ rrotate(z);
+ }
+ z->parent()->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ lrotate(z->grandp());
+ }
+ } else {
+ auto y = z->grandp()->right();
+ if (y && y->color() == Color::Red) {
+ z->parent()->color() = Color::Black;
+ y->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ z = z->grandp();
+ } else {
+ if (z == z->parent()->right()) {
+ z = z->parent();
+ lrotate(z);
+ }
+ z->parent()->color() = Color::Black;
+ z->grandp()->color() = Color::Red;
+ rrotate(z->grandp());
+ }
+ }
+
+ if (z == root_)
+ break;
+ }
+
+ root_->color() = Color::Black;
+ }
+
+ void
+ lrotate(Node<H>* node)
+ {
+ auto y = node->right();
+ node->right() = y->left();
+ if (y->left())
+ y->left()->parent() = node;
+ y->parent() = node->parent();
+
+ if (!node->parent())
+ root_ = y;
+ else if (node == node->parent()->left())
+ node->parent()->left() = y;
+ else
+ node->parent()->right() = y;
+
+ y->left() = node;
+ node->parent() = y;
+ }
+
+ void
+ rrotate(Node<H>* node)
+ {
+ auto y = node->left();
+ node->left() = y->right();
+ if (y->right())
+ y->right()->parent() = node;
+ y->parent() = node->parent();
+
+ if (!node->parent())
+ root_ = y;
+ else if (node == node->parent()->right())
+ node->parent()->right() = y;
+ else
+ node->parent()->left() = y;
+
+ y->right() = node;
+ node->parent() = y;
+ }
+};
+
+int
+main(int argc, char** argv)
+{
+ int n = (argc > 1) ? stoi(argv[1]) : 100;
+ string t, print;
+ int m;
+ ifstream fin("input.txt");
+ ofstream fout("output.txt");
+
+ for (int i = 0; i < n; ++i) {
+ fin >> t >> m >> print;
+
+ if (t == "int") {
+ RBtree<int>* rb = new RBtree<int>();
+ int k;
+ for (int j = 0; j < m; ++j) {
+ fin >> k;
+ rb->insert(k);
+ }
+ if (print == "preorder")
+ rb->printPre(rb->root(), fout);
+ else if (print == "postorder")
+ rb->printPost(rb->root(), fout);
+ else if (print == "inorder")
+ rb->printIn(rb->root(), fout);
+ } else if (t == "double") {
+ RBtree<double>* rb = new RBtree<double>();
+ double k;
+ for (int j = 0; j < m; ++j) {
+ fin >> k;
+ rb->insert(k);
+ }
+ if (print == "preorder")
+ rb->printPre(rb->root(), fout);
+ else if (print == "postorder")
+ rb->printPost(rb->root(), fout);
+ else if (print == "inorder")
+ rb->printIn(rb->root(), fout);
+ }
+ fout << endl;
+ }
+
+ fin.close();
+ fout.close();
+ return 0;
+}
--
cgit v1.2.3-18-g5258