Преглед на кода на АВЛ Дърво

{{обработка|проверка на превода}}
{{Структура данни
| име            = АВЛ дърво
| картинка       = AVLtreef.svg
| описание       = Пример за АВЛ дърво
| тип            = [[Дърво (структура от данни)|дърво]]
| година         = 1962 г.
| изобретено     = [[Georgy Adelson-Velsky]] и [[Evgenii Landis]]
| място средно   = {{math|O(''n'')}}
| място лошо     = {{math|O(''n'')}}
| търсене средно = {{math|O(log ''n'')}}<ref name="wiscurl">{{cite web | url=http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html | title=AVL Trees | author=Eric Alexander}}</ref>
| търсене лошо   = {{math|O(log ''n'')}}<ref name="wiscurl"/>
| добавяне средно  = {{math|O(log ''n'')}}<ref name="wiscurl"/>
| добавяне лошо  = {{math|O(log ''n'')}}<ref name="wiscurl"/>
| изтриване средно = {{math|O(log ''n'')}}<ref name="wiscurl"/>
| изтриване лошо = {{math|O(log ''n'')}}<ref name="wiscurl"/>
| бележки        = 
| общомедия      = 
}}
В [[Информатика|компютърните науки]] '''АВЛ дърво''' ({{lang|en|AVL tree}} е вид самобалансиращо се [[двоично дърво за търсене]], кръстено на съветските изобретатели Аделсон-Велский и Ландис ('''A'''delson-'''V'''elskii и '''L'''andis), които публикуват през 1962 година своя труд „An algorithm for the organization of information“<ref>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,</ref>). То е и първото самобалансиращо се дърво,<ref>Robert Sedgewick, Algorithms, Addison-Wesley, 1983, ISBN 0-201-06672-6, page 199, chapter 15: Balanced Trees.</ref> като балансирането му е идеално – разликата в броя на върховете на лявото и дясното поддървета на всеки от върховете е най-много единица. АВЛ дървото позволява ефективно търсене, вмъкване и изтриване за време [[Big O нотация|О]](log ''n'') в средния и най-лошия случаи, където n е броят на елементите в дървото. Поради идеалното си балансиране, вмъкването и изтриването на елементи може да доведе до нуждата от една или повече ротации на дървото с цел възстановяване на баланса.

АВЛ дърветата често са сравнявани с [[Червено-черно дърво|червено-черни дървета]], тъй като и двете поддържат един и същ набор от операции за сходно O(log ''n'') време за основните операции. В сравнение с червено-черните дървета, АВЛ дърветата са по-строго балансирани,<ref name="Pfaff">{{cite web|last = Pfaff|first = Ben|title = Performance Analysis of BSTs in System Software|date=June 2004|url = http://www.stanford.edu/~blp/papers/libavl.pdf|format = PDF}}</ref> което води до по-бавно вмъкване и изтриване, но по-бързо обработване. Това ги прави привлекателни за структури от данни, които могат да бъдат изградени веднъж и заредени без реконструкция, като например езикови или програмни речници.

== Операции ==
[[Файл:BinaryTreeRotations.svg|мини|300px|Дървесни ротации]]
Основните операции с АВЛ дърво включват същите действия, извършвани при небалансирано двоично дърво, като търсене, добавяне на връх, изтриване на връх, но модификациите на АВЛ дървото са последвани от нула или повече операции, наречени дървесни ротации, които гарантират баланса на всички поддървета.

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

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

{|
|-valign="top"
|
 '''inorder'''(node)
   '''if''' (node = '''null''')
     '''return'''
   inorder(node.left)
   visit(node)
   inorder(node.right)
|}

=== Вмъкване ===
[[Файл:Ребалансиране на АВЛ дърво.png|мини|559x559пкс|Пример как ротациите ребалансират връх в АВЛ дърво. Номерираните кръгове представляват върхове, които се ребалансират. Триъгълниците, означени с букви, представляват поддървета, които сами по себе си са балансирани АВЛ дървета. Син номер в непосредствена близост до връх определя възможен баланс фактор (номерът в скоби възниква само в случай на изтриване).]]
Първоначално върховете се включват по същия начин, както при обикновените двоични дървета, т.е. винаги се включват като листа. След вмъкване на връх е необходимо да се провери всеки връх за съответствие с инвариантите на АВЛ дърветата, като се започне от родителя на добавения връх и се достигне до корена. Тази операция се нарича „повторно обхождане“ (retracing). За целта се пресмята баланс фактор (balance factor) за всеки връх, който се дефинира като разликата във височините на лявото и дясното поддървета. [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html Визуализация]

За всеки връх на АВЛ дървото баланс факторът е цяло число в диапазона [-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) при вмъкване може да се извърши със следния примерен код:<syntaxhighlight lang="d">
 // 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); // евентуално нагоре до корена
</syntaxhighlight>

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

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

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

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

Нека връх X е върхът, чиято стойност желаем да изтрием, връх Y е върхът, чиято стойност трябва да открием в дървото и поставим на позицията на връх X, a връх Z е върхът, който ще извадим от дървото.
[[Файл:binary search tree delete.svg|мини|640px|център|Изтриване на връх с две деца (поддървета) от двоично дърво за търсене чрез използване на последователен предшественик ([[In-order traversal|in-order]] predecessor). Най-десният връх в лявото поддърво е отбелязан с 6.]]
Нужните стъпки за изтриване на връх в АВЛ дърво са следните:
# В случай че връх X е листо или има само едно дете, се преминава на стъпка 5, където Z=X.
# Определяне на връх Y чрез установяване на най-големия връх в лявото поддърво на връх X (последователният предшественик на X – не притежава дясно дете) или на най-малкия в дясното поддърво (последователният наследник на X – не притежава ляво дете).
# Разменят се всички връзки между деца и родители от връх X с тези на връх Y. С това действие последователната редица между възлите X и Y е временно нарушена, но структурата на дървото е запазена.
# Нека връх Z приеме всички връзки на децата и родителите на стария връх Y – тези на новия връх X.
# Ако връх Z има поддърво (което може да е листо), се закача към родителите на Z.
# Ако връх Z е корен (неговият родител е несъществуващ), се актуализира коренът.
# Изтриване на връх Z.
# Обхождане на дървото обратно към корена (започвайки от родителя на върха Z) и корекция на баланс факторите при нужда.

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

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

Процесът на обхождане за изтриване е следният:
<syntaxhighlight lang="d">
 // 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); // Обратно към корена
</syntaxhighlight>

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

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

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

== Сравнение с други структури ==
'''АВЛ''' са балансиращи се [[Двоично дърво|двоични дървета]] за търсене и са математически сходни на [[Червено-черно дърво|червено-черни дървета]].

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

Първата разлика между двете е в размера на височината. За дърво с размер '''''<math>n</math>''''':
* Височината на АВЛ дърво е строго по-малка от:<ref>{{cite book|last=Burkhard|first=Walt|title=Advanced Data Structures|url=http://ieng6.ucsd.edu/~cs100s/public/Notes/CS100s12.pdf|date=Spring 2012|publisher=[https://web.archive.org/web/20170715000635/http://softreserves.ucsd.edu/ A.S. Soft Reserves], page=103|chapter=AVL Dictionary Data Type Implementation}}{{Dead link|date=февруари 2021 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref>{{cite book|last=Knuth|first=Donald E.|title=Sorting and searching|year=2000|publisher=Addison-Wesley|location=Boston|isbn=0-201-89685-0|pages=460|edition=2. ed., 6. printing, newly updated and rev.}}</ref>

<math>\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</math>,

където <math>\varphi</math> е [[Златно сечение|златното сечение]].
* Височината на червено-черното дърво е не по-голяма от <math>2\log2(n + 1)</math>.

В резултат на това, АВЛ дърветата са по-строго балансирани от червено-черните дървета<ref>Всъщност, всяко АВЛ дърво може да се трансформира в червено-черно такова</ref> и при тях възстановяването на баланса е по-бързо, но това потенциално е за сметка на добавянето и премахването на елементи. Сравнение на резултатите за двете дървета може да бъде намерено в Бен Пфафф.<ref name="Pfaff"/> Неговите резултати са изложени в 79 измервания на сходството на АВЛ дървета ('''AVL''') с червено-черни дървета ('''RB''') с отношение '''''<sup>AVL</sup>''/''<sub>RB</sub>''''' между 0.677 и 1.077, [[Медиана (статистика)|медиана]] ≈0.947 и [[Средно геометрично|средна геометрична стойност]] ≈0.910.

Друга разлика е, както е посочено от Мелхорн<ref>Mehlhorn, Kurt; Sanders, Peter (2008).{{cite book|last1=Mehlhorn|first1=Kurt|authorlink1=Kurt Mehlhorn|last2=Sanders|first2=Peter|authorlink2=Peter Sanders (computer scientist)|title=Algorithms and Data Structures. The Basic Toolbox.|year=2008|publisher=Springer, Berlin/Heidelberg|isbn=978-3-540-77977-3|doi=10.1007/978-3-540-77978-0|pages=154 – 165|url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf}}</ref> (стр. 165): „''АВЛ дърветата не поддържат постоянни амортизирани разходи за актуализация''“, докато червено-черните дървета поддържат такива (стр. 158).

== Източници ==
<references />
{{Превод от|en|AVL tree|717279479}}

[[Категория:Структури от данни]]