Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar10 / AVLTree.hpp
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar10/AVLTree.hpp
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
1 files changed, 0 insertions, 203 deletions
-rw-r--r--Seminar10/AVLTree.hpp203
diff --git a/Seminar10/AVLTree.hpp b/Seminar10/AVLTree.hpp
deleted file mode 100644
index 355d1c5..0000000
--- a/Seminar10/AVLTree.hpp
+++ /dev/null
@@ -1,203 +0,0 @@
-#ifndef AVL_TREE_IMPL
-#define AVL_TREE_IMPL
-
-#include<algorithm>
-#include<cassert>
-#include<cstddef>
-
-template<class T>
-class AVLTree {
-private:
-
- struct Node {
- T data;
- Node* left;
- Node* right;
- int height;
-
- static int getHeight(const Node* r) {
- if (r == nullptr)
- return 0;
-
- return r->height;
- }
-
- static void rotateLeft(Node*& r) {
- assert(r->right != nullptr);
-
- Node* originalRight = r->right;
- r->right = originalRight->left;
- originalRight->left = r;
- r = originalRight;
- }
-
- static void rotateRight(Node*& r) {
- assert(r->left != nullptr);
-
- Node* originalLeft = r->left;
- r->left = originalLeft->right;
- originalLeft->right = r;
- r = originalLeft;
- }
-
- static void balanceLeft(Node*& r) {
- assert(r);
-
- int rootBalance = getBalanceFactor(r);
- int leftBalance = getBalanceFactor(r->left);
-
- if (rootBalance == -2) {
- if (leftBalance == 1) {
- rotateLeft(r->left);
- updateHeight(r->left->left);
- updateHeight(r->left);
- }
-
- rotateRight(r);
- updateHeight(r->right);
- updateHeight(r);
- }
- }
-
- static void balanceRight(Node*& r) {
- assert(r);
-
- int rootBalance = getBalanceFactor(r);
- int rightBalance = getBalanceFactor(r->right);
-
- if (rootBalance == 2) {
- if (rightBalance == -1) {
- rotateRight(r->right);
- updateHeight(r->right->right);
- updateHeight(r->right);
- }
-
- rotateLeft(r);
- updateHeight(r->left);
- updateHeight(r);
- }
- }
-
- static void updateHeight(Node* r) {
- if (r == nullptr)
- return;
- r->height = std::max(getHeight(r->left), getHeight(r->right)) + 1;
- }
-
- static int getBalanceFactor(const Node* r) {
- if (r == nullptr)
- return 0;
-
- return getHeight(r->right) - getHeight(r->left);
- }
-
- Node(const T& d, Node* l, Node* r, int h) : data{ d }, left{ l }, right{ r }, height{ h } {}
- };
-
- Node* findMinNode(Node* r) {
- if (r->left == nullptr)
- return r;
-
- return findMinNode(r->left);
- }
-
- void insertRec(Node*& r, const T& elem) {
- if (r == nullptr) {
- r = new Node(elem, nullptr, nullptr, 1);
- size++;
- return;
- }
-
- if (r->data < elem) {
- insertRec(r->right, elem);
-
- Node::updateHeight(r->right);
- Node::balanceRight(r);
- }
- else if (r->data > elem) {
- insertRec(r->left, elem);
-
- Node::updateHeight(r->left);
- Node::balanceLeft(r);
- }
- }
-
- bool removeRec(Node*& r, const T& elem) {
- if (r == nullptr) {
- return false;
- }
-
- if (r->data < elem) {
- removeRec(r->right, elem);
-
- Node::updateHeight(r);
- Node::balanceLeft(r);
- }
- else if (r->data > elem) {
- removeRec(r->left, elem);
-
- Node::updateHeight(r);
- Node::balanceRight(r);
- }
- else {
- if (!r->left && !r->right) {
- delete r;
- r = nullptr;
- return true;
- }
- else if (r->left && !r->right) {
- Node* toDelete = r;
- r = r->left;
- delete toDelete;
- }
- else if (!r->left && r->right) {
- Node* toDelete = r;
- r = r->right;
- delete toDelete;
- }
- else {
- root->data = findMinNode(root->right)->data;
- removeRec(r->right, r->data);
- Node::updateHeight(r);
- Node::balanceRight(r);
- }
- }
- return true;
- }
-
- void freeRec(Node* r) {
- if (r == nullptr)
- return;
-
- freeRec(r->left);
- freeRec(r->right);
- delete r;
- }
-
-public:
- AVLTree() : root{ nullptr }, size{ 0 } {}
-
- // TBI
- AVLTree(const AVLTree<T>& other) = delete;
- AVLTree& operator=(const AVLTree<T>& other) = delete;
- bool contains(const T& elem);
-
- void insert(const T& elem) {
- insertRec(root, elem);
- }
-
- bool remove(const T& elem) {
- return removeRec(root, elem);
- }
-
- ~AVLTree() {
- freeRec(root);
- }
-
-private:
-
- Node* root;
- size_t size;
-};
-
-#endif