diff options
fix readme
2 files changed, 28 insertions, 13 deletions
| -rw-r--r-- | Seminar10/README.md | 41 | ||||
| -rw-r--r-- | Seminar10/media/avl-disbalance-1.png | bin | 87566 -> 87543 bytes |
diff --git a/Seminar10/README.md b/Seminar10/README.md index c999bc1..034ea77 100644 --- a/Seminar10/README.md +++ b/Seminar10/README.md @@ -21,7 +21,7 @@ bf(k) да е в множеството {-1, 0, 1}. Тяхната реализация както и тестове за тяхната коректност можете да намерите [тук](https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Seminar09/solutions.cpp#L75). ## Как разбираме, че сме нарушили балансираността на възел? -Ако bf(k) не е в {-1, 0, 1} то тогава сме нарушили балансираността. Трябва ни начин да пресмятаме баланс фактора на всечи възел колкото се може по - бързо. Както в много неща в този курс, за да пресмятаме бързо баланс фактора на възел ще жертваме малко памет и ще записваме височината на поддървото във всеки възел. Структурата би изглеждала така: +Ако bf(k) не е в {-1, 0, 1} то тогава сме нарушили балансираността. Трябва ни начин да пресмятаме баланс фактора на всеки възел колкото се може по - бързо. Както в много неща в този курс, за да пресмятаме бързо баланс фактора на възел ще жертваме малко памет и ще записваме височината на поддървото във всеки възел. Структурата би изглеждала така: ```cpp template<class T> @@ -34,7 +34,7 @@ struct Node { Node(const T& d, Node<T>* l, Node<T>* r, int h) : data {d}, left {l}, right {r}, height{h} {} }; ``` -Сега, За константно време можем да смятаме баланс фактора: +Сега, за константно време можем да смятаме баланс фактора: ```cpp template<class T> int getHeight(const Node<T>* r) { @@ -51,17 +51,18 @@ int getBalanceFactor(const Node<T>* r) { return getHeight(r->right) - getHeight(r->left); } ``` +Разбира се, тази сметка е вярна тогава и само тогава когато височините на лявото и дясното поддърво са коректни. ## insert Искаме да напишем операция, която за логаритмично време добавя елемент в дървото и запазва неговата балансираност. -В началото започваме по стандартния начин - рекурсивно намираме къде да добавим елемента и го добавяме като листо. След това обаче става интересно - какво става ако този елемент чупи балансираността. Той увеличава височината на (логаритмичен) брой поддървета. +В началото започваме по стандартния начин - рекурсивно намираме къде да добавим елемента и го добавяме като листо. След това обаче става интересно - какво става ако този елемент разбалансира дървото? Той увеличава височината на (логаритмичен) брой поддървета и е напълно възможно да направи някой баланс фактор на 2 или -2. Използваме факта, че рекурсивно сме слезли до някое листо и когато излизаме от рекурсията чрез ротации поправяме балансираността на дървото. При добавяне на елемент ни се налага да направим **най - много две ротации** -Също така при добавяне на елемент трябва да променяме височината. Разбрахме се, че я пазим, а това, че добавяме елемент я променя. За щастие това може да стане в константно време: +Също така при добавяне на елемент трябва да променяме височината. Разбрахме се, че я пазим, а това, че добавяме елемент я променя. За щастие това може да стане за константно време: ```cpp template<class T> @@ -100,32 +101,45 @@ void addElement(Node<T>*& root, const T& elem) { } } ``` -Можем да оптимизираме този алгоритъм, но засега целта е да разберем какво се случва. +Как можем да оптимизираме този алгоритъм като знаем, че винаги при вмъкване се правят най - много две ротации? -Логиката по добавянето е почти същата като при стандартното двоично наредено дърво, но този път имаме функцията balance(r); +Логиката по добавянето е почти същата като при стандартното двоично наредено дърво, но този път имаме функциии поддържащи баланса на r. Да разгледаме какви случаи имаме при дисбалансираността. Нега разгледаме случая в който дясното поддърво е дисбалансирано. Нещата за лявото са абсолютно симетрични! -Имаме три случая за баланс фактора на дясното поддърво. +## Имаме три случая за баланс фактора на дясното поддърво. -* Случай 1 - той е 1 + +## bf(root.right) = 1  Тук виждаме, че просто лява ротация около корена ни свърши работа, супер. -* Случай 2 - той е 0 +## bf(root.right) = 0  Тук също просто лява ротация ни свърши работа. -* Случай 3 - той е -1 +## bf(root.right) = -1  -Е, какво направихме с тази лява ротация.. Само направихме нещата по - лоши. Лявата ротация не ни върши работа тук и трябва на намерим друг начин да се справим. +Е, какво направихме с тази лява ротация? Само направихме нещата по - лоши. Лявата ротация не ни върши работа тук и трябва на намерим друг начин да се справим. + +В предните два случая нещата с лява ротация работиха. Дали има начин да отида в някой от тях? + +<span style="color:red"> +<b>Забелязвам, че ако направя дясна ротация около корена на дясното поддърво (с височина k + 1) вече баланс фактора на дясното поддърво ще бъде 1.</b> +</span> + -В предните два случая нещата с лява ротация работиха. Дали има начин да отида в някой от тях? Забелязвам, че ако направя дясна ротация около корена на дясното поддърво (с височина k + 1) вече баланс фактора на дясното поддърво ще бъде 1. +<span style="color:red"> +<b>Това обаче е случай 1, който знаем, че с лява ротация работи. +</b> +</span> -Това обаче е случай 1, който знаем, че с лява ротация работи. Тоест просто правя дясна ротация около корена на дясното поддърво (за да отида в сл. 1) и после правя лява ротация около корена. +<span style="color:red"> +Тоест просто правя дясна ротация около корена на дясното поддърво (за да отида в сл. 1) и после правим лява ротация около корена. +</span> Нарисувайте си по подобен на примерите начин как ще изглежда това. @@ -162,6 +176,7 @@ void balanceRight(Node<T>*& root) { ``` Проверката за ляв дисбаланс ще изглежда по симетричен начин. +При левия дисбаланс баланс факторът при който трябва да оправим нещата няма да е 2 а ще е -2. Също така случая, в който ни трябват две ротации няма да е -1 а ще е 1. ## Премахване на елемент При стандартните дървета имахме следния алгоритъм: diff --git a/Seminar10/media/avl-disbalance-1.png b/Seminar10/media/avl-disbalance-1.png Binary files differindex 55d6a26..6d94cd6 100644 --- a/Seminar10/media/avl-disbalance-1.png +++ b/Seminar10/media/avl-disbalance-1.png |
