From 8be9b7e84fbc723089412f62505fee5e6a4c879d Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Wed, 18 Jan 2023 00:16:22 +0100 Subject: Add exs --- Year_2/Algorithms/RB.cc | 335 +++++++++++++++++++++++++++++++++++++++++++ Year_2/Algorithms/heapify.cc | 182 +++++++++++++++++++++++ 2 files changed, 517 insertions(+) create mode 100644 Year_2/Algorithms/RB.cc create mode 100644 Year_2/Algorithms/heapify.cc (limited to 'Year_2') diff --git a/Year_2/Algorithms/RB.cc b/Year_2/Algorithms/RB.cc new file mode 100644 index 0000000..9569fe0 --- /dev/null +++ b/Year_2/Algorithms/RB.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; +} diff --git a/Year_2/Algorithms/heapify.cc b/Year_2/Algorithms/heapify.cc new file mode 100644 index 0000000..bb19360 --- /dev/null +++ b/Year_2/Algorithms/heapify.cc @@ -0,0 +1,182 @@ +#include +#include +#include + +using namespace std; + +enum class HeapType { + Min, + Max +}; + +template +class Heap { +public: + Heap(HeapType type, int n) + : n_ { n + 1 } + , type_ { type } + { + a_ = new H[n + 1]; + a_[0] = 0; + } + + ~Heap() + { + delete[] a_; + } + + void + heapify(int i) + { + if (heapsize_ >= 1) + count_++; + + int l = left(i); + int r = right(i); + int max = i; + + if (l <= heapsize_ && compare(l, max)) + max = l; + if (r <= heapsize_ && compare(r, max)) + max = r; + + if (max != i) { + swap(a_[i], a_[max]); + heapify(max); + } + } + + void + build(H aux[], int n) + { + a_ = aux; + heapsize_ = n; + + for (int i = heapsize_ / 2; i > 0; --i) { + heapify(i); + } + } + + H + extract() + { + swap(a_[1], a_[heapsize_]); + heapsize_--; + heapify(1); + + return a_[heapsize_ + 1]; + } + + inline int + left(int i) + { + return i << 1; + } + inline int + right(int i) + { + return (i << 1) | 1; + } + + void + sort(ostream& out) + { + H* b = new H[heapsize_ + 1]; + + int n = heapsize_; + + for (unsigned i = n; i > 0; --i) { + b[i] = extract(); + } + out << count_ << endl; + + delete[] b; + } + +private: + H* a_; + int heapsize_ { 0 }; + int n_; + HeapType type_; + + bool + compare(int i, int j) + { + return (type_ == HeapType::Max) ? a_[i] > a_[j] : a_[j] > a_[i]; + } + int count_ { 0 }; +}; + +int +main(int argc, char** argv) +{ + int n = (argc > 1) ? stoi(argv[1]) : 100; + ifstream fin("input.txt"); + ofstream fout("output.txt"); + + string t; + int m; + + for (int i = 0; i < n; ++i) { + fin >> t >> m; + + if (t == "int") { + Heap* pq = new Heap(HeapType::Max, m); + int* k = new int[m + 1]; + + k[0] = 0; + for (int j = 1; j <= m; ++j) { + fin >> k[j]; + } + pq->build(k, m); + + pq->sort(fout); + + delete pq; + } else if (t == "double") { + Heap* pq = new Heap(HeapType::Max, m); + double* k = new double[m + 1]; + + k[0] = 0; + for (int j = 1; j <= m; ++j) { + fin >> k[j]; + } + pq->build(k, m); + + pq->sort(fout); + + delete pq; + } else if (t == "bool") { + Heap* pq = new Heap(HeapType::Max, m); + bool* k = new bool[m + 1]; + + k[0] = 0; + for (int j = 1; j <= m; ++j) { + fin >> k[j]; + } + pq->build(k, m); + + pq->sort(fout); + + delete pq; + } else if (t == "char") { + Heap* pq = new Heap(HeapType::Max, m); + char* k = new char[m + 1]; + + k[0] = 0; + for (int j = 1; j <= m; ++j) { + fin >> k[j]; + } + pq->build(k, m); + + pq->sort(fout); + + delete pq; + } + } + + fin.close(); + fout.close(); + + return 0; +} -- cgit v1.2.3-18-g5258