From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar08/README.md | 193 ---------------------- Seminar08/height.cpp | 14 -- Seminar08/inorder-traversal.cpp | 23 --- Seminar08/insert-in-bst.cpp | 36 ----- Seminar08/media/left-child-right-sibling.png | Bin 22100 -> 0 bytes Seminar08/media/stick.png | Bin 13709 -> 0 bytes Seminar08/media/subtree.png | Bin 32004 -> 0 bytes Seminar08/media/tree-first-example.png | Bin 16135 -> 0 bytes Seminar08/media/tree-second-example.png | Bin 20847 -> 0 bytes Seminar08/min-max-elem.cpp | 64 -------- Seminar08/tree-utils.h | 230 --------------------------- 11 files changed, 560 deletions(-) delete mode 100644 Seminar08/README.md delete mode 100644 Seminar08/height.cpp delete mode 100644 Seminar08/inorder-traversal.cpp delete mode 100644 Seminar08/insert-in-bst.cpp delete mode 100644 Seminar08/media/left-child-right-sibling.png delete mode 100644 Seminar08/media/stick.png delete mode 100644 Seminar08/media/subtree.png delete mode 100644 Seminar08/media/tree-first-example.png delete mode 100644 Seminar08/media/tree-second-example.png delete mode 100644 Seminar08/min-max-elem.cpp delete mode 100644 Seminar08/tree-utils.h (limited to 'Seminar08') diff --git a/Seminar08/README.md b/Seminar08/README.md deleted file mode 100644 index a61b2bd..0000000 --- a/Seminar08/README.md +++ /dev/null @@ -1,193 +0,0 @@ -# Дървета - част 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*. Тогава то не може да стане по - ниско от $\lfloor \log_k n \rfloor$. - -Опитайте се да начертаете дърво с разклоненост 2 и 8 върха. Възможно ли е височината му да е по - малка от 3? - -## Поддървета -Неформално, поддърво вкоренено във връх *u* е върхът *u* и всичко под него. Формалната дефиниция ще оставим за друг курс, но това е пример за поддърво, вкоренено във връх 2: - -![](media/subtree.png) - -## Двоични дървета. -Двоичното дърво е дърво с максимална разклоненост 2. Това означава, че всеки възел има най - много две деца. В общия случай различаваме децата като ляво и дясно дете (или ляв и десен наследник). -За двоичните дървета можем също да си мислим като рекурсивно дефинирана структура от данни: -* Празното дърво е двоично дърво -* Дърво с един връх и без ребра е двоично дърво -* Възел с ляв наследник двоично дърво и десен наследник двоично дърво е двоично дърво. - -Голяма част от алгоритмите върху двоичните дървета са рекурсивни точно поради този удобен начин да дефинираме двоично дърво. - -Дървото в пример 1 е двоично дърво. Дървото в пример 2 не е двоично дърво, понеже има възел от степен 4. - -Двоичните дървета поддържат операции по добавяне на елемент и премахване на елемент. Проблемът е, че нищо не знаем за елементите. Нищо не знаем за височината. Единственото което знаем е, че това е дърво с разклоненост 2. - -## Двоични наредени дървета -Двоичното наредено дърво е двоично дърво за което е вярно следното **свойство:** - -- Нека *u* е възел в двоично наредено дърво. Стойността на всеки възел от лявото поддърво на *u* е по - малка от стойността на *u*. Стойността на всеки възел от дясното поддърво на *u* е по - голяма от стойността на *u*. - -Можем да имаме повтарящи се елементи, това не е проблем. Можем да ги слагаме само отляво или само отдясно, важното е да се поддържа една конвенция. - -Едно важно нещо, без което не можем да имаме двоично наредено дърво, е свойството на стойностите на възлите да са сравними. не можем да строим двоично наредено дърво от несравними стойности. Двоичните наредени дървета са сравнително лесни за разбиране и ползване и притежават интересни свойства, с който ще се занимаваме тепърва! - -## Представяне на дървета - -### Свързано представяне - Двоични дървета -Свързаното представяне е ужасно удобно когато поддържаме операции като добавяне или изтриване. То ще се ползва най - често в курса, представяме двоично дърво като: - -```cpp -template -struct Tree { - T data; - Tree* left; - Tree* right; - - Tree(T data, Tree* l = nullptr, Tree* r = nullptr) : data {data}, left {l}, right {r} {} -} -``` - -От тук всеки указател от типа *Tree\\** е валидно дърво. Ако то е празно стойността му би била nullptr. Ако е непразно, данните записани във възела му достъпваме чрез data полето, а лявото и дясното поддърво достъпваме съответно чрез left и right. - -Дървото от пример 1, представено по този начин, би изглеждало така: - -```cpp -Tree* createExampleOne() { - 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 isLeaf(const Tree* t) { - return t != nullptr && t->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, 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) байта за допълнителен указател. Но пък ако ни трябва добавяне, премахване и движение както от корен към листа така и листа корен плащаме малко памет и имаме всичко това! - -## Задача първа -Да се реализира функция, която добавя елемент в двоично наредено дърво. - -## Задача втора -Да се напише функция *contains(Tree\\* tree, const T& elem)* която връща дали елемента се съдържа в двоично дърво. Да се реализира същата функция за двоично наредено дърво. - -## Задача трета -Да се напише функция *max((Tree\\* tree)* която връща най - големия елемент в двоично дърво. Да се реализира същата функция за двоично наредено дърво. Да се реализира функция намираща най - малкия елемент. - -## Задача четвърта -Да се реализира функция, която връща височината на двоично дърво. - -## Задача пета -Да се напише функция, която обхожда елементите на двоично дърво по схемата ляво-корен-дясно. (още позната като inorder traversal). Извикайте функцията върху двоично наредено дърво. Какво забелязвате? diff --git a/Seminar08/height.cpp b/Seminar08/height.cpp deleted file mode 100644 index c115228..0000000 --- a/Seminar08/height.cpp +++ /dev/null @@ -1,14 +0,0 @@ -#include"tree-utils.h" -#include - -template -size_t height(const Tree* tree) { - if (!tree) - return 0; - - return 1 + std::max(height(tree->left), height(tree->right)); -} - -int main(){ - -} diff --git a/Seminar08/inorder-traversal.cpp b/Seminar08/inorder-traversal.cpp deleted file mode 100644 index c9a9bd6..0000000 --- a/Seminar08/inorder-traversal.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include "tree-utils.h" - -template -void inorderTraversal(const Tree *tree) { - if (tree == nullptr) { - return; - } - - inorderTraversal(tree->left); - std::cout << tree->data << ' '; - inorderTraversal(tree->right); -} - -int main() { - Tree *root = new Tree(8, new Tree(3, new Tree(1), new Tree(6, new Tree(4), new Tree(7))), new Tree(10, nullptr, new Tree(14, new Tree(13)))); - - inorderTraversal(root); //изпечатва елементите на дървото сортирано - std::cout << '\n'; - printTree(root); - - freeTree(root); - return 0; -} \ No newline at end of file diff --git a/Seminar08/insert-in-bst.cpp b/Seminar08/insert-in-bst.cpp deleted file mode 100644 index ac4c9f4..0000000 --- a/Seminar08/insert-in-bst.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include -#include"tree-utils.h" - -// Тук допускаме да има повторения. Ако искаме да няма повторения втория else ще стане else if(t->data > elem) -template -void insertInBST(Tree*& t, const T& elem) { - if(t == nullptr) { - t = new Tree(elem); - return; - } - else if(t->data < elem) { - insertInBST(t->right, elem); - } - else { - insertInBST(t->left, elem); - } -} - -int main() { - Tree* example = new Tree(4, new Tree(2), new Tree(6)); - - insertInBST(example, 1); - printTree(example); - - // За любопитните: колко ли ще е височината на дърво от 50 случайни числа? - Tree* secondExample = nullptr; - srand(time(NULL)); - for (int i = 0; i < 50; i++) - insertInBST(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 deleted file mode 100644 index 180f782..0000000 Binary files a/Seminar08/media/left-child-right-sibling.png and /dev/null differ diff --git a/Seminar08/media/stick.png b/Seminar08/media/stick.png deleted file mode 100644 index 9fcc5ad..0000000 Binary files a/Seminar08/media/stick.png and /dev/null differ diff --git a/Seminar08/media/subtree.png b/Seminar08/media/subtree.png deleted file mode 100644 index 5875be2..0000000 Binary files a/Seminar08/media/subtree.png and /dev/null differ diff --git a/Seminar08/media/tree-first-example.png b/Seminar08/media/tree-first-example.png deleted file mode 100644 index 4fe94bf..0000000 Binary files a/Seminar08/media/tree-first-example.png and /dev/null differ diff --git a/Seminar08/media/tree-second-example.png b/Seminar08/media/tree-second-example.png deleted file mode 100644 index bf57c99..0000000 Binary files a/Seminar08/media/tree-second-example.png and /dev/null differ diff --git a/Seminar08/min-max-elem.cpp b/Seminar08/min-max-elem.cpp deleted file mode 100644 index cbd8560..0000000 --- a/Seminar08/min-max-elem.cpp +++ /dev/null @@ -1,64 +0,0 @@ -#include "tree-utils.h" -#include - -// for regular binary trees -template -T max_elem(Tree *tree) { - T res = tree->data; - - if (tree->left != nullptr) { - res = std::max(res, max_elem(tree->left)); - } - if (tree->right != nullptr) { - res = std::max(res, max_elem(tree->right)); - } - - return res; -} - -template -T min_elem(Tree *tree) { - T res = tree->data; - - if (tree->left != nullptr) { - res = std::min(res, min_elem(tree->left)); - } - if (tree->right != nullptr) { - res = std::min(res, min_elem(tree->right)); - } - - return res; -} - -// for binary search trees -template -T max_elem_bst(Tree *tree) { - while (tree->right != nullptr) - tree = tree->right; - - return tree->data; -} - -template -T min_elem_bst(Tree *tree) { - while (tree->left != nullptr) - tree = tree->left; - - return tree->data; -} - -int main() { - Tree *regularTree = new Tree(2, new Tree(3, new Tree(4), new Tree(5)), new Tree(13, new Tree(7), new Tree(8))); - printTree(regularTree); - std::cout << "Maximum element in regular binary tree: " << max_elem(regularTree) << '\n'; - std::cout << "Minimum element in regular binary tree: " << min_elem(regularTree) << '\n'; - - Tree *binarySearchTree = new Tree(8, new Tree(3, new Tree(1), new Tree(6, new Tree(4), new Tree(7))), new Tree(10, nullptr, new Tree(14, new Tree(13)))); - printTree(binarySearchTree); - std::cout << "Maximum element in bs tree: " << max_elem_bst(binarySearchTree) << '\n'; - std::cout << "Minimum element in bs tree: " << min_elem_bst(binarySearchTree) << '\n'; - - freeTree(regularTree); - freeTree(binarySearchTree); - return 0; -} \ No newline at end of file diff --git a/Seminar08/tree-utils.h b/Seminar08/tree-utils.h deleted file mode 100644 index 3ce0d93..0000000 --- a/Seminar08/tree-utils.h +++ /dev/null @@ -1,230 +0,0 @@ -#ifndef TREE_UTIL_IMPL -#define TREE_UTIL_IMPL - -#include -#include -#include -#include - -// Важни неща: -template -struct Tree { - T data; - Tree* left; - Tree* right; - - Tree(T data, Tree* l = nullptr, Tree* r = nullptr) : data{ data }, left{ l }, right{ r } {} -}; - -template -void freeTree(Tree* t) { - if (t == nullptr) - return; - freeTree(t->left); - freeTree(t->right); - delete t; -} - -template -void insertInBST(Tree*& t, const T& elem, bool hasDuplicates = true) { - if (t == nullptr) { - t = new Tree(elem); - return; - } - else if (t->data < elem) { - insertInBST(t->right, elem, hasDuplicates); - } - else if ((t->data > elem) || hasDuplicates) { - insertInBST(t->left, elem, hasDuplicates); - } -} - -template -const Tree* getMinNode(const Tree* t) { - assert(t != nullptr); - - const Tree* iter = t; - - while (iter->left) { - iter = iter->left; - } - return iter; -} - -template -bool removeElement(Tree*& t, const T& elem) { - if (t == nullptr) - return false; - - if (t->data > elem) { - return removeElement(t->left, elem); - } - else if (t->data < elem) { - return removeElement(t->right, elem); - } - - // Намерили сме елемента - if (!t->left && !t->right) { // Листо - delete t; - t = nullptr; // !! - } - else if (!t->left && t->right) { // Има само дясно поддърво - Tree* toDelete = t; - t = t->right; - delete toDelete; - } - else if (t->left && !t->right) { // Има само ляво поддърво - Tree* toDelete = t; - t = t->left; - delete toDelete; - } - else { // Вътрешен връх. - T newData = getMinNode(t->right)->data; - t->data = newData; - removeElement(t->right, newData); - } - return true; -} - -template -bool containsBST(const Tree* t, const T& elem) { - if (t == nullptr) - return false; - - if (t->data == elem) - return true; - - if (t->data < elem) - return containsBST(t->right, elem); - - return containsBST(t->left, elem); -} - - -// За по - любопитните премахване на възел -// само с пренасочване на указатели и без копие на T -template -void innerVertexRemoveCase(Tree*& inVertex) { - assert(inVertex && inVertex->left && inVertex->right); - - Tree** minNode = &inVertex->right; - Tree** minNodeParent = &inVertex; - - bool firstGoingDown = true; - - while ((*minNode)->left) { - minNode = &(*minNode)->left; - - minNodeParent = firstGoingDown ? &(*minNodeParent)->right : &(*minNodeParent)->left; - - firstGoingDown = false; - } - - Tree* originalRight = (*minNode)->right; - - (*minNode)->left = inVertex->left; - - if (!firstGoingDown) - (*minNode)->right = inVertex->right; - - Tree* toDelete = inVertex; - - inVertex = (*minNode); - - if (!firstGoingDown) - (*minNodeParent)->left = originalRight; - - delete toDelete; -} - -template -bool removeElementPointerSwap(Tree*& t, const T& elem) { - if (t == nullptr) - return false; - - if (t->data > elem) { - return removeElementPointerSwap(t->left, elem); - } - else if (t->data < elem) { - return removeElementPointerSwap(t->right, elem); - } - - // Намерили сме елемента - if (!t->left && !t->right) { // Листо - delete t; - t = nullptr; - } - else if (!t->left && t->right) { // Има само дясно поддърво - Tree* toDelete = t; - t = t->right; - delete toDelete; - } - else if (t->left && !t->right) { // Има само ляво поддърво - Tree* toDelete = t; - t = t->left; - delete toDelete; - } - else { // Вътрешен връх. - innerVertexRemoveCase(t); - } - return true; -} - -// Неща за мое удобство, не е нужно да ги четете: - -// Взето от: -// https://stackoverflow.com/questions/36802354/print-binary-tree-in-a-pretty-way-using-c -template -void printBT(const std::string& prefix, const Tree* 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 -void printTree(const Tree* node) { - printBT("", node, false); -} - -// Следващите две функции са малко по - красив начин да изпринтим дърво, но го конвертира къмм LaTeX документ -// Когато извикате exportToTex("file.txt") ще ви създаде фейл с код. -// Пейстнете кода в overleaf.com и ще ви излезе дървото. - -// Не е перфектно но пък е по - удобно от конзолата. Това е за демонстрации, не е нужно да го учите или разбирате. -template -void recFillFileStream(std::ofstream& outFile, const Tree* r) { - if (r == nullptr) - return; - - outFile << "[" << r->data << " "; - recFillFileStream(outFile, r->left); - recFillFileStream(outFile, r->right); - - outFile << "]"; -} - -template -void exportToTex(const Tree* 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 -- cgit v1.3.1-26-gb76a