Un arborele AVL definit ca o autoechilibrare Diferența dintre înălțimile subarborelui din stânga și subarborelui din dreapta pentru orice nod este cunoscută sub numele de factor de echilibru a nodului.
Arborele AVL este numit după inventatorii săi, Georgy Adelson-Velsky și Evgenii Landis, care l-au publicat în lucrarea lor din 1962 Un algoritm pentru organizarea informațiilor.
Exemplu de arbori AVL:
arborele AVL
Arborele de mai sus este AVL deoarece diferențele dintre înălțimile subarborilor din stânga și din dreapta pentru fiecare nod sunt mai mici sau egale cu 1.
Operații pe un arbore AVL:
Rotirea subarborilor într-un arbore AVL:
Un arbore AVL se poate roti în unul dintre următoarele patru moduri pentru a se menține echilibrat:
Rotație la stânga :
Când un nod este adăugat în subarborele din dreapta al subarborelui din dreapta, dacă arborele se dezechilibrează, facem o singură rotație la stânga.
Rotație la stânga în arborele AVL
Rotire dreapta :
Dacă se adaugă un nod la subarborele din stânga al subarborelui din stânga, arborele AVL se poate dezechilibra, facem o singură rotație la dreapta.
Rotire la dreapta în arborele AVL
Rotire stânga-dreapta :
O rotație stânga-dreapta este o combinație în care prima rotație la stânga are loc după ce se execută rotația la dreapta.
Rotație stânga-dreapta în arborele AVL
Rotire dreapta-stânga :
O rotație dreapta-stânga este o combinație în care prima rotație la dreapta are loc după executarea acelei rotații la stânga.
Rotire dreapta-stânga în arborele AVL
Aplicații ale arborelui AVL:
- Este folosit pentru a indexa înregistrări uriașe într-o bază de date și, de asemenea, pentru a căuta eficient în aceasta.
- Pentru toate tipurile de colecții în memorie, inclusiv seturi și dicționare, se folosesc arbori AVL.
- Aplicații de baze de date, unde inserările și ștergerile sunt mai puțin frecvente, dar sunt necesare căutări frecvente de date
- Software care necesită căutare optimizată.
- Se aplică în zonele corporative și în jocurile de poveste.
Avantajele arborelui AVL:
- Arborii AVL se pot autoechilibra.
- Cu siguranță nu este deformată.
- Oferă căutări mai rapide decât Red-Black Trees
- O complexitate mai bună a timpului de căutare în comparație cu alți copaci precum arborele binar.
- Înălțimea nu poate depăși log(N), unde, N este numărul total de noduri din arbore.
Dezavantajele arborelui AVL:
- Este greu de implementat.
- Are factori constanti mari pentru unele operatii.
- Mai puțin folosiți în comparație cu copacii roșu-negru.
- Datorită echilibrului său destul de strict, arborii AVL asigură operații complicate de inserare și îndepărtare pe măsură ce se efectuează mai multe rotații.
- Luați mai multă procesare pentru echilibrare.
Articole similare:
- Introducere în arbori de căutare binare – Structura datelor și tutoriale de algoritm
- Inserarea într-un arbore AVL
- Ștergerea într-un arbore AVL
