# AVL дървета. ## Целта за днес | Операции | build(x) | find(x) | insert/delete | min/max | prev/next | | ----------- | ----------- |----------- | ----------- | ---------- | --------- | | Binary tree | O(nlog(n)) | O(h) | O(h) | O(h) | O(h) | | AVL tree | O(nlog(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | ## Балансирани дървета Двоично дърво, което поддържа log(n) височина при динамични операции се нарича **балансирано дърво**. Има много схеми за балансиране на дървета което влезе и съществуването на различни видове балансирани дървета (Red-Black tree, 2-3 Tree...) Първата схема за балансиране на дървета е предложена през 1962 година от Andelson-Velsky и Landis от където идва и името на AVL дървото. Баланс фактор на възел k определяме като: bf(k) = h(k->left) - h(k->right). Целта ни е за всеки възел k: bf(k) да е в множеството {-1, 0, 1}. Трябва да поддържаме това свойство при всяко добавяне или премахване на възел. Тук на помощ идват ротациите! Тяхната реализация както и тестове за тяхната коректност можете да намерите [тук](https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Seminar09/solutions.cpp#L75). ## Как разбираме, че сме нарушили балансираността на възел? Ако bf(k) не е в {-1, 0, 1} то тогава сме нарушили балансираността. Трябва ни начин да пресмятаме баланс фактора на всечи възел колкото се може по - бързо. Както в много неща в този курс, за да пресмятаме бързо баланс фактора на възел ще жертваме малко памет и ще записваме височината на поддървото във всеки възел. Структурата би изглеждала така: ```cpp template struct Node { T data; Node* left; Node* right; int height; Node(const T& d, Node* l, Node* r, int h) : data {d}, left {l}, right {r}, height{h} {} }; ``` Сега, За константно време можем да смятаме баланс фактора: ```cpp template int getHeight(const Node* r) { if(r == nullptr) return 0; return r->height; } template int getBalanceFactor(const Node* r) { if(r == nullptr) return 0; return getHeight(r->right) - getHeight(r->left); } ``` ## insert Искаме да напишем операция, която за логаритмично време добавя елемент в дървото и запазва неговата балансираност. В началото започваме по стандартния начин - рекурсивно намираме къде да добавим елемента и го добавяме като листо. След това обаче става интересно - какво става ако този елемент чупи балансираността. Той увеличава височината на (логаритмичен) брой поддървета. Използваме факта, че рекурсивно сме слезли до някое листо и когато излизаме от рекурсията чрез ротации поправяме балансираността на дървото. При добавяне на елемент ни се налага да направим **най - много две ротации** Също така при добавяне на елемент трябва да променяме височината. Разбрахме се, че я пазим, а това, че добавяме елемент я променя. За щастие това може да стане в константно време: ```cpp template void updateHeight(Node*& r) { if(r == nullptr) return; r->height = getHeight(r->left) + getHeight(r->right) + 1; } ``` Алгоритъмът за добавяне би изглеждал по следния начин: ```cpp template void addElement(Node*& root, const T& elem) { // Стигнали сме до дъното на рекурсията if(root == nullptr) { root = new Node(elem, nullptr, nullptr, 1); return; } else if(root->data < elem) { addElement(root->right, elem); // добавяме елемента, но работата ни не е приключила balanceRight(root); // balance проверява дали има дисбаланс в дървото което променихме // и ако има го коригира! updateHeight(root); // Добавихме възел, все пак трябва да си оправим височината! } else if(root->data > elem) { // Аналогично на горния случай. addElement(root->left, elem); balanceLeft(root); updateHeight(root); } } ``` Можем да оптимизираме този алгоритъм, но засега целта е да разберем какво се случва. Логиката по добавянето е почти същата като при стандартното двоично наредено дърво, но този път имаме функцията balance(r); Да разгледаме какви случаи имаме при дисбалансираността. Нега разгледаме случая в който дясното поддърво е дисбалансирано. Нещата за лявото са абсолютно симетрични! Имаме три случая за баланс фактора на дясното поддърво. * Случай 1 - той е 1 ![](media/avl-disbalance.png) Тук виждаме, че просто лява ротация около корена ни свърши работа, супер. * Случай 2 - той е 0 ![](media/avl-disbalance-0.png) Тук също просто лява ротация ни свърши работа. * Случай 3 - той е -1 ![](media/avl-disbalance-1.png) Е, какво направихме с тази лява ротация.. Само направихме нещата по - лоши. Лявата ротация не ни върши работа тук и трябва на намерим друг начин да се справим. В предните два случая нещата с лява ротация работиха. Дали има начин да отида в някой от тях? Забелязвам, че ако направя дясна ротация около корена на дясното поддърво (с височина k + 1) вече баланс фактора на дясното поддърво ще бъде 1. Това обаче е случай 1, който знаем, че с лява ротация работи. Тоест просто правя дясна ротация около корена на дясното поддърво (за да отида в сл. 1) и после правя лява ротация около корена. Нарисувайте си по подобен на примерите начин как ще изглежда това. Хайде да го напишем на код: ```cpp template void balanceRight(Node*& root) { // Това не трябва да се случва! assert(root != nullptr); int rootBalance = getBalanceFactor(root); int rightSubTreeBalance = getBalanceFactor(root->right); // Както видяхме в картинката десния дисбаланс е със стойност 2 :) if(balance == 2) { // Това е гадния случай в който ми трябва още една ротация. if(rightSubTreeBalance == -1) { rotateRight(root->right); // Променям височините на двете поддървета, които са засегнати от ротацията updateHeight(root->right->right); updateHeight(root->right); } // Сега вече или съм в случай 1 или в случай 2 и просто си правя лява ротация rotateLeft(root); // Отново актуализирам височините на възлите засегнати от ротацията updateHeight(root->left); updateHeight(root); } } ``` Проверката за ляв дисбаланс ще изглежда по симетричен начин. ## Премахване на елемент При стандартните дървета имахме следния алгоритъм: 1. Намери елемента. Ако го няма върни false. 2. Ако елемента е листо просто го изтрий 3. Ако елемента има само ляво или само дясно поддърво просто лявото (или дясното) поддърво заемат неговото място а той бива изтрит. 4. В противен случай намери най малкия елемент в дясното му поддърво. Този елемент става корен а ние изтриваме елемента, който ни беше зададено да изтрием. В този алгоритъм обаче винаги се премахва едно листо. Това значи, че височината на логаритмичен брой поддървета ще се промени, а на нас това не ни харесва. Това което трябва да добавим в алгоритъма е балансиране на пътя, по който сме преминали. Също така трябва динамично да променяме височините така, че те да са коректни. ```cpp template bool removeElement(Node*& root, const T& elem) { if(root == nullptr) return false; if(root->data < elem) { bool res = removeElement(root->right, elem); // Не е възможно да има десен дисбаланс, понеже променяме дясното поддърво updateHeight(root); balanceLeft(root); return res; } else if(root->data > elem) { bool res = removeElement(root->left, elem); updateHeight(root); balanceRight(root); return res; } if(!root->left && !root->right) { delete root; root = nullptr; } else if(root->left && !root->right) { Node* toDelete = root; root = root->left; delete toDelete; updateHeight(root); } else if(!root->left && root->right) { Node* toDelete = root; root = root->right; delete toDelete; updateHeight(root); } else { // Това е неефикасно. root->data = findMinElement(root->right)->data; removeElement(root->right, root->data); updateHeight(root); balanceLeft(root); } return true; } ``` Коментара "това е неефикасно" има за цел да намекне, че тази реализация на алгоритъма за премахване може да бъде подобрена. Проблемът е, че T може да е всякакъв тип, вкючително и доста тежък за копиране тип. Също така слизаме да намерим минималния възел един път и след това слизаме още един път за да го премахнем. Това са две разходки, което може да се подобри. Решението може да стане само с разместване на указатели. Причината да не го реализираме така тук е за да може да се концентрирате не толкова върху техническата реализация а върху самия алгоритъм. [Тук](https://github.com/stoychoX/AVL-vs-SkipList/blob/main/AVL/AVLTree.hpp#L409) можете да погледнете примерен начин възел да се премахне само чрез разместване на указатели. Това не е единствения начин, можете да се опитате да го направите сами и да pull-request-нете кода за да го обсъдим. ## Дърветата и stl В стандартната библиотека на c++ няма нещо като std::tree\. Въпреки това stl ни предоставя обекти, които в реализацията си използват балансирани дървета. ### std::set Сет (или множество) е асоциативен контейнер който съдържа сортирана последователност от обекти от тип Т. Търсене, премахване и добавяне имат логаритмична сложност. В стл сетовете се имплементират чрез червено черни дървета, които също като AVL дървото поддържат логаритмична височина (използвайки друга схема за балансиране). Както в множествата, обектите в сета **са уникални**. За него можете също да си мислите като за дърво, което при insert не допуска повторения на ключове. Да видим бърз пример: ```cpp #include #include int main() { std::set s; for (size_t i = 0; i < 10; i++) s.insert(i); // find метода връща итератор към елемента std::set::iterator elem = s.find(4); // Това извежда 4 std::cout << *elem << " "; // Отиваме на следващия елемент... Но колекцията е сортирана! ++elem; // Това извежда 5 std::cout << *elem; } ``` Супер, но какво връща find когато елемента го няма? Как изобщо да премахвам елемент? Следващия пример отговаря на тези въпроси. ```cpp #include #include int main() { std::set s; // Вкарваме 10 пъти 5, но елементите нямат повторения! for (size_t i = 0; i < 10; i++) s.insert(5); // Премахваме 5 s.erase(5); std::set::iterator it = s.find(5); // Когато елемента го няма в множеството просто връща end() итератора (както е с много други обекти в stl) if (it == s.end()) std::cout << "Element not found!"; } ``` Та обекта го няма - връща end итератора. Лесна работа. Супер сега обаче наредбата не ми харесва. Искам колекцията ми да е сортирана в обратен ред. Сортировката зависеше единствено от компаратор функцията (rли релацията по която сортирам, която в първия пример по подразбиране е <). Дали не мога да накарам моя сет да сортира по >? Това би станало по следния начин: ```cpp #include #include int main() { // std::greater е структура с оператор() // Дали ще можем ние да си напишем наша структура с operator() // И да я пуснем като comparator? Опитайте! std::set> s; for (size_t i = 0; i < 10; i++) s.insert(i); for (auto x : s) std::cout << x << " "; } ``` Често ни се налага да държим в множество обекти които не са числа а примерно някакви структури или класове. Да разгледаме следния код: ```cpp #include struct Entity { int x; int y; }; int main() { std::set s; s.insert({1, 1}); } ``` Тази програма ще ни върне грешка. Все пак std::set държи последователността сортирана. Тук по какво да сортира? Компилатора ни се оплаква, че нямаме operator<. Нека си напишем и да видим какво ще се случи: ```cpp #include struct Entity { int x; int y; bool operator<(const Entity& e) const { return x < e.x; } }; int main() { std::set s; s.insert({1, 1}); } ``` Сега вече всичко работи. Ами ако ни трябват повторения? ## std::multiset std::multiset е мултимножество. Освен стандартните функции multiset може да ни каже колко обекта от този тип имаме чрез метода count. Тук метода erase премахва **всички** елементи с подадена стойност! Ако искаме да премахнем един елемент използваме метода extract. extract връща елемент от тип node handle който държи в себе си стойността на извадения елемент. ```cpp #include #include int main() { std::multiset s; s.insert(10); s.insert(10); s.insert(10); auto k = s.extract(10); // 10 2 std::cout << k.value() << " " << s.count(10); } ``` ## Предшественици и наследници в множество ## std::map ## std::multimap