Топ-100
Back

ⓘ АВЛ Дърво. В компютърните науки АВЛ дърво, които публикуват през 1962 година своя труд An algorithm for the organization of information. То е и първото самобала ..




АВЛ Дърво
                                     

ⓘ АВЛ Дърво

В компютърните науки АВЛ дърво, които публикуват през 1962 година своя труд "An algorithm for the organization of information"). То е и първото самобалансиращо се дърво, като балансирането му е идеално – разликата в броя на върховете на лявото и дясното поддървета на всеки от върховете е най-много единица. АВЛ дървото позволява ефективно търсене, вмъкване и изтриване за време О в средния и най-лошия случаи, където n е броят на елементите в дървото. Поради идеалното си балансиране, вмъкването и изтриването на елементи може да доведе до нуждата от една или повече ротации на дървото с цел възстановяване на баланса.

АВЛ дърветата често са сравнявани с червено-черни дървета, тъй като и двете поддържат един и същ набор от операции за сходно Olog n време за основните операции. В сравнение с червено-черните дървета, АВЛ дърветата са по-строго балансирани, което води до по-бавно вмъкване и изтриване, но по-бързо обработване. Това ги прави привлекателни за структури от данни, които могат да бъдат изградени веднъж и заредени без реконструкция, като например езикови или програмни речници.

                                     

1. Операции

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

                                     

1.1. Операции Търсене

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

                                     

1.2. Операции Обхождане

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

                                     

1.3. Операции Вмъкване

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

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

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

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


                                     

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

Нека баланс факторът за определен връх 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 при вмъкване може да се извърши със следния примерен код:

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

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

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

                                     

1.5. Операции Изтриване

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

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

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

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

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

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

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

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

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

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



                                     

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

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

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

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

  • Височината на АВЛ дърво е строго по-малка от

log φ ⁡ n + 2 5) − 2 = log 2 ⁡ n + 2 + log 2 ⁡ 5 log 2 ⁡ φ − 2 ≈ 1.44 log 2 ⁡ n + 2 − 0.328 {\displaystyle \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},

където φ {\displaystyle \varphi } е златното сечение.

  • Височината на червено-черното дърво не по-голяма от 2 log ⁡ 2 n + 1 {\displaystyle 2\log 2n+1}.

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

Друга разлика е, както е посочено от Мелхорн стр. 165: "АВЛ дърветата не поддържат постоянни амортизирани разходи за актуализация", докато червено-черните дървета поддържат такива стр. 158.