From d703960951d838ce92687a4947581bc09a160f60 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Wed, 18 Jan 2023 12:46:40 +0100 Subject: Add --- Year_2/Algorithms/insert-RBtree.cc | 335 +++++++++++++++++++++++++++++++++++++ 1 file changed, 335 insertions(+) create mode 100644 Year_2/Algorithms/insert-RBtree.cc (limited to 'Year_2/Algorithms/insert-RBtree.cc') 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 +#include + +using namespace std; + +enum class Color { + Red, + Black +}; + +template +class Node { +public: + Node(Color color, H key, Node* parent = nullptr, Node* left = nullptr, Node* 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*& + parent() const + { + return parent_; + } + Node*& + parent() + { + return parent_; + } + + const Node*& + grandp() const + { + return parent_->parent(); + } + Node*& + grandp() + { + return parent_->parent(); + } + + const Node*& + left() const + { + return left_; + } + Node*& + left() + { + return left_; + } + + const Node*& + right() const + { + return right_; + } + Node*& + right() + { + return right_; + } + +private: + Color color_; + H key_; + Node* parent_ { nullptr }; + Node* left_ { nullptr }; + Node* right_ { nullptr }; +}; + +template +class RBtree { +public: + RBtree(Node* root = nullptr) + : root_ { root } + { + } + + RBtree* + insert(H key) + { + Node* z = new Node(Color::Red, key); + + Node* 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* + root() + { + return root_; + } + + void + printPre(Node* 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* 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* 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* root_ { nullptr }; + + Node* + 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* 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* 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* 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* rb = new RBtree(); + 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* rb = new RBtree(); + 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