Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar10 / README.md
blob: c999bc1be74f2c4a48a5b67fdad1167f446c5272 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
# 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<class T>
struct Node {
    T data;
    Node<T>* left;
    Node<T>* right;
    int height;

    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) {
    if(r == nullptr)
        return 0;
    return r->height;
}

template<class T>
int getBalanceFactor(const Node<T>* r) {
    if(r == nullptr)
        return 0;

    return getHeight(r->right) - getHeight(r->left);
}
```

## insert
Искаме да напишем операция, която за логаритмично време добавя елемент в дървото и запазва неговата балансираност. 

В началото започваме по стандартния начин - рекурсивно намираме къде да добавим елемента и го добавяме като листо. След това обаче става интересно - какво става ако този елемент чупи балансираността. Той увеличава височината на (логаритмичен) брой поддървета. 

Използваме факта, че рекурсивно сме слезли до някое листо и когато излизаме от рекурсията чрез ротации поправяме балансираността на дървото.

При добавяне на елемент ни се налага да направим **най - много две ротации**

Също така при добавяне на елемент трябва да променяме височината. Разбрахме се, че я пазим, а това, че добавяме елемент я променя. За щастие това може да стане в константно време:

```cpp
template<class T>
void updateHeight(Node<T>*& r) {
    if(r == nullptr)
        return;
    
    r->height = getHeight(r->left) + getHeight(r->right) + 1;
}
```

Алгоритъмът за добавяне би изглеждал по следния начин:

```cpp
template<class T>
void addElement(Node<T>*& root, const T& elem) {
    // Стигнали сме до дъното на рекурсията
    if(root == nullptr) {
        root = new Node<T>(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<class T>
void balanceRight(Node<T>*& 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<class T>
bool removeElement(Node<T>*& 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<T>* toDelete = root;
        root = root->left;
        delete toDelete;

        updateHeight(root);
    }
    else if(!root->left && root->right) {
        Node<T>* 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\<T>. Въпреки това stl ни предоставя обекти, които в реализацията си използват балансирани дървета.

### std::set
Сет (или множество) е асоциативен контейнер който съдържа сортирана последователност от обекти от тип Т. Търсене, премахване и добавяне имат логаритмична сложност. В стл сетовете се имплементират чрез червено черни дървета, които също като AVL дървото поддържат логаритмична височина (използвайки друга схема за балансиране).

Както в множествата, обектите в сета **са уникални**. За него можете също да си мислите като за дърво, което при insert не допуска повторения на ключове.

Да видим бърз пример:
```cpp
#include<iostream>
#include<set>

int main() {
	std::set<int> s;

	for (size_t i = 0; i < 10; i++)
		s.insert(i);

	// find метода връща итератор към елемента
	std::set<int>::iterator elem = s.find(4);

	// Това извежда 4
	std::cout << *elem << " ";

	// Отиваме на следващия елемент... Но колекцията е сортирана!
	++elem;
	
	// Това извежда 5
	std::cout << *elem;
}
```

Супер, но какво връща find когато елемента го няма? Как изобщо да премахвам елемент? Следващия пример отговаря на тези въпроси.

```cpp
#include<iostream>
#include<set>

int main() {
	std::set<int> s;

	// Вкарваме 10 пъти 5, но елементите нямат повторения!
	for (size_t i = 0; i < 10; i++)
		s.insert(5);

	// Премахваме 5
	s.erase(5);

	std::set<int>::iterator it = s.find(5);

	// Когато елемента го няма в множеството просто връща end() итератора (както е с много други обекти в stl)
	if (it == s.end())
		std::cout << "Element not found!";
}
```

Та обекта го няма - връща end итератора. Лесна работа. Супер сега обаче наредбата не ми харесва. Искам колекцията ми да е сортирана в обратен ред. Сортировката зависеше единствено от компаратор функцията (rли релацията по която сортирам, която в първия пример по подразбиране е <). Дали не мога да накарам моя сет да сортира по >?
Това би станало по следния начин:

```cpp
#include<iostream>
#include<set>

int main() {
    // std::greater<T> е структура с оператор()
    // Дали ще можем ние да си напишем наша структура с operator() 
    // И да я пуснем като comparator? Опитайте!
	std::set<int, std::greater<int>> s;

	for (size_t i = 0; i < 10; i++)
		s.insert(i);

	for (auto x : s)
		std::cout << x << " ";
}
```

Често ни се налага да държим в множество обекти които не са числа а примерно някакви структури или класове. Да разгледаме следния код:

```cpp
#include<set>

struct Entity {
    int x;
    int y;
};

int main() {
    std::set<Entity> s;

    s.insert({1, 1});
}
```
Тази програма ще ни върне грешка. Все пак std::set държи последователността сортирана. Тук по какво да сортира? Компилатора ни се оплаква, че нямаме operator<. Нека си напишем и да видим какво ще се случи:

```cpp
#include<set>

struct Entity {
    int x;
    int y;

    bool operator<(const Entity& e) const {
        return x < e.x;
    }
};

int main() {
    std::set<Entity> s;

    s.insert({1, 1});
}
```
Сега вече всичко работи. Ами ако ни трябват повторения?

## std::multiset
std::multiset е мултимножество. Освен стандартните функции multiset може да ни каже колко обекта от този тип имаме чрез метода count. Тук метода erase премахва **всички** елементи с подадена стойност! Ако искаме да премахнем един елемент използваме метода extract.

 extract връща елемент от тип node handle който държи в себе си стойността на извадения елемент.

```cpp
#include<set>
#include<iostream>

int main() {
	std::multiset<int> 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