АВЛ Дърво

АВЛ дърво
	АВЛ дърво
	Пример за АВЛ дърво
Информация
Тип	дърво
Година	1962 г.
Изобретено от	Georgy Adelson-Velsky и Evgenii Landis
Сложност в O-нотация
	АВЛ дърво в Общомедия

В компютърните науки АВЛ дърво (на английски: AVL tree е вид самобалансиращо се двоично дърво за търсене, кръстено на съветските изобретатели Аделсон-Велский и Ландис (Adelson-Velskii и Landis), които публикуват през 1962 година своя труд „An algorithm for the organization of information“^[2]). То е и първото самобалансиращо се дърво,^[3] като балансирането му е идеално – разликата в броя на върховете на лявото и дясното поддървета на всеки от върховете е най-много единица. АВЛ дървото позволява ефективно търсене, вмъкване и изтриване за време О(log n) в средния и най-лошия случаи, където n е броят на елементите в дървото. Поради идеалното си балансиране, вмъкването и изтриването на елементи може да доведе до нуждата от една или повече ротации на дървото с цел възстановяване на баланса.

АВЛ дърветата често са сравнявани с червено-черни дървета, тъй като и двете поддържат един и същ набор от операции за сходно O(log n) време за основните операции. В сравнение с червено-черните дървета, АВЛ дърветата са по-строго балансирани,^[4] което води до по-бавно вмъкване и изтриване, но по-бързо обработване. Това ги прави привлекателни за структури от данни, които могат да бъдат изградени веднъж и заредени без реконструкция, като например езикови или програмни речници.

Операции

Основните операции с АВЛ дърво включват същите действия, извършвани при небалансирано двоично дърво, като търсене, добавяне на връх, изтриване на връх, но модификациите на АВЛ дървото са последвани от нула или повече операции, наречени дървесни ротации, които гарантират баланса на всички поддървета.

Търсене

Търсене на връх в АВЛ дърво се осъществява по същия начин както при обикновено небалансирано двоично дърво. В най-лошия случай алгоритъмът за търсене трябва да обходи от корена на дървото до най-далечното листо. Операцията по търсене отнема време, пропорционално на височината на дървото в най-лошия случай. Благодарение на идеалното си балансиране, АВЛ дърво с n върха има O(log n) височина.

Обхождане

Елементите на двоично дърво могат да бъдат обходени последователно (in-order обхождане) чрез рекурсивно обхождане на лявото поддърво, посещаване на корена и рекурсивно обхождане на дясното поддърво. Броят операцията по обхождане на всички елементи в АВЛ дърво е пропроционален на броя на елементите в дървото О(n).

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

Вмъкване

Първоначално върховете се включват по същия начин, както при обикновените двоични дървета, т.е. винаги се включват като листа. След вмъкване на връх е необходимо да се провери всеки връх за съответствие с инвариантите на АВЛ дърветата, като се започне от родителя на добавения връх и се достигне до корена. Тази операция се нарича „повторно обхождане“ (retracing). За целта се пресмята баланс фактор (balance factor) за всеки връх, който се дефинира като разликата във височините на лявото и дясното поддървета. Визуализация

За всеки връх на АВЛ дървото баланс факторът е цяло число в диапазона [-1,+1]. Факторът се съхранява във върха, но може да се наложи да се коригира след вмъкване или изтриване, което се извършва при операцията на повторно обхождане. Тъй като с единично вмъкване височината на АВЛ поддърво не може да се понижи с повече от единица, временно преизчисленият баланс фактор за връх е в диапазона [−2,+2]. Нито един проверен връх, за който преизчисленият баланс фактор е в диапазона [−1,+1], не се нуждае от ротации. Ако обаче преизчисленият баланс фактор е по-малък от -1 или по-голям от +1, поддървото, чийто корен е съответният връх, е небалансирано и е необходима ротация.

Поддържането на баланс фактора в АВЛ дърво се осъществява с помощта на няколко ротационни функции:

Двойна дясна ротация (Right Right Case)
Двойна лява ротация (Left Left Case)
Двойна ляво-дясна ротация (състои се от лява ротация, последвана от дясна) (Left Right Case)
Двойна дясно-лява ротация (състои се от дясна ротация, последвана от лява) (Right Left Case)

Описание на ротациите

Нека баланс факторът за определен връх P е 2 (случаят за стойност -2 ще бъде разгледан по-долу). Този случай е показан в лявата колона на илюстрацията за P:=5. Ако лявото поддърво (по-високото) с корен N не е наклонено надясно, т.е. N има балансов фактор 1 (или 0 при делене), дървото с корен 5 може да се завърти надясно, при което се получава балансирано дърво. Този случай е обозначен като „ляв-ляв случай“ (двойно ляв) в илюстрацията с N:=4. Ако поддървото е наклонено надясно, т.е. N:=3 има балансов фактор -1, първо се завърта поддървото наляво и така случаят се свежда до предишния. Този случай е обозначен като „ляв-десен случай“.

Ако баланс факторът на връх P е -2 (виж дясната колона на фигурата за P:=3), горният алгоритъм може да се изпълни в огледален ред: ако коренът N на дясното (по-високо) поддърво има баланс фактор -1 (или 0 при делене), може да се получи балансирано дърво, ако се завърти цялото дърво наляво. Случаят е обозначен като „десен-десен случай“ (двойно десен) в илюстрацията с N:=4. Ако коренът N:=5 на дясното поддърво има баланс фактор 1 („десен-ляв случай“), при завъртане на поддървото надясно се достига до „десен-десен случай“.

Повторното обхождане (retracing) при вмъкване може да се извърши със следния примерен код:

 // N е дете на P, чиято височина се увеличава с 1.
 do {
   // balance_factor(P) не е променен!
   if (N == left_child(P)) { // лявото поддърво се увеличава
     if (balance_factor(P) == 1) { // лявата колона на фигурата
       // ==> временният balance_factor(P) == 2 ==> необходимо е ребалансиране.
       if (balance_factor(N) == -1) { // ляв-десен случай
          rotate_left(N); // редукция към ляв-ляв случай
       }
       // ляв-ляв случай
       rotate_right(P);
       break; // излизане от цикъла
     }
     if (balance_factor(P) == -1) {
       balance_factor(P) = 0; // увеличението на височината на N се абсорбира в P.
       break; // излизане от цикъла
     }
     balance_factor(P) = 1; // височината се увеличава в P
   } else { // N == right_child(P), детето, чиято височина се увеличава с 1.
     if (balance_factor(P) == -1) { // дясната колона във фигурата
       // ==> временният balance_factor(P) == -2 ==> необходимо е ребалансиране.
       if (balance_factor(N) == 1) { // десен-ляв случай
          rotate_right(N); // редукция към десен-десен случай
       }
       // десен-десен случай
       rotate_left(P);
       break; // излизане от цикъла
     }
     if (balance_factor(P) == 1) {
       balance_factor(P) = 0; // увеличението на височината на N се абсорбира в P.
       break; // излизане от цикъла
     }
     balance_factor(P) = -1; // височината в P се увеличава
   }
   N = P;
   P = parent(P);
 } while (P != null); // евентуално нагоре до корена

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

За да се възстановят баланс факторите на всички възли, се използва това, че всички възли, които се нуждаят от корекция, лежат на „траекторията“, определена от вмъкването. Ако възстановяването се стартира от вмъкнатия връх, всеки връх от дървото отново ще има баланс фактор -1, 0 или 1.

Необходимото време за намиране на място за вмъкване е О(log n), плюс максимум О(log n) време за „повторно обхождане“ (retracing) обратно към корена и евентуално ребалансиране. Приема се, че операцията може да бъде завършена за О(log n) време.

Изтриване

Изтриването на елемент има същата сложност, както операциите търсене и вмъкване. При изтриване на елемент трябва да се запази свойството на двоичното дърво.

Нека връх X е върхът, чиято стойност желаем да изтрием, връх Y е върхът, чиято стойност трябва да открием в дървото и поставим на позицията на връх X, a връх Z е върхът, който ще извадим от дървото.

Нужните стъпки за изтриване на връх в АВЛ дърво са следните:

В случай че връх X е листо или има само едно дете, се преминава на стъпка 5, където Z=X.
Определяне на връх Y чрез установяване на най-големия връх в лявото поддърво на връх X (последователният предшественик на X – не притежава дясно дете) или на най-малкия в дясното поддърво (последователният наследник на X – не притежава ляво дете).
Разменят се всички връзки между деца и родители от връх X с тези на връх Y. С това действие последователната редица между възлите X и Y е временно нарушена, но структурата на дървото е запазена.
Нека връх Z приеме всички връзки на децата и родителите на стария връх Y – тези на новия връх X.
Ако връх Z има поддърво (което може да е листо), се закача към родителите на Z.
Ако връх Z е корен (неговият родител е несъществуващ), се актуализира коренът.
Изтриване на връх Z.
Обхождане на дървото обратно към корена (започвайки от родителя на върха Z) и корекция на баланс факторите при нужда.

Чрез операцията изтриване височината на АВЛ поддърво не може да бъде намалена с повече от единица, докато временният баланс фактор на върха е в диапазона от -2 до +2.

В случай че баланс факторът приеме стойност ±2, тогава поддървото е небалансирано и трябва да бъде извършена ротация. Различните случаи на ротации са описани в секция „Вмъкване“.

Процесът на обхождане за изтриване е следният:

 // N е дете на P, чиято височина се намалява с 1.
 do {
   // balance_factor(P) все още не е актуализиран!
   if (N == right_child(P)) { // Дясното поддърво се намалява
     if (balance_factor(P) == 1) { // Лявата колона на фигурата
       // ==> временният balance_factor(P) == 2 ==> необходимо е ребалансиране.
       S = left_child(P); // Брат на N
       B = balance_factor(S);
       if (B == -1) { // Двойна ляво-дясна ротация
          rotate_left(S); // Намаляване до лява ротация
       }
       // Лява ротация
       rotate_right(P);
       if (B == 0) // (На фигурата малката синя (0) на връх 4)
         break; // Височината не се променя: Излизане от цикъла
     }
     if (balance_factor(P) == 0) {
       balance_factor(P) = 1; // Намалянето на височината на N се абсорбира в P.
       break; // Излизане от цикъла
     }
     balance_factor(P) = 0; // Височината се намалява в P
   } else { // N == left_child(P), детето, чиято височина се намалява с 1.
     if (balance_factor(P) == -1) { // Дясната колона във фигурата
       // ==> временният balance_factor(P) == -2 ==> необходимо е ребалансиране.
       S = right_child(P); // Брат на N
       B = balance_factor(S);
       if (B == 1) { // Двойна дясно-лява ротация
          rotate_right(S); // Намаляване до дясна ротация
       }
       // Дясна ротация
       rotate_left(P);
       if (B == 0) // (На фигурата малката синя (0) на връх 4)
         break; // Височината не се променя: Излизане от цикъла
     }
     if (balance_factor(P) == 0) {
       balance_factor(P) = -1; // Навалянето на височината на N се абсорбира в P.
       break; // Излизане от цикъла
     }
     balance_factor(P) = 0; // Височината се намалява в P
   }
   N = P;
   P = parent(N);
 } while (P != null); // Обратно към корена

Обхождането може да приключи, ако баланс факторът приеме стойност ±1, показвайки, че височината на поддървото е останала непроменена. Този резултат може да бъде получен и от ротация, при която дете, стоящо по-високо в йерархията, притежава баланс фактор 0.

Ако баланс факторът приеме стойност 0, тогава височината на поддървото е намаляла с едно и обхождането трябва да продължи.

Необходимото време за намиране е О(log n), плюс максимум О(log n) време за „повторно обхождане“ (retracing) обратно към корена и евентуално ребалансиране. Приема се, че операцията може да бъде завършена за О(log n) време.

Сравнение с други структури

АВЛ са балансиращи се двоични дървета за търсене и са математически сходни на червено-черни дървета.

Въпреки че операциите за възстановяване на баланса са различни, и при двата вида те имат линейна сложност О(1) за едно ниво. И при двете структури има известна вероятност (≤ 0.5) правилата за балансиране да бъдат нарушени на следващото или по-следващото ниво към корена. Така средната стойност на броя възстановени нива е ≈1 или 2 с линейна сложност О(1), или в най-лошия случай О(logn), когато възстановяването се случва при всяко ниво до корена.

Първата разлика между двете е в размера на височината. За дърво с размер $n$ :

Височината на АВЛ дърво е строго по-малка от:^[5]^[6]

$\log _{\varphi }((n+2){\sqrt {5}})-2={\frac {\log _{2}(n+2)+\log _{2}({\sqrt {5}})}{\log _{2}(\varphi )}}-2\approx 1.44\log _{2}(n+2)-0.328$ ,

където $\varphi$ е златното сечение.

Височината на червено-черното дърво е не по-голяма от $2\log 2(n+1)$ .

В резултат на това, АВЛ дърветата са по-строго балансирани от червено-черните дървета^[7] и при тях възстановяването на баланса е по-бързо, но това потенциално е за сметка на добавянето и премахването на елементи. Сравнение на резултатите за двете дървета може да бъде намерено в Бен Пфафф.^[4] Неговите резултати са изложени в 79 измервания на сходството на АВЛ дървета (AVL) с червено-черни дървета (RB) с отношение ^AVL/_RB между 0.677 и 1.077, медиана ≈0.947 и средна геометрична стойност ≈0.910.

Друга разлика е, както е посочено от Мелхорн^[8] (стр. 165): „АВЛ дърветата не поддържат постоянни амортизирани разходи за актуализация“, докато червено-черните дървета поддържат такива (стр. 158).

Източници

↑ ^а ^б ^в ^г ^д ^е Eric Alexander. AVL Trees
↑ Georgy Adelson-Velsky, G.; Evgenii Landis (1962). „An algorithm for the organization of information“. Proceedings of the USSR Academy of Sciences (in Russian) 146: 263 – 266.English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259 – 1263,
↑ Robert Sedgewick, Algorithms, Addison-Wesley, 1983, ISBN 0-201-06672-6, page 199, chapter 15: Balanced Trees.
↑ ^а ^б Pfaff, Ben. Performance Analysis of BSTs in System Software (PDF) // June 2004.
↑ Burkhard, Walt. AVL Dictionary Data Type Implementation // Advanced Data Structures. A.S. Soft Reserves, page=103, Spring 2012.^{[неработеща препратка]}
↑ Knuth, Donald E. Sorting and searching. 2. ed., 6. printing, newly updated and rev. Boston, Addison-Wesley, 2000. ISBN 0-201-89685-0. с. 460.
↑ Всъщност, всяко АВЛ дърво може да се трансформира в червено-черно такова
↑ Mehlhorn, Kurt; Sanders, Peter (2008).Mehlhorn, Kurt, Sanders, Peter. Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg, 2008. ISBN 978-3-540-77977-3. DOI:10.1007/978-3-540-77978-0. с. 154 – 165.

Тази страница частично или изцяло представлява превод на страницата AVL tree в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[wiscurl-1] а ^б ^в ^г ^д ^е Eric Alexander. AVL Trees

[2] Georgy Adelson-Velsky, G.; Evgenii Landis (1962). „An algorithm for the organization of information“. Proceedings of the USSR Academy of Sciences (in Russian) 146: 263 – 266.English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259 – 1263,

[3] Robert Sedgewick, Algorithms, Addison-Wesley, 1983, ISBN 0-201-06672-6, page 199, chapter 15: Balanced Trees.

[Pfaff-4] а ^б Pfaff, Ben. Performance Analysis of BSTs in System Software (PDF) // June 2004.

[5] Burkhard, Walt. AVL Dictionary Data Type Implementation // Advanced Data Structures. A.S. Soft Reserves, page=103, Spring 2012.^{[неработеща препратка]}

[6] Knuth, Donald E. Sorting and searching. 2. ed., 6. printing, newly updated and rev. Boston, Addison-Wesley, 2000. ISBN 0-201-89685-0. с. 460.

[7] Всъщност, всяко АВЛ дърво може да се трансформира в червено-черно такова

[8] Mehlhorn, Kurt; Sanders, Peter (2008).Mehlhorn, Kurt, Sanders, Peter. Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg, 2008. ISBN 978-3-540-77977-3. DOI:10.1007/978-3-540-77978-0. с. 154 – 165.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]