From 3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Wed, 20 Nov 2024 15:37:03 -0500 Subject: Add Seminar06 --- Seminar06/README.md | 305 +++++++++++++++++++++++++++ Seminar06/media/left-child-right-sibling.png | Bin 0 -> 22100 bytes Seminar06/media/stick.png | Bin 0 -> 13709 bytes Seminar06/media/subtree.png | Bin 0 -> 32004 bytes Seminar06/media/tree-first-example.png | Bin 0 -> 16135 bytes Seminar06/media/tree-second-example.png | Bin 0 -> 20847 bytes Seminar06/src/balanced-brackets.cpp | 43 ++++ Seminar06/src/forward-iterator-bst.hpp | 260 +++++++++++++++++++++++ Seminar06/src/test-bst-iter.cpp | 19 ++ 9 files changed, 627 insertions(+) create mode 100644 Seminar06/README.md create mode 100644 Seminar06/media/left-child-right-sibling.png create mode 100644 Seminar06/media/stick.png create mode 100644 Seminar06/media/subtree.png create mode 100644 Seminar06/media/tree-first-example.png create mode 100644 Seminar06/media/tree-second-example.png create mode 100644 Seminar06/src/balanced-brackets.cpp create mode 100644 Seminar06/src/forward-iterator-bst.hpp create mode 100644 Seminar06/src/test-bst-iter.cpp diff --git a/Seminar06/README.md b/Seminar06/README.md new file mode 100644 index 0000000..7c455a9 --- /dev/null +++ b/Seminar06/README.md @@ -0,0 +1,305 @@ +# Шести семинар по структури от данни - 14.11.2024 + +## Структура от данни опашка. +Абстрактната структура от данни опашка поддържа следния интерфейс: + +* push(x) или enqueue(x) - Добавя елемент в опашката. +* pop() или dequeue() - Премахва елементът, който е бил в колекцията най - дълго време. +* front() - Връща елементът, който е бил в колекцията най - дълго време. +* size() - Връща броя на елементите в колекцията. + +За опашката интуитивно може да се мисли като за истинска опашка (опашка пред каса, опашка от песни, ...). Тя имплементира First-In First-Out стратегия - първия добавен елемент е винаги първия изваден. Аналогично - втория добавен елемент е втория изваден и т.н. STL предлага имплементация на АСД опашка - нека разгледаме следния пример: + +```cpp +#include +#include + +int main() +{ + std::queue q; + q.push(1); + q.push(2); + q.push(3); + + std::cout << q.top(); // 1 + q.pop(); + std::cout << q.top(); // 2 + q.pop(); + std::cout << q.top(); // 3 + q.pop(); + + std::cout << q.empty(); // true +} +``` + +Също така класът `std::queue` поддържа и метод `back()`, който не се споменава в интерфейса на АСД. + +### Къде се използват опашки +Структурата от данни опашка има множество приложения, някои от които: +* За различни алгоритми - Опашката е основна част в някои осносви алгоритми, като алгоритъмът "Търсене в широчина" (breath first search). + +* Опашките се използват за реализиране на стратегии за оптимално кеширане на данни. Пример за това е стратегията LRU (least recently used), в която при препълване на кеша от него се освобождават елементите, които са били достъпвани последни във времето. + +* Опашки на задачите - В много ситуации нашата програма трябва да обработи няколко задачи наведнъж. При невъзможност всички задачи да се обработят на момента, задачите се запазват в опашка и след като програмата ни приключи с изпълнение на дадена задача, тя проверява в опашката със задачи за следваща. + +* Планиране на задачи - Различни алгоритми за планиране на задачи използват опашки за да подсигурят коректната си работа. + +### Начини за имплементация +Опашка можем да реализираме използвайки идеите от разгледани структури от данни. + +1. Свързано представяне - Можем да преизползваме идеята на свързания списък и да ограничим интерфейса. Операциите `push` и `pop` могат да се реализират в константно време използвайки двусвързано представяне. + +2. Представяне чрез динамичен масив - Можем да преизползваме идеята за динамичен масив и да ограничим интерфейса. Всъщност, реализацията ще е "окастрена" версия на разгледаната структура от данни `deque`. Това не трябва да ни очудва - името `deque` произлиза от `double ended queue`. + +3. Представяне чрез статичен масив - Понякога имаме нужда от ограничени опашки. В такъв случай можем да използваме статичен масив - при препълване на опашката можем или да премахваме най - рано добавения елемент или да хвърляме грешка. + +Реализацията в stl използва контейнер, който поддържа операции `push_back(x)`, `pop_front()`, `back()` и `front()`. Имайки тези четири операции можем да реализираме опашка без да се интересуваме как е реализиран контейнера. Това също така е пример за `Adapter Design Pattern` - преобразуваме интерфейса на един клас към друг. + +По подрзбиране контейнера, който се използва, е std::deque. Можем да променим това: + +```cpp +#include +#include + +int main() +{ + std::queue> q; +} +``` + +## Структура от данни стек. +Абстрактната структура от данни стек поддържа следните операции: + +* push(x) - Добавя елемент към колекцията. +* pop() - Премахва последния добавен елемент. +* top() - Връща последния добавен елемент. +* size() - Връща броя на елементите на стека. + +Стекът имплементира Last-In First-Out стратегия. За стека можем да си мислим като купчина чинии наредени една върху друга. Можем да премахнем единствено най - горната чиния (без да счупим нещо). + +В STL има готова имплементация на стек - `std::stack`. Нека разгледаме следния пример: +```cpp +#include +#include + +int main() +{ + std::stack s; + + s.push(1); + s.push(2); + s.push(3); + + std::cout << s.top(); s.pop(); // 3 + std::cout << s.top(); s.pop(); // 2 + std::cout << s.top(); s.pop(); // 1 +} +``` +### Къде се използват стекове +* В различни алгоритми - Използва се в backtracking алгоритми (търсене на път в лабиринт, обхождане в дълбочина, ...) както и в алгоритми за обработка на текст. +* Системния стек - Голяма част от езиците за програмиране са ориентирани около тази идея. +* Undo/redo операции. + +### Начини за имплементация +Начините за имплементация съвпадат с тези на опашката: +* Свързано представяне - тук разликата е, че можем да имплементираме стек поддържащ константни операции по добавяне и премахване използвайки само едносвързано представяне. +* Статичен масив (ограничен стек) +* Динамичен масив - ограничен интерфейс на deque или vector. + +Имплементацияна в stl също намопня имплементацията на `std::queue`. Отново, ако желаем, можем да подадем контейнер който да е отговорен за работата на стека. + +## Задача за разпознаване на балансиран низ от скоби. +Да се имплементира функция +```cpp +bool balanced_brackets(const std::string& str); +``` + +която връща истина ако скобите, съдържащи се в в подадения низ са балансирани, и лъжа в противен случай. + +## Имплементация на ForwardIterator за двоично наредено дърво. + +## Дървета +Свързан граф, който не съдържа цикли наричаме дърво. + +## Примери за дървета +Вероятно всеки вече в един или друг момент се е сблъсквал с дървета. Това е дърво: + +![](media/tree-first-example.png) + +Това също е дърво: + +![](media/tree-second-example.png) + +## Малко дефиниции +| Понятие | Дефиниция +| :--- | :----: +| Дърво | Свързан ацикличен граф. +| Кореново дърво | Дърво, в което точно един връх е избран за корен. В курса говорейки за дърво дърво разбираме кореново дърво. +| Листо | Връх без наследници. +| Вътрешен връх | Връх, който не е листо или корен. +| Разклоненост | Максималния брой деца на кой да е връх. +| Височина на връх *u* | Максималното разстояние между *u* и кое да е листо. +| Дълбочина на връх *u* | Разстоянието между корена и *u*. +| Височина на дърво | Височината на корена. +| Ниво *k* | Множеството от всички върхове с дълбочина *к*. +| Предшественик на връх *u* | За връх *v* казваме, че е предшественик на *u* ако *v* се съдържа в пътя между корена и *u*. +| Наследник на връх *u* | За връх *v* казваме, че е наследник на *u* ако *u* е предшественик на *v*. + +В дефиницията на предшественик, казваме "пътя между корена и *u*". Важно свойство на дърветата е, че между всеки два върха има **точно един път**. Това свойство е необходимо и достатъчно условие граф да е дърво, ако в един граф имаме точно един път между всеки два върха то той е дърво. Какво би се объркало ако съществуват два върха без път между тях? Какво би станало ако имаме два пътя между два върха? + +## Височина на дърво +Височината на дървото ще е от особен интерес за нас. Колко е максималната височина на дърво с *n* върха? Най - много тя може да стане *n*. Това се случва когато дървото е изродено. +Пример за изродено дърво с 4 върха: + +![](media/stick.png) + +Има ли долна граница за височината на дърво? Ако нищо не знаем за дървото, то височината му най - малко може да е 1. Това се случва когато всички възли, различни от корена, са негови наследници (т.е. когато нямаме вътрешни върхове). +Доста често обаче, когато работим с дървета, знаем тяхната разклоненост. +Нека имаме дърво с *n* върха и разклоненост *k*. Тогава то не може да стане по - ниско от $\lfloor \log_k n \rfloor$. + +Опитайте се да начертаете дърво с разклоненост 2 и 8 върха. Възможно ли е височината му да е по - малка от 3? + +## Поддървета +Неформално, поддърво вкоренено във връх *u* е върхът *u* и всичко под него (всички негови наследници). + +![](media/subtree.png) + +## Двоични дървета. +Двоичното дърво е дърво с (максимална) разклоненост 2. Това означава, че всеки връх има най - много две деца. В общия случай различаваме децата като ляво и дясно дете (или ляв и десен наследник). +За двоичните дървета можем също да си мислим като рекурсивно дефинирана структура от данни: +* Празното дърво е двоично дърво. +* Дърво с един връх и без ребра е двоично дърво. +* Възел с ляв наследник двоично дърво и десен наследник двоично дърво е двоично дърво. + +Голяма част от алгоритмите върху двоичните дървета са рекурсивни точно поради този удобен начин да дефинираме двоично дърво. + +Дървото в пример 1 е двоично дърво. Дървото в пример 2 не е двоично дърво, понеже има възел от степен 4. + +## Двоични наредени дървета +Двоичното наредено дърво е двоично дърво за което е вярно следното **свойство:** + +- Нека *u* е възел в двоично наредено дърво. Стойността на всеки връх от лявото поддърво на *u* е по - малка от стойността на *u*. Стойността на всеки връх от дясното поддърво на *u* е по - голяма от стойността на *u*. + +Нищо не ни пречи и да поддържаме повтарящи се елементи - тогава в лявото (или в дясното) поддърво ще държим по - малки или равни (или по - големи или равни) елементи. + +Едно важно нещо, без което не можем да имаме двоично наредено дърво, е свойството на **стойностите на възлите да са сравними**. Не можем да строим двоично наредено дърво от несравними стойности. + +## Представяне на дървета + +### Свързано представяне - Двоични дървета +Представяме двоично дърво като: + +```cpp +template +struct Tree +{ + T data; + Tree* left; + Tree* right; + + Tree(const T& data_, Tree* l = nullptr, Tree* r = nullptr) : + data (data_), + left (l), + right (r) {} +}; +``` + +От тук представяме дървото като указател към обект от тип Tree. + +Дървото от пример 1, представено по този начин, би изглеждало така: + +```cpp +Tree* create_exaple_one() { + return new Tree( + 0, // Корена + new Tree(1), // Лявото поддърво + new Tree( // Дясното поддърво + 2, + new Tree(3, new Tree(5), new Tree(6)), + new Tree(4, nullptr, new Tree(7)) + ) + ); +} +``` + +Как можем да проверим дали възел е листо? +```cpp +template +bool is_leaf(const Tree* t) { + return t != nullptr && t->left == nullptr && t->right == nullptr; +} +``` + +### Списък на бащите +Чрез свързаното представяне в някакъв смисъл слизаме от корена към листата. Какво правим обаче ако искаме да се качваме от листата към корена? + +Нека имаме дърво с *n* върха. Върховете можем да номерираме с числа от 0 до *n-1*. Едно валидно номериране можем да видим в пример едно. Коренът е 0, левия наследник 1, десния 2 и така, по нива, от ляво надясно им даваме индекси от 0 до *n* - 1. + +Разглеждаме масив parent с *n* елемента за който е вярно: **В parent[i] е записан номера на бащата на връх с номер i. Ако върхът с номер i е корен (а корена няма баща) просто пишем -1**. +Дървото от пример 1 може да се представи чрез списък на бащите по следния начин: + +* [-1, 0, 0, 2, 2, 3, 3, 4] + +Едно от предимствата на това представяне е, че можем да представим дърво с произволна разклоненост. Все пак няма значение разклонеността, ако можем да номерираме възлите с числа от 0 до *n-1* можем да го представим по този начин. + +Недостатъците на това представяне са, че добавянето, проверката дали връх е листо, премахването и други операции върху дървета стават сложни. + +### Ляв син десен брат +Представянето чрез масив на бащите ни позволи да представим дърво с произволна разклоненост. Има поне още два начина да се представи такова дърво. За всеки възел пазим указател към най - левия му син и най - десния му брат: + +```cpp +template +struct Tree{ + T data; + Tree* leftChild; + Tree* rightSibling; +}; +``` + +Така от корена можем да достъпим кой да е връх на произволно разклоненото дърво. +![](media/left-child-right-sibling.png) + +Тук в leftChild указателя на 2 ще е записан адреса на 4. В rightSibling указателя на 2 ще е записан 3. Ако някой възел няма ляво дете или десен брат, то указателя просто е nullptr. +Предимството е, че за същата памет, с която представихме двоично дърво, можем да представим дърво с произволна разклоненост. Недостатъка е, че имаме последователен достъп до децата. Тоест ако искам да взема третото дете на връх *u* първо ще трябва да сляза до най - лявото му дете и да се предвижа две позиции надясно. Ако често имаме нужда да четем дете на позиция k това може би не би било най - подходящото представяне. + +### Чрез вектор от децата +Разглеждаме следното представяне: +```cpp +template +struct Tree { + T data; + std::vector*> children; +}; +``` +Ако искаме да вземем третото дете на връх *u* просто правим u->children[2]. Предимството е очевидно - нямаме последователен достъп до децата. Недостатъкът е, че възлите започват да заемат повече памет. Размера на вектора (в x64) е 32 байта. Ако възлите ни са от тип int то размера на структурата би бил 40 байта. +Вектора ще направи алокации, което също в някакъв смисъл забавя програмата. Но пък веднъж като построим дървото имаме бърз достъп до децата. + +### Чрез допълнителен parent указател +Представянето чрез масив на бащите беше хубаво, но проблемът е, че трудно добавяме и изваждаме елемент от колекцията. Ако искаме да имаме дърво което поддържа добавяне и изтриване и също така може да намира родителя си, то просто добавяме още един указател. +```cpp +template +struct Tree { + T data; + Tree* parent; + Tree* left; + Tree* right; + + Tree(T data, Tree* p = nullptr, Tree* l = nullptr, Tree* r = nullptr) : data {data}, parent {p}, left {l}, right {r} {} +} +``` +Тук проблемът е, че отново плащаме цената от 4 (или 8) байта за допълнителен указател. Но пък ако ни трябва добавяне, премахване и движение както от корен към листа така и листа корен плащаме малко памет и имаме всичко това! + +## Задача първа +Да се напише функция, който принтира всички листа на дърво. + +## Задача втора +Да се напише функция, която принтира всички пътища от корена до което и да е листо. + +## Задача трета +Да се напише функция *max((Tree\\* tree)* която връща най - големия елемент в двоично дърво. Да се реализира същата функция за двоично наредено дърво. Да се реализира функция намираща най - малкия елемент. + +## Задача четвърта +Да се реализира функция, която връща височината на двоично дърво. + +## Задача пета +Да се напише функция, която обхожда елементите на двоично дърво по схемата ляво-корен-дясно. (още позната като inorder traversal). Извикайте функцията върху двоично наредено дърво. Какво забелязвате? diff --git a/Seminar06/media/left-child-right-sibling.png b/Seminar06/media/left-child-right-sibling.png new file mode 100644 index 0000000..180f782 Binary files /dev/null and b/Seminar06/media/left-child-right-sibling.png differ diff --git a/Seminar06/media/stick.png b/Seminar06/media/stick.png new file mode 100644 index 0000000..9fcc5ad Binary files /dev/null and b/Seminar06/media/stick.png differ diff --git a/Seminar06/media/subtree.png b/Seminar06/media/subtree.png new file mode 100644 index 0000000..5875be2 Binary files /dev/null and b/Seminar06/media/subtree.png differ diff --git a/Seminar06/media/tree-first-example.png b/Seminar06/media/tree-first-example.png new file mode 100644 index 0000000..4fe94bf Binary files /dev/null and b/Seminar06/media/tree-first-example.png differ diff --git a/Seminar06/media/tree-second-example.png b/Seminar06/media/tree-second-example.png new file mode 100644 index 0000000..bf57c99 Binary files /dev/null and b/Seminar06/media/tree-second-example.png differ diff --git a/Seminar06/src/balanced-brackets.cpp b/Seminar06/src/balanced-brackets.cpp new file mode 100644 index 0000000..cce5d01 --- /dev/null +++ b/Seminar06/src/balanced-brackets.cpp @@ -0,0 +1,43 @@ +#include +#include + +bool is_opening_bracket(char ch) +{ + return ch == '(' || ch == '{' || ch == '['; +} + +bool is_closing_bracket(char ch) +{ + return ch == ')' || ch == ']' || ch == '}'; +} + +bool is_corresponding_brackets(char left, char right) +{ + return left == '(' && right == ')' || left == '{' && right == '}' || left == '[' && right == ']'; +} + +bool balanced_brackets(const std::string& str) +{ + std::stack s; + + for (char c : str) + { + if (is_opening_bracket(c)) + { + s.push(c); + } + else if (is_closing_bracket(c)) + { + if (s.empty()) + return false; + + char top = s.top(); + s.pop(); + + if (!is_corresponding_brackets(top, c)) + return false; + } + } + + return s.empty(); +} \ No newline at end of file diff --git a/Seminar06/src/forward-iterator-bst.hpp b/Seminar06/src/forward-iterator-bst.hpp new file mode 100644 index 0000000..9e3a722 --- /dev/null +++ b/Seminar06/src/forward-iterator-bst.hpp @@ -0,0 +1,260 @@ +#pragma once +#include +#include +#include +#include + +template > +class Bst +{ +private: + struct Node + { + T data; + Node* left; + Node* right; + Node(const T& data, Node* left = nullptr, Node* right = nullptr) : data(data), left(left), right(right) {} + }; + + Node* root = nullptr; + size_t size = 0; + Compare comp; // comparator instance + + Node** findMinNode(Node** root); + void free(Node* current); + Node* copy(Node* current); + +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; + + class ForwardIterator + { + private: + std::stack nodeStack; + + void pushLeft(Node* node) + { + while (node != nullptr) + { + nodeStack.push(node); + node = node->left; + } + } + + public: + ForwardIterator(Node* root = nullptr) + { + pushLeft(root); + } + + T& operator*() const + { + return nodeStack.top()->data; + } + + ForwardIterator& operator++() + { + Node* right = nodeStack.top()->right; + nodeStack.pop(); + pushLeft(right); + + return *this; + } + ForwardIterator operator++(int) + { + ForwardIterator copy(*this); + ++(*this); + return copy; + } + + bool operator!=(const ForwardIterator& other) const + { + return !(*this == other); + } + + bool operator==(const ForwardIterator& other) const + { + return (other.nodeStack.empty() && nodeStack.empty()) || (nodeStack.size() && other.nodeStack.size() && nodeStack.top() == other.nodeStack.top()); + } + }; + + ForwardIterator begin() const + { + return ForwardIterator(root); + } + + ForwardIterator end() const + { + return ForwardIterator(nullptr); + } +}; + +template +bool Bst::insert(const T& data) +{ + Node** current = &root; + + while (*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); + size++; + 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) +{ + Node** current = root; + + while ((*current)->left) + { + current = &(*current)->left; + } + return current; +} + +template +bool Bst::remove(const T& data) +{ + Node** current = &root; + + while (*current) + { + if (comp(data, (*current)->data)) + current = &(*current)->left; + else if (comp((*current)->data, data)) + current = &(*current)->right; + else + break; + } + + 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); + + *current = *rightMin; + *rightMin = (*rightMin)->right; + + (*current)->left = toDelete->left; + (*current)->right = toDelete->right; + } + delete toDelete; + size--; + return true; +} + +template +size_t Bst::getSize() const +{ + return size; +} + +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); + return res; +} + +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); + size = other.size; +} + +template +Bst& Bst::operator=(const Bst& other) +{ + if (this != &other) + { + free(root); + root = copy(other.root); + size = other.size; + 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/Seminar06/src/test-bst-iter.cpp b/Seminar06/src/test-bst-iter.cpp new file mode 100644 index 0000000..c1d6ba4 --- /dev/null +++ b/Seminar06/src/test-bst-iter.cpp @@ -0,0 +1,19 @@ +#include "forward-iterator-bst.hpp" +#include + +int main() +{ + Bst b; + b.insert(1); + b.insert(2); + b.insert(3); + b.insert(0); + b.insert(4); + b.insert(5); + b.insert(6); + + for(int x : b) + { + std::cout << x << " "; + } +} \ No newline at end of file -- cgit v1.3.1-26-gb76a