Ce este un copac AVL?
Un arbore AVL este un subtip de arbore de căutare binară. Numit după inventatorii săi Adelson, Velskii și Landis, arborii AVL au proprietatea de auto-echilibrare dinamică în plus față de toate proprietățile prezentate de arborii de căutare binari.
Un BST este o structură de date compusă din noduri. Are următoarele garanții:
- Fiecare copac are un nod rădăcină (în partea de sus).
- Nodul rădăcină are zero, unul sau două noduri copil.
- Fiecare nod copil are zero, unul sau două noduri copil și așa mai departe.
- Fiecare nod are până la doi copii.
- Pentru fiecare nod, descendenții săi din stânga sunt mai mici decât nodul curent, care este mai mic decât descendenții din dreapta.
Arborii AVL au o garanție suplimentară:
- Diferența dintre adâncimea subarborilor dreapta și stânga nu poate fi mai mult decât una. Pentru a menține această garanție, o implementare a unui AVL va include un algoritm pentru a reechilibra arborele atunci când adăugarea unui element suplimentar ar deranja această garanție.
Arborii AVL au cel mai rău caz de căutare, inserare și ștergere a timpului O (jurnal n).
Rotire dreapta
Rotire stânga
Procesul de inserție AVL
Veți efectua o inserare similară cu o inserție normală în arborele de căutare binară. După inserare, remediați proprietatea AVL utilizând rotații la stânga sau la dreapta.
- Dacă există un dezechilibru în copilul stâng al subarborelui drept, atunci efectuați o rotație stânga-dreapta.
- Dacă există un dezechilibru în copilul stâng al subarborelui stâng, atunci efectuați o rotație dreaptă.
- Dacă există un dezechilibru în copilul drept al subarborelui drept, atunci efectuați o rotație la stânga.
- Dacă există un dezechilibru în copilul drept al subarborelui stâng, atunci efectuați o rotație dreapta-stânga.
Un arbore AVL este un arbore de căutare binar auto-echilibrat. Un arbore AVL este un arbore binar de căutare care are următoarele proprietăți: -> Subarborii fiecărui nod diferă în înălțime cu cel mult unul. -> Fiecare sub-copac este un copac AVL.
Arborele AVL verifică înălțimea subarborilor din stânga și din dreapta și asigură că diferența nu depășește 1. Această diferență se numește Factorul de echilibru. Înălțimea unui arbore AVL este întotdeauna O (Logn) unde n este numărul de noduri din arbore.
Rotații arbore AVL
În arborele AVL, după efectuarea fiecărei operațiuni, cum ar fi inserarea și ștergerea, trebuie să verificăm factorul de echilibru al fiecărui nod din arbore. Dacă fiecare nod îndeplinește condiția factorului de echilibru, atunci încheiem operația, altfel trebuie să o echilibrăm. Folosim operații de rotație pentru a face arborele echilibrat ori de câte ori arborele devine dezechilibrat din cauza oricărei operații.
Operațiile de rotație sunt utilizate pentru a face un copac echilibrat. Există patru rotații și sunt clasificate în două tipuri:
Rotație unică la stânga (rotație LL)
În rotația LL, fiecare nod se deplasează cu o poziție la stânga din poziția curentă.
Rotație unică dreaptă (Rotație RR)
În RR Rotation fiecare nod se deplasează cu o poziție spre dreapta din poziția curentă.
Rotire stânga dreapta (rotire LR)
Rotația LR este o combinație de rotație simplă la stânga urmată de rotație simplă la dreapta. În LR Rotation, mai întâi fiecare nod se deplasează o poziție la stânga, apoi o poziție la dreapta din poziția curentă.
Rotire stânga dreapta (rotire RL)
Rotația RL este o combinație de rotație unică dreaptă urmată de o rotație simplă stângă. În RL Rotation, mai întâi fiecare nod se deplasează o poziție la dreapta, apoi o poziție la stânga din poziția curentă.
Analiza timpului arborilor AVL
Arborele AVL este arborele de căutare binar cu proprietăți suplimentare, diferența dintre înălțimea subarborelui stâng și subarborele drept al oricărui nod nu poate fi mai mare de 1.
Algoritm Cel mai rău caz: Spațiu: O(n), Timp: O(n)
Aplicarea copacilor AVL
Arborii AVL sunt benefici în cazurile în care proiectați o bază de date în care inserțiile și ștergerile nu sunt atât de frecvente, dar trebuie să căutați frecvent elementele prezente acolo.
