From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar09/README.md | 119 ---------------------------------------------------- 1 file changed, 119 deletions(-) delete mode 100644 Seminar09/README.md (limited to 'Seminar09/README.md') 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 -T maxElem(const Tree* 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\ -std::optional\ е клас който в някакъв смисъл "обвива" елемент от тип Т. Както името подсказва той или има стойност.. или няма. -Този тип се поддържа от с++17, та ако искате да го използвате бъдете сигурни, че компилирате с правилната версия на с++. - -Примерно, кодът използвайки std::optional би изглеждал по следния начин: - -```cpp -#include -#include"tree-utils.h" - -template -std::optional max(const Tree* t) { - if (t == nullptr) - return {}; // Това означава, че std::optional няма стойност - - std::optional left = max(t->left); // Вземи макса на левия - std::optional 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* t = nullptr; - std::optional 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 са параметри на функцията. -- cgit v1.3.1-26-gb76a