Add Seminar08

9 files changed, 317 insertions, 1 deletions

diff --git a/README.md b/README.md
index 0c00236..836d3bd 100644
--- a/README.md
+++ b/README.md
@@ -4,4 +4,6 @@
 * Тема 3: Опашки и декове.
 * Тема 4: Динамичен масив. Свързан списък (част 1).
 * Тема 5: Итератори. std::list. Задачи за упражнение [тук най-долу](Seminar05/README.md)
-* Тема 6: Двойно свързани списъци. Задачи върху списъци. [Упражнение - реализирайте двойно свързан списък](Seminar06/DLLSkeleton.cpp)
\ No newline at end of file
+* Тема 6: Двойно свързани списъци. Задачи върху списъци. [Упражнение - реализирайте двойно свързан списък](Seminar06/DLLSkeleton.cpp)
+* Тема 7: Сортиращи алгоритми.
+* Тема 8: Дървета. Двоични дървета. Двоични наредени дървета.
\ No newline at end of file
diff --git a/Seminar08/README.md b/Seminar08/README.md
new file mode 100644
index 0000000..fcb7df9
--- /dev/null
+++ b/Seminar08/README.md
@@ -0,0 +1,193 @@
+# Дървета - част 1
+Свързан граф, който не съдържа цикли наричаме дърво. Дървета се използват от далечната 1875 година когато английски математик на име Arthur Cayley ги използва за да брои видове химични съединения.
+
+## Примери за дървета
+Вероятно всеки вече в един или друг момент се е сблъсквал с дървета. Това е дърво:
+
+![](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*. Тогава то не може да стане по - ниско от floor(log<sub>k</sub>(n)).
+
+Опитайте се да начертаете дърво с разклоненост 2 и 8 върха. Възможно ли е височината му да е по - малка от 3?
+
+## Поддървета
+Неформално, поддърво вкоренено във връх *u* е върхът *u* и всичко под него. Формалната дефиниция ще оставим за друг курс, но това е пример за поддърво, вкоренено във връх 2:
+
+![](media/subtree.png)
+
+## Двоични дървета.
+Двоичното дърво е дърво с максимална разклоненост 2. Това означава, че всеки възел има най - много две деца. В общия случай различаваме децата като ляво и дясно дете (или ляв и десен наследник). 
+За двоичните дървета можем също да си мислим като рекурсивно дефинирана структура от данни:
+* Празното дърво е двоично дърво
+* Дърво с един връх и без ребра е двоично дърво
+* Възел с ляв наследник двоично дърво и десен наследник двоично дърво е двоично дърво.
+
+Голяма част от алгоритмите върху двоичните дървета са рекурсивни точно поради този удобен начин да дефинираме двоично дърво.
+
+Дървото в пример 1 е двоично дърво. Дървото в пример 2 не е двоично дърво, понеже има възел от степен 4.
+
+Двоичните дървета поддържат операции по добавяне на елемент и премахване на елемент. Проблемът е, че нищо не знаем за елементите. Нищо не знаем за височината. Единственото което знаем е, че това е дърво с разклоненост 2.
+
+## Двоични наредени дървета
+Двоичното наредено дърво е двоично дърво за което е вярно следното **свойство:**
+
+- Нека *u* е възел в двоично наредено дърво. Стойността на всеки възел от лявото поддърво на *u* е по - малка от стойността на *u*. Стойността на всеки възел от дясното поддърво на *u* е по - голяма от стойността на *u*.
+
+Можем да имаме повтарящи се елементи, това не е проблем. Можем да ги слагаме само отляво или само отдясно, важното е да се поддържа една конвенция.
+
+Едно важно нещо, без което не можем да имаме двоично наредено дърво, е свойството на стойностите на възлите да са сравними. не можем да строим двоично наредено дърво от несравними стойности. Двоичните наредени дървета са сравнително лесни за разбиране и ползване и притежават интересни свойства, с който ще се занимаваме тепърва!
+
+## Представяне на дървета
+
+### Свързано представяне - Двоични дървета
+Свързаното представяне е ужасно удобно когато поддържаме операции като добавяне или изтриване. То ще се ползва най - често в курса, представяме двоично дърво като:
+
+```cpp
+template<class T>
+struct Tree {
+    T data;
+    Tree* left;
+    Tree* right;
+
+    Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, left {l}, right {r} {}
+}
+```
+
+От тук всеки указател от типа *Tree\<T>** е валидно дърво. Ако то е празно стойността му би била nullptr. Ако е непразно, данните записани във възела му достъпваме чрез data полето, а лявото и дясното поддърво достъпваме съответно чрез left и right.
+
+Дървото от пример 1, представено по този начин, би изглеждало така:
+
+```cpp
+Tree<int>* createExampleOne() {
+    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 isLeaf(const Tree<T>* t) {
+    return t != nullptr && r->left == nullptr && t->right == nullptr;
+}
+```
+
+### Списък на бащите
+Очевидно, чрез свързаното представяне в някакъв смисъл слизаме от корена към листата. Какво правим обаче ако искаме да се качваме от листата към корена?
+
+Нека имаме дърво с *n* върха. Върховете са номерирани с числа от 0 до *n-1*. Едно валидно номериране можем да видим в пример едно. Корена е 0 левия наследник 1, десния 2 и така, по нива, от ляво надясно им даваме индекси от 0 до *n* - 1. Разбира се, това номериране не е единствено, но някак е най - удобно.
+
+Разглеждаме масив tArray с *n* елемента за който е вярно: **В tArray[i] е записан номера на бащата на връх с номер i. Ако върхът с номер i е корен (а корена няма баща) просто пишем -1**.
+Дървото от пример 1 може да се представи чрез списък на бащите по следния начин:
+
+* [-1, 0, 0, 2, 2, 3, 3, 3]
+
+Едно от предимствата на това представяне е, че можем да представим дърво с произволна разклоненост. Все пак няма значение разклонеността, ако можем да номерираме възлите с числа от 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) байта за допълнителен указател. Но пък ако ни трябва добавяне, премахване и движение както от корен към листа така и листа корен плащаме малко памет и имаме всичко това!
+
+## Задача първа
+Да се реализира функция, която добавя елемент в двоично наредено дърво.
+
+## Задача втора
+Да се напише функция *contains(Tree\<T>* tree, const T& elem)* която връща дали елемента се съдържа в двоично дърво. Да се реализира същата функция за двоично наредено дърво.
+
+## Задача трета
+Да се напише функция *max((Tree\<T>* tree)* която връща най - големия елемент в двоично дърво. Да се реализира същата функция за двоично наредено дърво. Да се реализира функция намираща най - малкия елемент.
+
+## Задача четвърта
+Да се реализира функция, която връща височината на двоично дърво.
+
+## Задача пета
+Да се напише функция, която обхожда елементите на двоично дърво по схемата ляво-корен-дясно. (още позната като inorder traversal). Извикайте функцията върху двоично наредено дърво. Какво забелязвате?
diff --git a/Seminar08/insert-in-bst.cpp b/Seminar08/insert-in-bst.cpp
new file mode 100644
index 0000000..ac4c9f4
--- /dev/null
+++ b/Seminar08/insert-in-bst.cpp
@@ -0,0 +1,36 @@
+#include<iostream>
+#include"tree-utils.h"
+
+// Тук допускаме да има повторения. Ако искаме да няма повторения втория else ще стане else if(t->data > elem)
+template<class T>
+void insertInBST(Tree<T>*& t, const T& elem) {
+    if(t == nullptr) {
+        t = new Tree<T>(elem);
+        return;
+    }
+    else if(t->data < elem) {
+        insertInBST(t->right, elem);
+    }
+    else {
+        insertInBST(t->left, elem);
+    }
+}
+
+int main() {
+    Tree<int>* example = new Tree<int>(4, new Tree<int>(2), new Tree<int>(6));
+    
+    insertInBST(example, 1);
+    printTree(example);
+
+    // За любопитните: колко ли ще е височината на дърво от 50 случайни числа?
+    Tree<int>* secondExample = nullptr;
+    srand(time(NULL));
+    for (int i = 0; i < 50; i++)
+        insertInBST<int>(secondExample, rand() % 100);
+    
+    exportToTex(secondExample, "file.txt");
+    //-------------------------------------------------
+
+    freeTree(example);
+    freeTree(secondExample);
+}
\ No newline at end of file
diff --git a/Seminar08/media/left-child-right-sibling.png b/Seminar08/media/left-child-right-sibling.png
new file mode 100644
index 0000000..180f782
--- /dev/null
+++ b/Seminar08/media/left-child-right-sibling.png
diff --git a/Seminar08/media/stick.png b/Seminar08/media/stick.png
new file mode 100644
index 0000000..9fcc5ad
--- /dev/null
+++ b/Seminar08/media/stick.png
diff --git a/Seminar08/media/subtree.png b/Seminar08/media/subtree.png
new file mode 100644
index 0000000..5875be2
--- /dev/null
+++ b/Seminar08/media/subtree.png
diff --git a/Seminar08/media/tree-first-example.png b/Seminar08/media/tree-first-example.png
new file mode 100644
index 0000000..4fe94bf
--- /dev/null
+++ b/Seminar08/media/tree-first-example.png
diff --git a/Seminar08/media/tree-second-example.png b/Seminar08/media/tree-second-example.png
new file mode 100644
index 0000000..bf57c99
--- /dev/null
+++ b/Seminar08/media/tree-second-example.png
diff --git a/Seminar08/tree-utils.h b/Seminar08/tree-utils.h
new file mode 100644
index 0000000..26c9596
--- /dev/null
+++ b/Seminar08/tree-utils.h
@@ -0,0 +1,85 @@
+#ifndef TREE_UTIL_IMPL
+#define TREE_UTIL_IMPL
+
+#include<iostream>
+#include<string>
+#include<fstream>
+
+// Важни неща:
+
+template<class T>
+struct Tree {
+    T data;
+    Tree* left;
+    Tree* right;
+
+    Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, left {l}, right {r} {}
+};
+
+template<class T>
+void freeTree(Tree<T>* t) {
+    if(t == nullptr)
+        return;
+    freeTree(t->left);
+    freeTree(t->right);
+    delete t;
+}
+
+// Неща за мое удобство, не е нужно да ги четете:
+
+// Взето от:
+// https://stackoverflow.com/questions/36802354/print-binary-tree-in-a-pretty-way-using-c
+template<class T>
+void printBT(const std::string& prefix, const Tree<T>* node, bool isLeft) {
+    if(node != nullptr) {
+        std::cout << prefix;
+
+        std::cout << (isLeft ? "|--" : "`--" );
+
+        std::cout << node->data << std::endl;
+
+        printBT( prefix + (isLeft ? "|   " : "    "), node->left, true);
+        printBT( prefix + (isLeft ? "|   " : "    "), node->right, false);
+    }
+}
+
+template<class T>
+void printTree(const Tree<T>* node) {
+    printBT("", node, false);    
+}
+
+// Следващите две функции са малко по - красив начин да изпринтим дърво, но го конвертира къмм LaTeX документ
+// Когато извикате exportToTex("file.txt") ще ви създаде фейл с код. 
+// Пейстнете кода в overleaf.com и ще ви излезе дървото.
+
+// Не е перфектно но пък е по - удобно от конзолата. Това е за демонстрации, не е нужно да го учите или разбирате.
+template<class T>
+void recFillFileStream(std::ofstream& outFile, const Tree<T>* r) {
+	if(r == nullptr)
+		return;
+
+	outFile << "[" << r->data << " ";
+	recFillFileStream(outFile, r->left);
+	recFillFileStream(outFile, r->right);
+
+	outFile << "]";
+}
+
+template<class T>
+void exportToTex(const Tree<T>* root, const char* filePath) {
+	std::ofstream outFile(filePath, std::ios::trunc);
+
+	outFile << "\\documentclass[tikz,border=10pt]{standalone}" << std::endl;
+	outFile << "\\usepackage[linguistics]{forest}" << std::endl;
+	outFile << "\\begin{document}" << std::endl;
+	outFile << "\\begin{forest}" << std::endl;
+
+	recFillFileStream(outFile, root);
+
+	outFile << "\\end{forest}";
+	outFile << "\\end{document}";
+
+    outFile.close();
+}
+
+#endif
\ No newline at end of file