Въведение в AVL дърво в структурата на данните
AVL дърво в структурата на данните се отнася до Adelson, Velski & Landis Tree. Това е подобрена версия на дървото за двоично търсене. Той има всички функции като на Binary Search Tree, но само се различава, тъй като те поддържат разлика между височината на лявото под дърво и дясното дърво и също така гарантира, че стойността му е <= 1 в дървото, това е известно като баланс фактор.
Balance Factor = height(left-subtree) − height(right-subtree)
Например: Помислете за следните дървета
В горния пример височината на дясното дърво = 2 и на лявото = 3 по този начин BF = 2, което е <= 1, така дървото се казва балансирано.
Защо се нуждаем от AVL дърво в DS?
Докато работим с Binary Search Tree, срещаме сценарий, в който елементите са подредени. В такива случаи всички елементи на масива са подредени от едната страна на корена, това води до увеличаване на времевата сложност на търсене на елемент в масива и сложността става-O (n), т.е. най-лошият случай на сложност на дървото, За да разрешат подобни проблеми и да намалят времето за търсене, AVL дърветата са изобретени от Adelson, Velski & Landis.
Пример:
На горната фигура Височината на лявото поддърво = 3 беше като
Височина на дясното поддърво = 0
По този начин балансиращ фактор = 3-0 = 3. По този начин търсенето на елемент в такова дърво има сложност O (n), която е подобна на линейното търсене. За да се избегне това сложно търсене AVL дърво беше въведено там, където всеки възел в дървото трябва да поддържа
коефициент на баланс <= 1, в противен случай се извършват различни техники на въртене, за да се балансира такова дърво.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Видове ротации
Когато коефициентът на баланс за дървото не отговаря на условието <= 1, тогава трябва да се извършат завъртания върху тях, за да го превърнат в балансирано дърво.
Има 4 вида ротации:
1. Ляво завъртане: Ако добавянето на възел вдясно от дървото прави дисбаланс, тогава в този случай трябва да се извърши завъртане на ляво.
2. Дясно завъртане: Ако добавянето на възел вляво от дървото прави дисбаланса на възела, тогава трябва да се извърши дясно въртене. С други думи, когато броят на възлите се увеличава от лявата страна, тогава възниква необходимост от преместване на елементите в дясната страна, за да се балансира, като по този начин се казва, че е въртене надясно.
3. Вляво-надясно въртене: Този тип въртене е комбинация от гореописаните две завъртания. Този тип завъртане възниква, когато един елемент се добави към дясното дърво на лявото дърво.
В такъв случай първо извършете въртене вляво върху поддървото, последвано от дясно завъртане на лявото дърво.
4. Дясно-ляво въртене: Този тип въртене също се състои от последователност от над 2 въртения. Този тип завъртане е необходим, когато елемент се добави вляво от дясното дърво и дървото стане дисбалансирано. В такъв случай първо извършваме дясно въртене в дясното поддърво и след това ляво въртене на дясното дърво.
Операции на AVL дърво в DS
По-долу 3 операции, които могат да бъдат извършени на AVL дървото: -
1. Търсете
Тази операция е подобна на извършване на търсене в Binary Search Tree. Следващите стъпки са както следва:
- Прочетете елемента, предоставен от потребителя, кажете x.
- Сравнете елемента от корена, ако е същият, тогава излезте в противен случай преминете към следващата стъпка.
- Ако х
Друго отидете при правилното дете и сравнете отново.
Следвайте процеси B и C, докато намерите елемента и излезете.
Този процес има сложност O (log n).
Пример:
 | Помислете за това дърво, където трябва да извършим търсене на стойност на възел 9. Първо нека x = 9, коренна стойност (12)> x след това, стойността трябва да бъде в лявото поддърво на кореновия елемент. |
 | Сега x се сравнява със стойността на възел 3 x> 3, така че трябва да продължим към дясното дърво. |
 | Сега x се сравнява с възел (9), където 9 == 9 връща истина. По този начин търсенето на елементи завършва в дървото. |
2. Вмъкване
Докато вмъквате елемент в AVL дървото, трябва да намерим конкретен за местоположението елемент, който трябва да бъде вмъкнат и след това елементът е прикрепен същият като вмъкване в BST, но след това се проверява дали дървото е все още балансирано или не т.е. коефициентът на баланс на възел е <= 1. И определени ротации се извършват според нуждите.
Сложността е O (log n).
Пример: Помислете по-долу дървото,
 | Всеки възел има коефициент на баланс като 0, -1 или 1 по този начин дървото е балансирано. Сега нека какво се случва, когато се вмъкне възел със стойност 1. Първото дърво се обикаля, за да намери мястото, където трябва да бъде поставено … Така 1 <2 се записва като ляво дете на възела (2). |
 | След поставяне възелът (9) става дисбаланс с коефициент на баланс = 2. Сега той е подложен на правилно въртене. |
 | Дървото става балансирано след въртене надясно и по този начин операцията за вмъкване е завършена успешно. |
3. Изтриване
Изтриването на елемент в AVL дървото включва също търсене на елемент в дървото и след това изтриването му. Операцията за търсене е същата като BST и след намирането на елемента, който трябва да бъде изтрит, елементът се премахва от дървото и елементите се настройват, за да го направят BST отново. След проверка на тези елементи има коефициент на баланс 0, -1 или 1 и по този начин се извършват подходящи завъртания, за да бъде балансиран.
Сложност, ако O (лог n).
 | Помислете за даденото дърво, чиито всички имат коефициент на баланс 0, -1 или 1. Сега нека изтрием възел със стойност 16. Първото дърво се преминава, за да намери възела със стойност 16, същата като алгоритъм за търсене. |
 | Възел 16 ще бъде заменен с предшестващия ред на този възел, който е най-големият елемент от лявото поддърво, т.е. 12 Дървото е станало небалансирано, поради което LL - трябва да се извърши въртене. |
 | Сега всеки възел стана балансиран. |
Заключение - AVL дърво в структурата на данните
AVL дървото е потомък на дървото за двоично търсене, но преодолява недостатъка на увеличаващата се сложност в случай, че елементите са сортирани. Той следи коефициентът на баланс на дървото да бъде 0 или 1 или -1. В случай, че дървото стане неуравновесено, се извършват съответните техники на въртене, за да се балансира дървото.
Препоръчителни статии
Това е ръководство за AVL дърво в структурата на данните. Тук обсъждаме Въведение, Операции на AVL дърво в DS и Видове ротации. Можете също да разгледате и другите ни свързани статии, за да научите повече -
- jQuery елементи
- Какво е Science Science
- Видове дървета в структурата на данните
- C # Видове данни