Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-11-20 15:37:03 -0500
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-11-20 15:37:03 -0500
Files551a81327303eb2d8458b1fdf03327aa31a2fa0c
Data-structures-and-algorithms-3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69.tar
Data-structures-and-algorithms-3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69.tar.gz
Data-structures-and-algorithms-3e16c3a1d047aca54d4d7134d5f5fb1cbd6acd69.zip
Parent98f6872efa0cd02e892ed5d7b836c6929d5c0e10 (diff)
Add Seminar06
9 files changed, 627 insertions, 0 deletions
-rw-r--r--Seminar06/README.md305
-rw-r--r--Seminar06/media/left-child-right-sibling.pngbin0 -> 22100 bytes
-rw-r--r--Seminar06/media/stick.pngbin0 -> 13709 bytes
-rw-r--r--Seminar06/media/subtree.pngbin0 -> 32004 bytes
-rw-r--r--Seminar06/media/tree-first-example.pngbin0 -> 16135 bytes
-rw-r--r--Seminar06/media/tree-second-example.pngbin0 -> 20847 bytes
-rw-r--r--Seminar06/src/balanced-brackets.cpp43
-rw-r--r--Seminar06/src/forward-iterator-bst.hpp260
-rw-r--r--Seminar06/src/test-bst-iter.cpp19
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 <iostream>
+#include <queue>
+
+int main()
+{
+ std::queue<int> 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 <queue>
+#include <vector>
+
+int main()
+{
+ std::queue<int, std::vector<int>> q;
+}
+```
+
+## Структура от данни стек.
+Абстрактната структура от данни стек поддържа следните операции:
+
+* push(x) - Добавя елемент към колекцията.
+* pop() - Премахва последния добавен елемент.
+* top() - Връща последния добавен елемент.
+* size() - Връща броя на елементите на стека.
+
+Стекът имплементира Last-In First-Out стратегия. За стека можем да си мислим като купчина чинии наредени една върху друга. Можем да премахнем единствено най - горната чиния (без да счупим нещо).
+
+В STL има готова имплементация на стек - `std::stack`. Нека разгледаме следния пример:
+```cpp
+#include <stack>
+#include <iostream>
+
+int main()
+{
+ std::stack<int> 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<class T>
+struct Tree
+{
+ T data;
+ Tree<T>* left;
+ Tree<T>* right;
+
+ Tree(const T& data_, Tree<T>* l = nullptr, Tree<T>* r = nullptr) :
+ data (data_),
+ left (l),
+ right (r) {}
+};
+```
+
+От тук представяме дървото като указател към обект от тип Tree.
+
+Дървото от пример 1, представено по този начин, би изглеждало така:
+
+```cpp
+Tree<int>* create_exaple_one() {
+ return new Tree<int>(
+ 0, // Корена
+ new Tree<int>(1), // Лявото поддърво
+ new Tree<int>( // Дясното поддърво
+ 2,
+ new Tree<int>(3, new Tree<int>(5), new Tree<int>(6)),
+ new Tree<int>(4, nullptr, new Tree<int>(7))
+ )
+ );
+}
+```
+
+Как можем да проверим дали възел е листо?
+```cpp
+template<class T>
+bool is_leaf(const Tree<T>* 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<class T>
+struct Tree{
+ T data;
+ Tree<T>* leftChild;
+ Tree<T>* rightSibling;
+};
+```
+
+Така от корена можем да достъпим кой да е връх на произволно разклоненото дърво.
+![](media/left-child-right-sibling.png)
+
+Тук в leftChild указателя на 2 ще е записан адреса на 4. В rightSibling указателя на 2 ще е записан 3. Ако някой възел няма ляво дете или десен брат, то указателя просто е nullptr.
+Предимството е, че за същата памет, с която представихме двоично дърво, можем да представим дърво с произволна разклоненост. Недостатъка е, че имаме последователен достъп до децата. Тоест ако искам да взема третото дете на връх *u* първо ще трябва да сляза до най - лявото му дете и да се предвижа две позиции надясно. Ако често имаме нужда да четем дете на позиция k това може би не би било най - подходящото представяне.
+
+### Чрез вектор от децата
+Разглеждаме следното представяне:
+```cpp
+template<class T>
+struct Tree {
+ T data;
+ std::vector<Tree<T>*> children;
+};
+```
+Ако искаме да вземем третото дете на връх *u* просто правим u->children[2]. Предимството е очевидно - нямаме последователен достъп до децата. Недостатъкът е, че възлите започват да заемат повече памет. Размера на вектора (в x64) е 32 байта. Ако възлите ни са от тип int то размера на структурата би бил 40 байта.
+Вектора ще направи алокации, което също в някакъв смисъл забавя програмата. Но пък веднъж като построим дървото имаме бърз достъп до децата.
+
+### Чрез допълнителен parent указател
+Представянето чрез масив на бащите беше хубаво, но проблемът е, че трудно добавяме и изваждаме елемент от колекцията. Ако искаме да имаме дърво което поддържа добавяне и изтриване и също така може да намира родителя си, то просто добавяме още един указател.
+```cpp
+template<class T>
+struct Tree {
+ T data;
+ Tree* parent;
+ Tree* left;
+ Tree* right;
+
+ Tree(T data, Tree<T>* p = nullptr, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, parent {p}, left {l}, right {r} {}
+}
+```
+Тук проблемът е, че отново плащаме цената от 4 (или 8) байта за допълнителен указател. Но пък ако ни трябва добавяне, премахване и движение както от корен към листа така и листа корен плащаме малко памет и имаме всичко това!
+
+## Задача първа
+Да се напише функция, който принтира всички листа на дърво.
+
+## Задача втора
+Да се напише функция, която принтира всички пътища от корена до което и да е листо.
+
+## Задача трета
+Да се напише функция *max((Tree\<T>\* 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
--- /dev/null
+++ b/Seminar06/media/left-child-right-sibling.png
Binary files differ
diff --git a/Seminar06/media/stick.png b/Seminar06/media/stick.png
new file mode 100644
index 0000000..9fcc5ad
--- /dev/null
+++ b/Seminar06/media/stick.png
Binary files differ
diff --git a/Seminar06/media/subtree.png b/Seminar06/media/subtree.png
new file mode 100644
index 0000000..5875be2
--- /dev/null
+++ b/Seminar06/media/subtree.png
Binary files differ
diff --git a/Seminar06/media/tree-first-example.png b/Seminar06/media/tree-first-example.png
new file mode 100644
index 0000000..4fe94bf
--- /dev/null
+++ b/Seminar06/media/tree-first-example.png
Binary files differ
diff --git a/Seminar06/media/tree-second-example.png b/Seminar06/media/tree-second-example.png
new file mode 100644
index 0000000..bf57c99
--- /dev/null
+++ b/Seminar06/media/tree-second-example.png
Binary files 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 <stack>
+#include <string>
+
+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<char> 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 <iostream>
+#include <functional>
+#include <stack>
+#include <vector>
+
+template <class T, typename Compare = std::less<T>>
+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<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;
+
+ class ForwardIterator
+ {
+ private:
+ std::stack<Node*> 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 <class T, typename Compare>
+bool Bst<T, Compare>::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 <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)
+{
+ Node** current = root;
+
+ while ((*current)->left)
+ {
+ current = &(*current)->left;
+ }
+ return current;
+}
+
+template <class T, typename Compare>
+bool Bst<T, Compare>::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 <class T, typename Compare>
+size_t Bst<T, Compare>::getSize() const
+{
+ return size;
+}
+
+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);
+ return res;
+}
+
+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);
+ size = other.size;
+}
+
+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);
+ size = other.size;
+ 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/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 <iostream>
+
+int main()
+{
+ Bst<int> 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