Дървото AVL е изобретено от GM Adelson - Velsky и EM Landis през 1962 г. Дървото е наречено AVL в чест на своите изобретатели.
AVL дървото може да се дефинира като балансирано по височина двоично дърво за търсене, в което всеки възел е свързан с фактор на баланс, който се изчислява чрез изваждане на височината на дясното му поддърво от тази на лявото му поддърво.
Твърди се, че дървото е балансирано, ако коефициентът на баланс на всеки възел е между -1 и 1, в противен случай дървото ще бъде небалансирано и трябва да бъде балансирано.
Фактор на баланс (k) = височина (ляво (k)) - височина (дясно (k))
Ако факторът на баланс на който и да е възел е 1, това означава, че лявото поддърво е едно ниво по-високо от дясното поддърво.
Ако факторът на баланс на който и да е възел е 0, това означава, че лявото поддърво и дясното поддърво имат еднаква височина.
Ако факторът на баланс на който и да е възел е -1, това означава, че лявото поддърво е едно ниво по-ниско от дясното поддърво.
AVL дърво е дадено на следващата фигура. Можем да видим, че коефициентът на баланс, свързан с всеки възел, е между -1 и +1. следователно, това е пример за AVL дърво.
Сложност
| Алгоритъм | Среден случай | Най-лошия случай |
|---|---|---|
| пространство | На) | На) |
| Търсене | o(log n) | o(log n) |
| Поставете | o(log n) | o(log n) |
| Изтрий | o(log n) | o(log n) |
Операции върху AVL дърво
Поради факта, че дървото на AVL също е дърво за двоично търсене, следователно всички операции се изпълняват по същия начин, както се извършват в дърво за двоично търсене. Търсенето и преминаването не водят до нарушаване на свойствата на дървото на AVL. Вмъкването и изтриването обаче са операциите, които могат да нарушат това свойство и следователно те трябва да бъдат преразгледани.
| SN | Операция | Описание |
|---|---|---|
| 1 | Вмъкване | Вмъкването в AVL дърво се извършва по същия начин, както се извършва в двоично дърво за търсене. Това обаче може да доведе до нарушение в свойството на дървото на AVL и следователно дървото може да се нуждае от балансиране. Дървото може да бъде балансирано чрез прилагане на ротации. |
| 2 | Изтриване | Изтриването може също да се извърши по същия начин, както се извършва в двоично дърво за търсене. Изтриването може също да наруши баланса на дървото, поради което се използват различни видове ротации за повторно балансиране на дървото. |
Защо AVL Tree?
AVL дървото контролира височината на двоичното дърво за търсене, като не позволява то да бъде изкривено. Времето, необходимо за всички операции в двоично дърво за търсене с височина h е O(h) . Въпреки това, той може да бъде разширен до На) ако BST се изкриви (т.е. най-лошият случай). Чрез ограничаване на тази височина до log n, дървото на AVL налага горна граница на всяка следваща операция O(log n) където n е броят на възлите.
AVL ротации
Извършваме ротация в дървото на AVL само в случай, че факторът на баланс е различен от -1, 0 и 1 . Има основно четири типа ротации, които са както следва:
- L L ротация: Вмъкнатият възел е в лявото поддърво на лявото поддърво на A
- R R ротация: Вмъкнатият възел е в дясното поддърво на дясното поддърво на A
- L R ротация: Вмъкнатият възел е в дясното поддърво на лявото поддърво на A
- R L ротация: Вмъкнатият възел е в лявото поддърво на дясното поддърво на A
Където възел A е възелът, чийто балансов фактор е различен от -1, 0, 1.
Първите две ротации LL и RR са единични ротации, а следващите две ротации LR и RL са двойни ротации. За да бъде дървото небалансирано, минималната височина трябва да бъде поне 2. Нека разберем всяко завъртане
конвертиране на int в низ
1. RR ротация
Когато BST стане небалансиран, поради вмъкване на възел в дясното поддърво на дясното поддърво на A, тогава извършваме RR ротация, RR ротация е ротация, обратна на часовниковата стрелка, която се прилага на ръба под възел с фактор на баланс -2
В горния пример възел А има фактор на баланс -2, тъй като възел С е вмъкнат в дясното поддърво на дясно поддърво. Извършваме RR ротация на ръба под A.
2. LL ротация
Когато BST стане небалансиран, поради вмъкване на възел в лявото поддърво на лявото поддърво на C, тогава извършваме LL ротация, LL ротация е ротация по посока на часовниковата стрелка, която се прилага на ръба под възел с фактор на баланс 2.
В горния пример възел C има коефициент на баланс 2, тъй като възел A е вмъкнат в лявото поддърво на лявото поддърво C. Извършваме LL ротация на ръба под A.
3. LR ротация
Двойните завъртания са малко по-трудни от единичните, което вече беше обяснено по-горе. LR ротация = RR ротация + LL ротация, т.е. първата RR ротация се извършва на поддърво и след това LL ротация се извършва на пълно дърво, под пълно дърво имаме предвид първия възел от пътя на вмъкнатия възел, чийто баланс фактор е различен от -1 , 0 или 1.
Нека разберем всяка стъпка много ясно:
заместване от низ в java
| състояние | Действие |
|---|---|
 | Възел B е вмъкнат в дясното поддърво на A, лявото поддърво на C, поради което C се е превърнал в небалансиран възел с фактор на баланс 2. Този случай е L R ротация, където: Вмъкнатият възел е в дясното поддърво на лявото поддърво на ° С |
 | Тъй като LR ротация = RR + LL ротация, следователно RR (обратно на часовниковата стрелка) на поддърво с корен в A се извършва първо. Като правите RR ротация, възел А , стана лявото поддърво на Б . |
 | След извършване на RR ротация, възел C все още е небалансиран, т.е. има фактор на баланс 2, тъй като вмъкнатият възел A е вляво отляво на ° С |
 | Сега извършваме LL въртене по посока на часовниковата стрелка на пълно дърво, т.е. на възел C. възел ° С сега се превърна в дясно поддърво на възел B, A е ляво поддърво на B |
 | Коефициентът на баланс на всеки възел сега е -1, 0 или 1, т.е. BST вече е балансиран. |
4. RL ротация
Както вече беше обсъдено, двойното завъртане е малко по-трудно от единичното завъртане, което вече беше обяснено по-горе. R L ротация = LL ротация + RR ротация, т.е. първо LL ротация се извършва на поддърво и след това RR ротация се извършва на пълно дърво, под пълно дърво имаме предвид първия възел от пътя на вмъкнатия възел, чийто баланс фактор е различен от -1 , 0 или 1.
| състояние | Действие |
|---|---|
 | Възел Б е вмъкнато в лявото поддърво на ° С дясното поддърво на А , поради което A се е превърнал в небалансиран възел с коефициент на баланс - 2. Този случай е RL ротация, където: Вмъкнатият възел е в лявото поддърво на дясното поддърво на A |
 | Тъй като RL въртене = LL въртене + RR въртене, следователно, LL (по посока на часовниковата стрелка) на поддърво с корен в ° С се извършва първо. Като правите RR ротация, възел ° С се превърна в дясното поддърво на Б . |
 | След извършване на LL ротация, възел А все още е небалансиран, т.е. има фактор на баланс -2, което се дължи на дясното поддърво на възела A на дясното поддърво. |
 | Сега извършваме RR ротация (въртене обратно на часовниковата стрелка) на пълно дърво, т.е. на възел A. възел ° С сега се превърна в дясно поддърво на възел B, а възел A се превърна в ляво поддърво на B. |
 | Коефициентът на баланс на всеки възел сега е -1, 0 или 1, т.е. BST сега е балансиран. |
В: Конструирайте AVL дърво със следните елементи
H, I, J, B, A, E, C, F, D, G, K, L
1. Вмъкнете H, I, J
При вмъкване на горните елементи, особено в случая на H, BST става небалансиран, тъй като факторът на баланс на H е -2. Тъй като BST е изкривен надясно, ние ще извършим RR ротация на възел H.
Полученото балансово дърво е:
2. Поставете B, A
При вмъкване на горните елементи, особено в случай на A, BST става небалансиран, тъй като факторът на баланс на H и I е 2, ние разглеждаме първия възел от последния вмъкнат възел, т.е. H. Тъй като BST от H е изкривен наляво, ще извършим LL ротация на възел H.
Полученото балансово дърво е:
3. Вмъкнете E
При вмъкване на E, BST става небалансиран, тъй като факторът на баланс на I е 2, тъй като ако пътуваме от E към I, откриваме, че е вмъкнат в лявото поддърво на дясното поддърво на I, ние ще извършим LR ротация на възел I. LR = RR + LL ротация
3 a) Първо извършваме RR ротация на възел B
Полученото дърво след RR ротация е:
3b) Първо извършваме LL ротация на възела I
Полученото балансирано дърво след LL ротация е:
4. Поставете C, F, D
java низът е празен
При вмъкване на C, F, D, BST става небалансирано, тъй като факторът на баланс на B и H е -2, тъй като ако пътуваме от D до B, откриваме, че е вмъкнато в дясното поддърво на лявото поддърво на B, ще изпълним RL Ротация на възел I. RL = LL + RR ротация.
4a) Първо извършваме LL ротация на възел E
Полученото дърво след LL ротация е:
4b) След това извършваме RR ротация на възел B
Полученото балансирано дърво след ротация на RR е:
5. Вмъкнете G
При вмъкване на G, BST става небалансиран, тъй като факторът на баланс на H е 2, тъй като ако пътуваме от G до H, откриваме, че е вмъкнат в лявото поддърво на дясното поддърво на H, ще извършим LR ротация на възел I. LR = RR + LL ротация.
5 a) Първо извършваме RR ротация на възел C
Полученото дърво след RR ротация е:
5 b) След това извършваме LL ротация на възел H
Полученото балансирано дърво след LL ротация е:
6. Вмъкнете К
При въвеждане на K, BST става небалансиран, тъй като факторът на баланс на I е -2. Тъй като BST е изкривен надясно от I до K, следователно ще извършим RR ротация на възела I.
Полученото балансирано дърво след ротация на RR е:
7. Поставете L
При вмъкване дървото L все още е балансирано, тъй като факторът на баланс на всеки възел сега е или -1, 0, +1. Следователно дървото е балансирано AVL дърво
