diff options
Cleanup
4 files changed, 0 insertions, 294 deletions
| -rw-r--r-- | Seminar09/README.md | 119 | ||||
| -rw-r--r-- | Seminar09/exam1.cpp | 35 | ||||
| -rw-r--r-- | Seminar09/media/rotations.png | bin | 50960 -> 0 bytes | |||
| -rw-r--r-- | Seminar09/solutions.cpp | 140 |
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)$. - -С балансирани дървета ще се занимаваме много подробно следващия път. Засега само дефинираме неща, които ще ни бъдат от голяма полза при реализацията на едно такова дърво. - -## Ротации и запазване на балансираността -Ротацията е операция върху балансирани двоични дървета, която запазва балансираността им. - - - -Ротациите обаче променят височината на лявото и дясното поддърво на корена. - -Нека разгледаме 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 Binary files differdeleted file mode 100644 index 0312e29..0000000 --- a/Seminar09/media/rotations.png +++ /dev/null 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 |
