Introducere în arborele AVL în structura datelor
Arborele AVL din structura de date se referă la arborele Adelson, Velski și Landis. Aceasta este o versiune îmbunătățită a arborelui de căutare binară. Are toate caracteristicile din Arborele de căutare binară, dar diferă doar deoarece mențin o diferență între înălțimea subarborei stânga și subarbore dreapta și asigură, de asemenea, că valoarea sa este <= 1 în Arbore, aceasta este cunoscută sub numele de Balanță. Factor.
Balance Factor = height(left-subtree) − height(right-subtree)
De exemplu: Luați în considerare următorii arbori
În exemplul de mai sus, înălțimea subarborei dreapta = 2 și stânga = 3, astfel BF = 2, care este <= 1, deci arborele este echilibrat.
De ce avem nevoie de un arbore AVL în DS?
În timp ce lucrăm cu Arborele de căutare binar, întâlnim un scenariu în care elementele sunt ordonate. În astfel de cazuri, toate elementele tabloului sunt dispuse pe o parte a rădăcinii, acest lucru duce la o creștere a complexității în timp a căutării unui element într-un tablou, iar complexitatea devine - O (n) adică complexitatea în cel mai rău caz al arborelui . Pentru a rezolva astfel de probleme și a reduce timpul de căutare, arbori AVL au fost inventați de Adelson, Velski și Landis.
Exemplu:
În figura de mai sus, Înălțimea subtreei stângi = 3 a fost ca
Înălțimea subtreei drepte = 0
Astfel Factorul de echilibru = 3-0 = 3. Astfel căutarea unui element într-un astfel de arbore are O (n) complexitate, care este similară cu căutarea liniară. Pentru a evita acel arbore complex de căutare AVL a fost introdus acolo unde fiecare nod din copac trebuie să se mențină
factor de echilibru <= 1, altfel trebuie efectuate diferite tehnici de rotație pentru a echilibra un astfel de arbore.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Tipuri de rotatii
Atunci când factorul de echilibru pentru arbore nu îndeplinește <= 1 condiție, atunci trebuie să se efectueze rotații pentru a-l transforma într-un arbore echilibrat.
Există 4 tipuri de rotații:
1. Rotație stângă: Dacă adăugarea unui nod la dreapta arborelui face dezechilibru, atunci, în acest caz, trebuie să se efectueze Rotația stângă.
2. Rotația dreaptă: Dacă adăugarea unui nod la stânga arborelui face ca dezechilibrul nodului să fie efectuată, atunci trebuie să se efectueze Rotația dreapta. Cu alte cuvinte, Când numărul de noduri crește pe partea stângă, apare nevoia de a muta elementele în partea dreaptă pentru a-l echilibra, astfel se spune că este Rotirea Dreaptă.
3. Rotație stânga-dreapta: acest tip de rotație este o combinație a celor 2 rotații de mai sus explicate. Acest tip de rotație are loc atunci când un element este adăugat la subtree dreapta a unui arbore din stânga.
Într-un astfel de caz mai întâi, efectuați rotația stângă pe subtree urmată de o rotație dreapta a arborelui stâng.
4. Rotație dreapta-stânga: acest tip de rotație este, de asemenea, compus dintr-o secvență de peste 2 rotații. Acest tip de rotație este necesar atunci când un element este adăugat la stânga subtreei drepte și arborele devine dezechilibrat. Într-un astfel de caz, efectuăm mai întâi rotația din dreapta pe subtree dreapta și apoi rotirea din stânga în arborele din dreapta.
Operațiuni în arborele AVL în DS
Mai jos de 3 operații care pot fi efectuate pe arborele AVL: -
1. Căutați
Această operație este similară cu efectuarea unei căutări în Arborele căutării binare. Etapele urmate sunt următoarele:
- Citiți elementul furnizat de utilizator spune x.
- Comparați elementul din rădăcină, dacă este același, apoi ieșiți, altfel, treceți la pasul următor.
- Dacă x
Altfel mergeți la copilul potrivit și comparați din nou.
Urmați procesele B și C până găsiți elementul și ieșiți.
Acest proces are O (log n) complexitate.
Exemplu:
 | Luați în considerare acest Arbore, unde trebuie să efectuăm o căutare pentru valoarea nodului 9. Mai întâi, lasă x = 9, valoarea rădăcină (12)> x apoi, valoarea trebuie să fie în subcentrul stâng al elementului rădăcină. |
 | Acum x este comparat cu valoarea nodului 3 x> 3, deci trebuie să mergem spre subtree potrivită. |
 | Acum x este comparat cu nodul (9), unde 9 == 9 se întoarce. Astfel, căutarea elementelor se completează în arbore. |
2. Inserarea
În timp ce inserați un element în arborele AVL, trebuie să găsim elementul de locație care trebuie inserat și apoi elementul este atașat la fel ca o inserție în BST, dar după aceea, este verificat dacă arborele este încă echilibrat sau nu adică factorul de echilibru al unui nod este <= 1. Și rotații speciale sunt efectuate după cum este necesar.
Complexitatea este O (log n).
Exemplu: Luați în considerare arborele de mai jos,
 | Fiecare nod are un factor de echilibru ca 0, -1 sau 1, astfel arborele este echilibrat. Acum permiteți ce se întâmplă atunci când este introdus un nod cu valoarea 1. Primul arbore este traversat pentru a găsi locația unde trebuie introdus … 1 <2 este astfel scris ca un copil stâng al nodului (2). |
 | După inserare, nodul (9) devine dezechilibrat cu un factor de echilibru = 2. Acum este supus unei rotații corecte. |
 | Un arbore devine echilibru după rotirea din dreapta și astfel operațiunea de inserare este finalizată cu succes. |
3. Ștergere
Ștergerea unui element din arborele AVL include, de asemenea, căutarea unui element din copac și apoi ștergerea acestuia. Operația de căutare este aceeași ca BST, iar după găsirea elementului care trebuie eliminat este eliminat din arbore și elementele sunt ajustate pentru a-l face din nou BST. După ce aceste elemente sunt verificate pentru a avea un factor de echilibru de 0, -1 sau 1 și astfel sunt efectuate rotații adecvate pentru a-l echilibra.
Complexitate dacă O (log n).
 | Luați în considerare arborele dat, ale cărui toate au un factor de echilibru de 0, -1 sau 1. Acum să ștergem un nod cu valoarea 16. Primul arbore este traversat pentru a găsi nodul cu valoarea 16 la fel ca un algoritm de căutare. |
 | Nodul 16 va fi înlocuit cu predecesorul inordonat al acestui nod care este cel mai mare element din subtree stânga, adică 12 Arborele s-a dezechilibrat, astfel încât trebuie să se efectueze rotația. |
 | Acum fiecare nod a devenit echilibrat. |
Concluzie - arborele AVL în structura datelor
Arborele AVL este un descendent al arborelui de căutare binară, dar își depășește dezavantajul de a crește complexitatea în cazul în care elementele sunt sortate. Monitorizează factorul de echilibru al arborelui ca fiind 0 sau 1 sau -1. În cazul în care arborele devine dezechilibrat se efectuează tehnici de rotație corespunzătoare pentru a echilibra arborele.
Articole recomandate
Acesta este un ghid pentru arborele AVL în structura datelor. Aici vom discuta Introducerea, Operațiuni pe arborele AVL în DS și Tipuri de rotații. De asemenea, puteți parcurge și alte articole conexe pentru a afla mai multe -
- Elemente jQuery
- Ce este știința datelor
- Tipuri de arbori din structura datelor
- C # Tipuri de date