Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit981037e28374f8c4ab44e26bdeda62da59f21a21 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-12-04 17:15:45 -0500
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-12-04 17:15:45 -0500
Files8e4caeb3663627ac318a839efa217216cc21f8b2
Data-structures-and-algorithms-981037e28374f8c4ab44e26bdeda62da59f21a21.tar
Data-structures-and-algorithms-981037e28374f8c4ab44e26bdeda62da59f21a21.tar.gz
Data-structures-and-algorithms-981037e28374f8c4ab44e26bdeda62da59f21a21.zip
Parent36a5f76137ee642768e828ace30359c5e468aa10 (diff)
Add sem08
5 files changed, 404 insertions, 1 deletions
-rw-r--r--README.md8
-rw-r--r--Seminar08/README.md3
-rw-r--r--Seminar08/src/BST/indexable-bst.hpp319
-rw-r--r--Seminar08/src/BST/tests.cpp28
-rw-r--r--Seminar08/src/rotations.cpp47
diff --git a/README.md b/README.md
index 16d9584..dc9ce6f 100644
--- a/README.md
+++ b/README.md
@@ -17,4 +17,10 @@
## Тема 6
Въвеждане и начини за имплементация на структура от данни опашка. Въвеждане и начини за имплементация на структура от данни стек. Задачата за разпознаване на балансиран низ от скоби. Имплементация
-на ForwardIterator за двоично наредено дърво. Въвеждане и начини за имплементация на структура от данни дърво. Основни задачи при работа с дървета. \ No newline at end of file
+на ForwardIterator за двоично наредено дърво. Въвеждане и начини за имплементация на структура от данни дърво. Основни задачи при работа с дървета.
+
+## Тема 7
+Задачи за дървета. Балансирани дървета. Ротации и AVL дървета.
+
+## Тема 8
+Имплементация на ротации. Индексация в двоично наредено дърво за логаритмично време. Heaps и абстрактна структура от данни приоритетна опашка. \ No newline at end of file
diff --git a/Seminar08/README.md b/Seminar08/README.md
new file mode 100644
index 0000000..8efc96a
--- /dev/null
+++ b/Seminar08/README.md
@@ -0,0 +1,3 @@
+# Осми семинар по структури от данни - 28.10.2024
+
+## Имплементация на ротации. Индексация в двоично наредено дърво за логаритмично време. Heaps и асд приоритетна опашка. \ No newline at end of file
diff --git a/Seminar08/src/BST/indexable-bst.hpp b/Seminar08/src/BST/indexable-bst.hpp
new file mode 100644
index 0000000..0770dbd
--- /dev/null
+++ b/Seminar08/src/BST/indexable-bst.hpp
@@ -0,0 +1,319 @@
+#pragma once
+#include <functional>
+#include <iostream>
+#include <stack>
+#include <vector>
+
+template <class T, typename Compare = std::less<T>>
+class Bst
+{
+ private:
+ struct Node
+ {
+ T data;
+ Node* left;
+ Node* right;
+ size_t size;
+ Node(const T& data, Node* left = nullptr, Node* right = nullptr)
+ : data(data)
+ , left(left)
+ , right(right)
+ , size(1)
+ {}
+ };
+
+ Node* root = nullptr;
+ Compare comp; // comparator instance
+
+ Node** findMinNode(Node** root, std::stack<Node*>& toDecrease);
+ void free(Node* current);
+ Node* copy(Node* current);
+
+ const T& indexRec(Node* root, unsigned idx) const;
+ public:
+ Bst() = default;
+ explicit Bst(const Compare& comparator)
+ : comp(comparator)
+ {}
+ Bst(const Bst<T, Compare>& other);
+ Bst<T, Compare>& operator=(const Bst<T, Compare>& other);
+ ~Bst();
+
+ bool insert(const T& data);
+ bool contains(const T& data) const;
+ bool remove(const T& data);
+
+ size_t getSize() const;
+ bool isEmpty() const;
+
+ const T& index(unsigned idx) const;
+
+ class ForwardIterator
+ {
+ private:
+ std::stack<Node*> nodeStack;
+
+ void pushLeft(Node* node)
+ {
+ while (node)
+ {
+ nodeStack.push(node);
+ node = node->left;
+ }
+ }
+
+ public:
+ ForwardIterator(Node* root = nullptr)
+ {
+ pushLeft(root);
+ }
+
+ T& operator*() const
+ {
+ return nodeStack.top()->data;
+ }
+
+ ForwardIterator& operator++()
+ {
+ Node* node = nodeStack.top();
+ nodeStack.pop();
+ if (node->right)
+ {
+ pushLeft(node->right);
+ }
+ return *this;
+ }
+ ForwardIterator operator++(int)
+ {
+ ForwardIterator old = *this;
+ ++(*this);
+ return old;
+ }
+
+ bool operator!=(const ForwardIterator& other) const
+ {
+ return nodeStack != other.nodeStack;
+ }
+
+ bool operator==(const ForwardIterator& other) const
+ {
+ return nodeStack == other.nodeStack;
+ }
+ };
+
+ ForwardIterator begin() const
+ {
+ return ForwardIterator(root);
+ }
+
+ ForwardIterator end() const
+ {
+ return ForwardIterator(nullptr);
+ }
+};
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::insert(const T& data)
+{
+ Node** current = &root;
+ std::stack<Node*> toIncrease;
+ while (*current)
+ {
+ toIncrease.push(*current);
+
+ if (comp(data, (*current)->data))
+ current = &(*current)->left;
+ else if (comp((*current)->data, data))
+ current = &(*current)->right;
+ else
+ return false; // Data already exists
+ }
+ *current = new Node(data);
+
+ while (toIncrease.size())
+ {
+ Node* currentNode = toIncrease.top();
+ currentNode->size++;
+ toIncrease.pop();
+ }
+
+ return true;
+}
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::contains(const T& data) const
+{
+ Node* current = root;
+
+ while (current)
+ {
+ if (comp(data, current->data))
+ current = current->left;
+ else if (comp(current->data, data))
+ current = current->right;
+ else
+ return true;
+ }
+ return false;
+}
+
+template <class T, typename Compare>
+typename Bst<T, Compare>::Node** Bst<T, Compare>::findMinNode(Node** root, std::stack<Node*>& toDecrease)
+{
+ Node** current = root;
+
+ while ((*current)->left)
+ {
+ toDecrease.push(*current);
+ current = &(*current)->left;
+ }
+ return current;
+}
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::remove(const T& data)
+{
+ Node** current = &root;
+ std::stack<Node*> toDecrease;
+
+ while (*current)
+ {
+ if (comp(data, (*current)->data))
+ current = &(*current)->left;
+ else if (comp((*current)->data, data))
+ current = &(*current)->right;
+ else
+ break;
+
+ toDecrease.push(*current);
+ }
+
+ if (!(*current))
+ return false; // Data not found
+
+ Node* toDelete = *current;
+
+ if (!(*current)->left && !(*current)->right)
+ *current = nullptr; // Node has no children
+ else if (!(*current)->right)
+ *current = (*current)->left; // Node has only left child
+ else if (!(*current)->left)
+ *current = (*current)->right; // Node has only right child
+ else
+ {
+ Node** rightMin = findMinNode(&(*current)->right, toDecrease);
+
+ *current = *rightMin;
+ *rightMin = (*rightMin)->right;
+
+ (*current)->left = toDelete->left;
+ (*current)->right = toDelete->right;
+ }
+ delete toDelete;
+
+ while (toDecrease.size())
+ {
+ Node* currentNode = toDecrease.top();
+ toDecrease.pop();
+ --currentNode->size;
+ }
+
+ return true;
+}
+
+template <class T, typename Compare>
+size_t Bst<T, Compare>::getSize() const
+{
+ return root ? root->size : 0;
+}
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::isEmpty() const
+{
+ return getSize() == 0;
+}
+
+template <class T, typename Compare>
+typename Bst<T, Compare>::Node* Bst<T, Compare>::copy(Node* current)
+{
+ if (!current)
+ return nullptr;
+ Node* res = new Node(current->data);
+ res->left = copy(current->left);
+ res->right = copy(current->right);
+ res->size = current->size;
+ return res;
+}
+
+template <class T, typename Compare>
+const T& Bst<T, Compare>::indexRec(Node* root, unsigned idx) const
+{
+ size_t currentIndex = root->left ? root->left->size : 0;
+
+ if(currentIndex == idx)
+ {
+ return root->data;
+ }
+
+ if(currentIndex > idx)
+ {
+ return indexRec(root->left, idx);
+ }
+
+ return indexRec(root->right, idx - currentIndex - 1);
+}
+
+template <class T, typename Compare>
+const T& Bst<T, Compare>::index(unsigned idx) const
+{
+ if(idx >= getSize())
+ throw std::runtime_error("Out of bound");
+
+ return indexRec(root, idx);
+}
+
+template <class T, typename Compare>
+void Bst<T, Compare>::free(Node* current)
+{
+ if (!current)
+ return;
+ free(current->left);
+ free(current->right);
+ delete current;
+}
+
+template <class T, typename Compare>
+Bst<T, Compare>::Bst(const Bst<T, Compare>& other)
+ : comp(other.comp)
+{
+ root = copy(other.root);
+}
+
+template <class T, typename Compare>
+Bst<T, Compare>& Bst<T, Compare>::operator=(const Bst<T, Compare>& other)
+{
+ if (this != &other)
+ {
+ free(root);
+ root = copy(other.root);
+ comp = other.comp;
+ }
+ return *this;
+}
+
+template <class T, typename Compare>
+Bst<T, Compare>::~Bst()
+{
+ free(root);
+}
+
+void treeSort(std::vector<int>& v)
+{
+ Bst<int> bst;
+ for (int i = 0; i < v.size(); i++)
+ bst.insert(v.at(i));
+
+ unsigned index = 0;
+ for (auto it = bst.begin(); it != bst.end(); it++)
+ v.at(index++) = *it;
+} \ No newline at end of file
diff --git a/Seminar08/src/BST/tests.cpp b/Seminar08/src/BST/tests.cpp
new file mode 100644
index 0000000..e1ba15e
--- /dev/null
+++ b/Seminar08/src/BST/tests.cpp
@@ -0,0 +1,28 @@
+#include "indexable-bst.hpp"
+
+int main()
+{
+ Bst<int> bst;
+
+ for (size_t i = 0; i < 100; i++)
+ {
+ bst.insert(i);
+ }
+
+ for (size_t i = 0; i < bst.getSize(); i++)
+ {
+ std::cout << bst.index(i) << " ";
+ }
+
+ std::cout << std::endl;
+
+ for (size_t i = 0; i < 50; i++)
+ {
+ bst.remove(i);
+ }
+
+ for (size_t i = 0; i < bst.getSize(); i++)
+ {
+ std::cout << bst.index(i) << " ";
+ }
+} \ No newline at end of file
diff --git a/Seminar08/src/rotations.cpp b/Seminar08/src/rotations.cpp
new file mode 100644
index 0000000..59c452a
--- /dev/null
+++ b/Seminar08/src/rotations.cpp
@@ -0,0 +1,47 @@
+#include <iostream>
+
+struct node
+{
+ int data;
+ node* left;
+ node* right;
+
+ node(int data_, node* left_ = nullptr, node* right_ = nullptr) :
+ data(data_),
+ left(left_),
+ right(right_) {}
+};
+
+node* leftRotate(node* root)
+{
+ if(root == nullptr || root->right == nullptr)
+ return nullptr;
+
+ node* originalRight = root->right;
+ root->right = originalRight->left;
+ originalRight->left = root;
+
+ return originalRight;
+}
+
+node* rightRotate(node* root)
+{
+ if(root == nullptr || root->left == nullptr)
+ return nullptr;
+
+ node* originalLeft = root->left;
+ root->left = originalLeft->right;
+ originalLeft->right = root;
+
+ return originalLeft;
+}
+
+int main()
+{
+ node* example = new node(2, new node(1), new node(3));
+ example = leftRotate(example);
+ example = rightRotate(example);
+
+ std::cout << example->data << " " << example->left->data << " " << example->right->data;
+
+}