From 981037e28374f8c4ab44e26bdeda62da59f21a21 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Wed, 4 Dec 2024 17:15:45 -0500 Subject: Add sem08 --- README.md | 8 +- Seminar08/README.md | 3 + Seminar08/src/BST/indexable-bst.hpp | 319 ++++++++++++++++++++++++++++++++++++ Seminar08/src/BST/tests.cpp | 28 ++++ Seminar08/src/rotations.cpp | 47 ++++++ 5 files changed, 404 insertions(+), 1 deletion(-) create mode 100644 Seminar08/README.md create mode 100644 Seminar08/src/BST/indexable-bst.hpp create mode 100644 Seminar08/src/BST/tests.cpp create mode 100644 Seminar08/src/rotations.cpp 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 +#include +#include +#include + +template > +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& 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& other); + Bst& operator=(const Bst& 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 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 +bool Bst::insert(const T& data) +{ + Node** current = &root; + std::stack 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 +bool Bst::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 +typename Bst::Node** Bst::findMinNode(Node** root, std::stack& toDecrease) +{ + Node** current = root; + + while ((*current)->left) + { + toDecrease.push(*current); + current = &(*current)->left; + } + return current; +} + +template +bool Bst::remove(const T& data) +{ + Node** current = &root; + std::stack 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 +size_t Bst::getSize() const +{ + return root ? root->size : 0; +} + +template +bool Bst::isEmpty() const +{ + return getSize() == 0; +} + +template +typename Bst::Node* Bst::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 +const T& Bst::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 +const T& Bst::index(unsigned idx) const +{ + if(idx >= getSize()) + throw std::runtime_error("Out of bound"); + + return indexRec(root, idx); +} + +template +void Bst::free(Node* current) +{ + if (!current) + return; + free(current->left); + free(current->right); + delete current; +} + +template +Bst::Bst(const Bst& other) + : comp(other.comp) +{ + root = copy(other.root); +} + +template +Bst& Bst::operator=(const Bst& other) +{ + if (this != &other) + { + free(root); + root = copy(other.root); + comp = other.comp; + } + return *this; +} + +template +Bst::~Bst() +{ + free(root); +} + +void treeSort(std::vector& v) +{ + Bst 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 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 + +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; + +} -- cgit v1.3.1-26-gb76a