Arborele AVL

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 octombrie 2021; verificările necesită 6 modificări .
arborele AVL
Engleză  A.V.L arbore
Tip de arborele de căutare
Anul inventiei 1968
Autor Adelson-Velsky Georgy Maksimovici și Landis Evgeny Mihailovici
Complexitatea în simbolurile O
In medie În cel mai rău caz
Consumul de memorie Pe) Pe)
Căutare O(log n) O(log n)
Introduce O(log n) O(log n)
Îndepărtarea O(log n) O(log n)
 Fișiere media la Wikimedia Commons

Un arbore AVL este un arbore de căutare binar  echilibrat pe înălțime : pentru fiecare dintre vârfurile sale, înălțimea celor doi subarbori diferă cu cel mult 1.

AVL este o abreviere formată din primele litere ale creatorilor (oameni de știință sovietici) Adelson-Velsky Georgy Maksimovici și Landis Evgeny Mikhailovici .

Înălțimea maximă

Înălțimea maximă a unui arbore AVL pentru un număr dat de noduri [1] :

Unde:

(ridica)

(rotunjind in jos)

(rotunjind în jos).

Numărul de înălțimi posibile este foarte limitat în practică (cu adresare pe 32 de biți, înălțimea maximă este de 45, cu adresare pe 48 de biți este de 68), așa că probabil este mai bine să precalculați toate valorile numărului minim de noduri pentru fiecare înălțime folosind formula recursivă pentru arborele Fibonacci :

,

,

.

Valorile intermediare ale numărului de noduri vor corespunde înălțimii anterioare (inferioare).

Echilibrare

În ceea ce privește un arbore AVL, echilibrarea vârfurilor este o operație care, dacă diferența de înălțime a subarborilor din stânga și din dreapta = 2, schimbă legăturile părinte-copil din subarborele acestui vârf, astfel încât diferența să devină <= 1, în caz contrar, nu schimba nimic. Rezultatul indicat se obține prin rotații ale subarborelui vârfului dat.

Se folosesc 4 tipuri de rotații:

1. Rotație mică la stânga Această rotație este utilizată atunci când diferența de înălțime dintre subarborele a și subarborele b este 2 și înălțimea C <= înălțimea R.

2. Rotație mare la stânga Această rotație este folosită atunci când diferența de înălțime dintre subarborele a și subarborele b este 2 și înălțimea subarborelui c > înălțimea R.

3. Rotație mică la dreapta Această rotație este utilizată atunci când diferența de înălțime dintre subarborele a și subarborele b este 2 și înălțimea C <= înălțimea L.

4. Rotație mare la dreapta Această rotație este utilizată atunci când diferența de înălțime dintre subarborele a și subarborele b este 2 și înălțimea subarborelui c > înălțimea L.

În fiecare caz, este suficient să demonstrați pur și simplu că operația duce la rezultatul dorit și că înălțimea totală scade cu cel mult 1 și nu poate crește. De asemenea, o rotire mare este o combinație de rotire mică la dreapta și la stânga. Din cauza condiției de echilibrare, înălțimea arborelui este O(log(N)), unde N este numărul de vârfuri, deci adăugarea unui element necesită operații O(log(N)).

Algoritm pentru adăugarea unui vârf

Indicatorul de echilibru va fi interpretat în continuare ca diferența dintre înălțimea subarborilor din stânga și din dreapta, iar algoritmul se va baza pe tipul TAVLTree descris mai sus. Direct la introducere (foaia) i se atribuie un sold zero. Procesul de includere a unui vârf constă din trei părți (acest proces este descris de Niklaus Wirth în Algoritmi și structuri de date):

  1. Treceți de-a lungul căii de căutare până când suntem siguri că cheia nu se află în copac.
  2. Includerea unui nou vârf în arbore și determinarea indicatorilor de echilibrare rezultați.
  3. „Se retrage” înapoi pe calea căutării și verificării la fiecare vârf al indicatorului de echilibru. Dacă este necesar, echilibrați.

Vom reveni ca rezultat al funcției dacă înălțimea copacului a scăzut sau nu. Să presupunem că un proces din ramura stângă revine la părinte (recursiunea se întoarce), atunci sunt posibile trei cazuri: { h l  - înălțimea subarborelului din stânga, h r  - înălțimea subarborelui din dreapta } Includerea unui vârf în subarborele din stânga va avea ca rezultat

  1. h l < h r : egalizează h l = h r . Nu trebuie făcut nimic.
  2. h l = h r : acum subarborele din stânga va fi mai mare cu unu, dar echilibrarea nu este necesară încă.
  3. h l > h r : acum h l  - h r = 2, - este necesară echilibrarea.

În a treia situație, este necesar să se determine echilibrarea subarborelui din stânga. Dacă subarborele din stânga acestui vârf (Tree^.left^.left) este mai mare decât cel din dreapta (Tree^.left^.right), atunci este necesară o rotație mare la dreapta, altfel va fi suficientă una mică la dreapta. Raționament similar (simetric) poate fi dat pentru includerea în subarborele din dreapta.

Algoritm pentru ștergerea unui vârf

Pentru simplitate, descriem un algoritm de ștergere recursiv. Dacă vârful este o frunză, atunci îl ștergem și numim echilibrarea tuturor strămoșilor săi în ordine de la părinte la rădăcină. În caz contrar, găsim cel mai apropiat vârf în valoare în subarborele cu cea mai mare înălțime (dreapta sau stânga) și îl mutăm în locul vârfului de șters, în timp ce apelăm procedura de eliminare.

Să demonstrăm că acest algoritm păstrează echilibrul. Pentru aceasta, demonstrăm prin inducție asupra înălțimii arborelui că după îndepărtarea unor vârfuri din arbore și echilibrarea ulterioară, înălțimea arborelui scade cu cel mult 1. Baza inducției: Pentru o frunză, evident adevărat. Etapa de inducție: Fie condiția de echilibru la rădăcină (după ștergere, rădăcina se poate schimba) nu este încălcată, atunci înălțimea arborelui dat nu s-a schimbat, fie cel strict mai mic dintre subarbori a scăzut => înălțimea înainte de echilibrare a scăzut neschimbat => după aceea va scădea cu cel mult 1.

Evident, ca urmare a acestor acțiuni, procedura de eliminare este apelată de cel mult 3 ori, deoarece vârful eliminat de al doilea apel nu are niciunul dintre subarbori. Dar găsirea celui mai apropiat necesită operații O(N) de fiecare dată. Posibilitatea de optimizare devine evidentă: căutarea celui mai apropiat vârf poate fi efectuată de-a lungul marginii subarborelui, ceea ce reduce complexitatea la O(log(N)).

Inserare de sus în jos nerecursivă într-un arbore AVL

Un algoritm nerecursiv este mai complicat decât unul recursiv.

  1. Se găsesc punctul de inserție și vârful, a căror înălțime nu se va modifica în timpul inserării (acesta este vârful pentru care înălțimea subarborelui din stânga nu este egală cu înălțimea celui din dreapta; îl vom numi PrimeNode)
  2. Coborârea de la PrimeNode până la punctul de inserare se realizează cu o modificare a soldurilor
  3. PrimeNode se reechilibrează atunci când există un depășire

Ștergerea nerecursivă de sus în jos a unui arbore AVL

Pentru a implementa ștergerea, vom proceda de la același principiu ca și la inserare: vom găsi un vârf, ștergerea din care nu va duce la modificarea înălțimii sale. Există două cazuri:

  1. înălțimea subarborelui din stânga este egală cu înălțimea arborelui secundar din dreapta (cu excepția cazului în care frunza nu are subarbori)
  2. înălțimea copacului în direcția de mișcare este mai mică decât opusul („fratele” direcției) și echilibrul „fratelui” este 0 (analizarea acestei opțiuni este destul de complicată, deci încă nu există nicio dovadă)

Pentru ușurință de înțelegere, algoritmul de mai sus nu conține nicio optimizare. Spre deosebire de algoritmul recursiv, vârful eliminat găsit este înlocuit cu valoarea din subramura stângă. Acest algoritm poate fi optimizat în același mod ca și cel recursiv (datorită faptului că după găsirea vârfului de îndepărtat se cunoaște direcția de mișcare):

  1. căutăm elementul de șters și pe parcurs găsim minunatul nostru top
  2. facem modificari in solduri, daca este necesar, facem reechilibrare
  3. ștergeți elementul nostru (de fapt nu îl ștergem, dar îi înlocuim cheia și valoarea, contabilizarea permutărilor nodurilor va fi puțin mai complicată)

Aranjarea soldurilor la scoatere

După cum sa menționat deja, dacă vârful care trebuie șters este o frunză, atunci acesta este șters, iar traversarea inversă a arborelui are loc de la părintele frunzei șterse. Dacă nu o frunză, se găsește un „înlocuitor” pentru ea, iar traversarea inversă a arborelui vine de la părintele „înlocuitor”. Imediat după îndepărtarea elementului - „înlocuirea” primește soldul nodului eliminat.

În bypass invers: dacă în timpul trecerii la părinte au venit din stânga, soldul crește cu 1, dacă au venit din dreapta, scade cu 1.

Acest lucru se face până când echilibrul se schimbă la -1 sau 1 (observați diferența cu inserarea unui element!): în acest caz, o astfel de modificare a echilibrului ar indica o înălțime constantă a deltei subarborilor. Rotațiile urmează aceleași reguli ca la introducere.

Aranjarea soldurilor la o singură tură

Denota:

Dacă rotația are loc atunci când un element este inserat, atunci echilibrul pivotului este fie 1, fie -1. În acest caz, după rotație, soldurile ambelor sunt setate egale cu 0. La ștergere, totul este diferit: soldul lui Pivot poate deveni egal cu 0 (acest lucru este ușor de verificat).

Iată un tabel rezumativ al dependenței balanțelor finale de direcția de rotație și echilibrul inițial al nodului Pivot:

Direcția de întoarcere Vechiul Balanță Pivot Curent nou.Balance Noul echilibru Pivot
Stanga sau dreapta -1 sau +1 0 0
Dreapta 0 -unu +1
Stânga 0 +1 -unu

Solduri duble de rotație

Pivot și Current sunt aceleași, dar se adaugă un al treilea membru al turnului. Să-l desemnăm pentru „Jos”: este (cu o viraj dublă la dreapta) fiul stâng al lui Pivot, iar cu o stânga dublă - fiul drept al lui Pivot.

Cu această rotație, Bottom dobândește întotdeauna un echilibru de 0 ca rezultat, dar aranjarea soldurilor pentru Pivot și Current depinde de soldul său inițial.

Iată un tabel rezumativ al dependenței balanțelor finale de sensul de rotație și echilibrul inițial al nodului de jos:

Direcţie Echilibrul de jos vechi Curent nou.Balance Noul echilibru Pivot
Stanga sau dreapta 0 0 0
Dreapta +1 0 -unu
Dreapta -unu +1 0
Stânga +1 -unu 0
Stânga -unu 0 +1

Evaluarea performanței

Din formula de mai sus, înălțimea unui arbore AVL nu va depăși niciodată înălțimea unui arbore perfect echilibrat cu mai mult de 45%. Pentru mari , avem estimarea . Astfel, efectuarea operațiilor de bază necesită o ordine a comparațiilor. Sa constatat experimental că are loc o echilibrare pentru fiecare 2 incluziuni și pentru fiecare 5 excepții.

Vezi și

Copaci echilibrați (auto-echilibrați):

Note

  1. ↑ D. Knut. Arta programarii. Sortați și căutați. - S. 460.

Literatură