Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar09
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar09
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
4 files changed, 0 insertions, 294 deletions
-rw-r--r--Seminar09/README.md119
-rw-r--r--Seminar09/exam1.cpp35
-rw-r--r--Seminar09/media/rotations.pngbin50960 -> 0 bytes
-rw-r--r--Seminar09/solutions.cpp140
diff --git a/Seminar09/README.md b/Seminar09/README.md
deleted file mode 100644
index 3bc2307..0000000
--- a/Seminar09/README.md
+++ /dev/null
@@ -1,119 +0,0 @@
-# Дървета - част 2. Балансирани дървета, ротации и задачи върху дървета.
-
-## Минимум и максимум в дърво
-Последния семинар разглеждахме задачата за намиране на минимален или максимален елемент в дърво. Тази задача е сравнително лесна, но нека разгледаме следния случай:
-
-```cpp
-template<class T>
-T maxElem(const Tree<T>* t) {
- T result = t->data;
-
- if(t->left != nullptr)
- result = std::max(result, maxElem(t->left));
-
- if(t->right != nullptr)
- result = std::max(result, maxElem(t->right));
-
- return result;
-}
-```
-Това решение работи почти винаги. Какво става ако t e nullptr?
-
-Ако знаехме, че дървото е от тип int, лесно можехме да връщаме INT_MAX, но в случая не знаем какъв тип е скрит зад Т.
-Един от начините да се справим с този проблем е да връщаме T\* вместо Т. Така, ако дървото е nullptr ние също ще връщаме nullptr. Това е валиден начин, и може би стандартния начин по който бихме подходили в С или във версиите на С++ преди С++17.
-
-## std::optional\<T>
-std::optional\<T> е клас който в някакъв смисъл "обвива" елемент от тип Т. Както името подсказва той или има стойност.. или няма.
-Този тип се поддържа от с++17, та ако искате да го използвате бъдете сигурни, че компилирате с правилната версия на с++.
-
-Примерно, кодът използвайки std::optional би изглеждал по следния начин:
-
-```cpp
-#include<optional>
-#include"tree-utils.h"
-
-template<class T>
-std::optional<T> max(const Tree<T>* t) {
- if (t == nullptr)
- return {}; // Това означава, че std::optional<T> няма стойност
-
- std::optional<T> left = max(t->left); // Вземи макса на левия
- std::optional<T> right = max(t->left); // Вземи макса на десния
-
- T res = t->data;
- // Ако левия има value тоест дървото не е празно...
- if (left.has_value() && left.value() > res)
- res = left.value();
-
- // Аналогично за десния
- if (right.has_value() && right.value() > res)
- res = right.value();
-
- return res;
-}
-
-int main() {
- Tree<int>* t = nullptr;
- std::optional<int> result = max(t);
-
- if(result.has_value())
- std::cout << "Max element is: " << result.value() << std::endl;
- else
- std::cout << "Empty tree!!";
-}
-```
-Логиката зад std::optional далеч не идва от с++. Езици като Haskell, Rust и други поддържат подобни структури.
-
-## Балансирани дървета
-Последния семинар дефинирахме височина на дърво и се разбрахме, че това ще бъде важно понятие за нас. Намекнахме, че е желателно да държим дърветата си ниски. Едно свойство на дърветата, което ги държи сравнително ниски е **балансираността.**
-
-Двоично дърво наричаме **балансирано** ако за всеки негов възел височините на лявото поддърво и на дясното поддърво се различават **най - много с единица**.
-
-Също така дърво ще наричаме **идеално балансирано** ако за всеки негов възел броя на възлите в лявото поддърво и броя на възлите в дясното поддърво се различават най - много с единица.
-
-В балансираните и идеално балансираните дървета сложността на операциите добавяне, търсене, изтриване стават $\mathcal{O} (\log_2 n)$.
-
-С балансирани дървета ще се занимаваме много подробно следващия път. Засега само дефинираме неща, които ще ни бъдат от голяма полза при реализацията на едно такова дърво.
-
-## Ротации и запазване на балансираността
-Ротацията е операция върху балансирани двоични дървета, която запазва балансираността им.
-
-![](media/rotations.png)
-
-Ротациите обаче променят височината на лявото и дясното поддърво на корена.
-
-Нека разгледаме 1, където правим ротация около х. Височината на дясното поддърво е 1 + max(h(beta), h(gamma)).
-
-След ротацията височината на дясното поддърво е h(gamma). Следователно височината е **намаляла поне с единица**.
-
-По същата логика височината на лявото поддърво расте отново поне с единица.
-
-Разбрахме се, че ще се стараем да си държим дърветата ниски. Тези операции ще ни бъдат полезни в тази ни задача.
-## Задача първа
-Да се напише функция, която проверява дали дадено дърво е двоично наредено дърво.
-
-## Задача втора
-Да се напише функция, която от сортиран вектор построява двоично наредено дърво.
-
-## Задача трета
-Да се напише функция, която премахва възел от двоично наредено дърво.
-
-## Задача четвърта
-Да се напише функция, която проверява дали две дървета са еднакви.
-
-## Задача пета
-Да се реализират ляво и дясна ротация за произволно дърво.
-
-## Задача шеста (За домашно)
-Нека имаме двоично наредено дърво T от цели числа.
-
-```
-pred(x) = max{y | y е ключ на възел в Т и y < x} // Предшественик
-succ(x) = min{y | y е ключ на възел в T и y > x} // Наследник
-```
-
-Да се реализира pred(t, x) и succ(t, x).
-Бележка: Не е нужно х да се съдържа в дървото.
-
-## Задача седма (Контролно)
-Да се напише функция, която намира сумата на всички елементи на двоично наредено дърво от цели числа, които имат нечетен брой наследници в интервала [x, y] (т.е. сумата на броя елементи в лявото поддърво и броя елементи в дясното поддърво в интервала [x, y] е нечетно число). Нека x и y са параметри на функцията.
diff --git a/Seminar09/exam1.cpp b/Seminar09/exam1.cpp
deleted file mode 100644
index 26eb3cb..0000000
--- a/Seminar09/exam1.cpp
+++ /dev/null
@@ -1,35 +0,0 @@
-#include"../Seminar08/tree-utils.h"
-
-// pair.first -> Сумата до момента
-// pair.second - Броя на наследниците, които изпълняват условието ключовете им да влизат в интервала в поддървото
-std::pair<int, int> findSumHelper(const Tree<int>* t, int x, int y) {
- if(t == nullptr)
- return std::make_pair(0, 0);
-
- std::pair<int, int> l = std::make_pair(0, 0);
- std::pair<int, int> r = std::make_pair(0, 0);
-
- if(t->data >= x)
- l = findSumHelper(t->left, x, y);
-
- if(t->data <= y)
- r = findSumHelper(t->right, x, y);
-
- bool oddChildren = ((l.second + r.second) % 2);
-
- int sum = l.first + r.first;
- int count = l.second + r.second + (t->data >= x && t->data <= y);
-
- if(oddChildren)
- sum += t->data;
-
- return std::make_pair(sum, count);
-}
-
-int findSum(const Tree<int>* t, int x, int y) {
- return findSumHelper(t, x, y).first;
-}
-
-int main() {
-
-} \ No newline at end of file
diff --git a/Seminar09/media/rotations.png b/Seminar09/media/rotations.png
deleted file mode 100644
index 0312e29..0000000
--- a/Seminar09/media/rotations.png
+++ /dev/null
Binary files differ
diff --git a/Seminar09/solutions.cpp b/Seminar09/solutions.cpp
deleted file mode 100644
index 94958e5..0000000
--- a/Seminar09/solutions.cpp
+++ /dev/null
@@ -1,140 +0,0 @@
-#include"../Seminar08/tree-utils.h"
-#include<optional>
-#include<vector>
-#include<assert.h>
-#include<algorithm>
-
-template<class T>
-std::optional<T> getMax(const Tree<T>* t) {
- if (t == nullptr)
- return {}; // Няма стойност
-
- T res = t->data;
-
- std::optional<T> left = getMax(t->left);
- std::optional<T> right = getMax(t->right);
-
- if (left.has_value())
- res = std::max(res, left.value());
-
- if (right.has_value())
- res = std::max(res, right.value());
-
- return res;
-}
-
-bool isBSTRec(const Tree<int>* t, int min, int max) {
- if (t == nullptr)
- return true;
-
- if (t->data < min || t->data > max)
- return false;
-
- return isBSTRec(t->left, min, t->data) && isBSTRec(t->right, t->data, max);
-}
-
-bool isBST(const Tree<int>* t) {
- return isBSTRec(t, INT_MIN, INT_MAX);
-}
-
-template<class T>
-Tree<T>* buildFromRec(const std::vector<T>& v, int start, int end) {
- if (end < start)
- return nullptr;
-
- int mid = (end - start) / 2 + start;
-
- return new Tree<T>(v[mid], buildFromRec(v, start, mid - 1), buildFromRec(v, mid + 1, end));
-}
-
-template<class T>
-Tree<T>* buildFrom(const std::vector<T>& v) {
- return buildFromRec(v, 0, v.size() - 1);
-}
-
-template<class T>
-bool isSameTree(const Tree<T>* fst, const Tree<T>* snd) {
- if (!fst && !snd)
- return true;
-
- if ((fst && !snd) || (!fst && snd) || fst->data != snd->data)
- return false;
-
- return isSameTree(fst->left, snd->left) && isSameTree(fst->right, snd->right);
-}
-
-template<class T>
-Tree<T>* clone(const Tree<T>* t) {
- if (!t)
- return nullptr;
-
- return new Tree<T>(t->data, clone(t->left), clone(t->right));
-}
-
-template<class T>
-void rotateLeft(Tree<T>*& root) {
- assert(root->right != nullptr);
-
- Tree<T>* originalRight = root->right;
- root->right = originalRight->left;
- originalRight->left = root;
- root = originalRight;
-}
-
-template<class T>
-void rotateRight(Tree<T>*& root) {
- assert(root->left != nullptr);
-
- Tree<T>* originalLeft = root->left;
- root->left = originalLeft->right;
- originalLeft->right = root;
- root = originalLeft;
-}
-
-void rotationsTests() {
- std::vector<int> v;
- for (size_t i = 0; i < 100; i++)
- v.push_back(rand() % 100);
-
- std::sort(v.begin(), v.end());
-
- Tree<int>* example = buildFrom(v);
- Tree<int>* exampleClone = clone(example);
-
- // Тестваме лява ротация:
- // Тука не правя проверки за nullptr понеже не е това целта на този пример
- Tree<int>* alpha = clone(example->left);
- Tree<int>* beta = clone(example->right->left);
- Tree<int>* gamma = clone(example->right->right);
-
- rotateLeft(example);
-
- assert(isSameTree(alpha, example->left->left));
- assert(isSameTree(beta, example->left->right));
- assert(isSameTree(gamma, example->right));
-
- freeTree(alpha); freeTree(beta); freeTree(gamma);
-
- // Тествам дясна ротация
- alpha = clone(example->left->left);
- beta = clone(example->left->right);
- gamma = clone(example->right);
-
- rotateRight(example);
-
- assert(isSameTree(alpha, example->left));
- assert(isSameTree(beta, example->right->left));
- assert(isSameTree(gamma, example->right->right));
-
- freeTree(alpha); freeTree(beta); freeTree(gamma);
-
- // Лявата ротация е симетрична на дясната следователно като направим лява + дясна трябва да остане същото дърво
- assert(isSameTree(example, exampleClone));
-
- freeTree(example);
- freeTree(exampleClone);
-}
-
-int main() {
- rotationsTests();
-} \ No newline at end of file