Arborele AVL este inventat de GM Adelson - Velsky și EM Landis în 1962. Arborele este numit AVL în onoarea inventatorilor săi.
Arborele AVL poate fi definit ca un arbore de căutare binar echilibrat în înălțime în care fiecare nod este asociat cu un factor de echilibru care este calculat prin scăderea înălțimii sub-arborelui din dreapta din cea a sub-arborelui stâng.
Arborele se spune că este echilibrat dacă factorul de echilibru al fiecărui nod este între -1 și 1, în caz contrar, arborele va fi dezechilibrat și va trebui echilibrat.
Factorul de echilibru (k) = înălțime (stânga (k)) - înălțime (dreapta (k))
Dacă factorul de echilibru al oricărui nod este 1, înseamnă că sub-arborele din stânga este cu un nivel mai mare decât sub-arborele din dreapta.
Dacă factorul de echilibru al oricărui nod este 0, înseamnă că sub-arborele din stânga și sub-arborele din dreapta conțin înălțime egală.
Dacă factorul de echilibru al oricărui nod este -1, înseamnă că sub-arborele din stânga este cu un nivel mai jos decât sub-arborele din dreapta.
Un arbore AVL este dat în figura următoare. Putem vedea că factorul de echilibru asociat fiecărui nod este între -1 și +1. prin urmare, este un exemplu de arbore AVL.
Complexitate
| Algoritm | Caz mediu | Cel mai rău caz |
|---|---|---|
| Spaţiu | pe) | pe) |
| Căutare | o(log n) | o(log n) |
| Introduce | o(log n) | o(log n) |
| Șterge | o(log n) | o(log n) |
Operații pe arborele AVL
Datorită faptului că, arborele AVL este și un arbore de căutare binar, prin urmare, toate operațiunile sunt efectuate în același mod în care sunt efectuate într-un arbore de căutare binar. Căutarea și traversarea nu duc la încălcarea proprietății arborelui AVL. Cu toate acestea, inserarea și ștergerea sunt operațiunile care pot încălca această proprietate și, prin urmare, trebuie revizuite.
| SN | Operațiune | Descriere |
|---|---|---|
| 1 | Inserare | Inserarea în arborele AVL este efectuată în același mod ca și într-un arbore binar de căutare. Cu toate acestea, poate duce la încălcarea proprietății arborelui AVL și, prin urmare, arborele poate avea nevoie de echilibrare. Arborele poate fi echilibrat prin aplicarea rotațiilor. |
| 2 | Ștergere | Ștergerea poate fi, de asemenea, efectuată în același mod în care se realizează într-un arbore de căutare binar. De asemenea, ștergerea poate perturba echilibrul arborelui, prin urmare, sunt folosite diferite tipuri de rotații pentru a reechilibra arborele. |
De ce arborele AVL?
Arborele AVL controlează înălțimea arborelui de căutare binar fără a-l lăsa să fie deformat. Timpul necesar pentru toate operațiile dintr-un arbore binar de căutare cu înălțimea h este Oh) . Cu toate acestea, poate fi extins la Pe) dacă BST devine denaturată (adică cel mai rău caz). Limitând această înălțime la log n, arborele AVL impune o limită superioară fiecărei operațiuni care urmează să fie O(log n) unde n este numărul de noduri.
Rotații AVL
Efectuăm rotația în arborele AVL numai în cazul în care Balance Factor este altul decât -1, 0 și 1 . Există în principiu patru tipuri de rotații, care sunt după cum urmează:
- Rotație L L: nodul inserat se află în subarborele din stânga al subarborelui din stânga al lui A
- Rotație R R : nodul inserat este în subarborele din dreapta al subarborelului din dreapta al lui A
- Rotație L R: nodul inserat este în subarborele din dreapta al subarborelului din stânga al lui A
- Rotație R L: nodul inserat se află în subarborele din stânga al subarborelui din dreapta al lui A
Unde nodul A este nodul al cărui factor de echilibru este altul decât -1, 0, 1.
comanda java return
Primele două rotații LL și RR sunt rotații simple, iar următoarele două rotații LR și RL sunt rotații duble. Pentru ca un copac să fie dezechilibrat, înălțimea minimă trebuie să fie de cel puțin 2, Să înțelegem fiecare rotație
1. Rotație RR
Când BST devine dezechilibrat, din cauza inserării unui nod în subarborele din dreapta al subarborelui drept al lui A, atunci efectuăm rotația RR, rotația RR este o rotație în sens invers acelor de ceasornic, care se aplică pe marginea de sub un nod având factor de echilibru -2
În exemplul de mai sus, nodul A are factor de echilibru -2 deoarece un nod C este inserat în subarborele din dreapta al subarborelui A din dreapta. Efectuăm rotația RR pe marginea de sub A.
2. Rotație LL
Când BST devine dezechilibrat, datorită inserării unui nod în subarborele stâng al subarborelului din stânga al lui C, atunci efectuăm rotația LL, rotația LL este rotație în sensul acelor de ceasornic, care se aplică pe marginea de sub un nod având factor de echilibru 2.
În exemplul de mai sus, nodul C are un factor de echilibru 2 deoarece un nod A este inserat în subarborele din stânga al subarborelui din stânga C. Efectuăm rotația LL pe marginea de sub A.
3. Rotație LR
Rotațiile duble sunt puțin mai dure decât rotația simplă, care a fost deja explicată mai sus. Rotația LR = Rotația RR + Rotația LL, adică prima rotație RR este efectuată pe subarbore și apoi rotația LL este efectuată pe arbore complet, prin arbore complet înțelegem primul nod din calea nodului inserat al cărui factor de echilibru este altul decât -1 , 0 sau 1.
Să înțelegem fiecare pas foarte clar:
| Stat | Acțiune |
|---|---|
 | Un nod B a fost inserat în subarborele din dreapta al lui A subarborele din stânga al lui C, din cauza căruia C a devenit un nod dezechilibrat având factor de echilibru 2. Acest caz este rotația L R unde: Nodul inserat este în subarborele din dreapta al subarborelului din stânga C |
 | Deoarece rotația LR = rotația RR + LL, deci RR (în sens invers acelor de ceasornic) pe subarborele înrădăcinat la A este efectuat mai întâi. Făcând rotația RR, nod A , a devenit subarborele din stânga al B . |
 | După efectuarea rotației RR, nodul C este încă dezechilibrat, adică are factor de echilibru 2, deoarece nodul A inserat este în stânga din stânga C |
 | Acum efectuăm rotația LL în sensul acelor de ceasornic pe arbore complet, adică pe nodul C. nodul C a devenit acum subarborele din dreapta al nodului B, A este subarborele din stânga al lui B |
 | Factorul de echilibru al fiecărui nod este acum fie -1, 0 sau 1, adică BST este echilibrat acum. |
4. Rotație RL
După cum sa discutat deja, acele rotații duble sunt puțin mai dure decât rotația simplă, care a fost deja explicată mai sus. Rotația RL = rotația LL + rotația RR, adică prima rotație LL este efectuată pe subarbore și apoi rotația RR este efectuată pe arbore complet, prin arbore complet înțelegem primul nod din calea nodului inserat al cărui factor de echilibru este altul decât -1 , 0 sau 1.
| Stat | Acțiune |
|---|---|
 | Un nod B a fost inserat în subarborele din stânga al C subarborele drept al A , din cauza căruia A a devenit un nod dezechilibrat având factor de echilibru - 2. Acest caz este rotația RL unde: Nodul inserat este în subarborele stâng al subarborelului din dreapta al lui A |
 | Deoarece rotația RL = rotația LL + rotația RR, prin urmare, LL (în sensul acelor de ceasornic) pe subarborele înrădăcinat la C se efectuează mai întâi. Făcând rotația RR, nod C a devenit subarborele potrivit al B . |
 | După efectuarea rotației LL, nod A este încă dezechilibrat, adică are factor de echilibru -2, ceea ce se datorează subarborelui drept al nodului subarboresc drept A. |
 | Acum efectuăm rotația RR (rotație în sens invers acelor de ceasornic) pe arbore complet, adică pe nodul A. nodul C a devenit acum subarborele din dreapta al nodului B, iar nodul A a devenit subarborele din stânga al lui B. |
 | Factorul de echilibru al fiecărui nod este acum fie -1, 0 sau 1, adică BST este echilibrat acum. |
Î: Construiți un arbore AVL având următoarele elemente
H, I, J, B, A, E, C, F, D, G, K, L
1. Introduceți H, I, J
La introducerea elementelor de mai sus, în special în cazul lui H, BST devine dezechilibrat deoarece factorul de echilibru al lui H este -2. Deoarece BST este declinat la dreapta, vom efectua Rotația RR pe nodul H.
Arborele de echilibru rezultat este:
2. Introduceți B, A
La inserarea elementelor de mai sus, în special în cazul lui A, BST devine dezechilibrat deoarece factorul de echilibru al lui H și I este 2, luăm în considerare primul nod din ultimul nod inserat, adică H. Deoarece BST din H este oblic la stânga, vom efectua LL Rotation pe nodul H.
Arborele de echilibru rezultat este:
3. Introduceți E
La inserarea lui E, BST devine dezechilibrat deoarece factorul de echilibru al lui I este 2, deoarece dacă călătorim de la E la I aflăm că este inserat în subarborele din stânga al subarborelui din dreapta al lui I, vom efectua Rotația LR pe nodul I. LR = rotatie RR + LL
3 a) Mai întâi efectuăm rotația RR pe nodul B
Arborele rezultat după rotația RR este:
3b) Mai întâi efectuăm rotația LL pe nodul I
Arborele echilibrat rezultat după rotația LL este:
4. Introduceți C, F, D
ce este obiectul java
La inserarea C, F, D, BST devine dezechilibrat deoarece factorul de echilibru al lui B și H este -2, deoarece dacă călătorim de la D la B aflăm că este inserat în subarborele din dreapta al subarborelului din stânga al lui B, vom efectua RL Rotație pe nodul I. RL = LL + RR rotație.
4a) Mai întâi efectuăm rotația LL pe nodul E
Arborele rezultat după rotația LL este:
4b) Apoi efectuăm rotația RR pe nodul B
Arborele echilibrat rezultat după rotația RR este:
5. Introduceți G
La inserarea lui G, BST devine dezechilibrat deoarece factorul de echilibru al lui H este 2, deoarece dacă călătorim de la G la H, aflăm că este inserat în subarborele din stânga al subarborelui din dreapta al lui H, vom efectua Rotația LR pe nodul I. LR = RR + LL rotație.
5 a) Mai întâi efectuăm rotația RR pe nodul C
Arborele rezultat după rotația RR este:
5 b) Apoi efectuăm rotația LL pe nodul H
Arborele echilibrat rezultat după rotația LL este:
6. Introduceți K
La introducerea K, BST devine dezechilibrat, deoarece factorul de echilibru al lui I este -2. Deoarece BST este declinat la dreapta de la I la K, prin urmare vom efectua Rotația RR pe nodul I.
Arborele echilibrat rezultat după rotația RR este:
7. Introduceți L
La inserarea arborelui L este încă echilibrat, deoarece factorul de echilibru al fiecărui nod este acum fie -1, 0, +1. Prin urmare, arborele este un arbore AVL echilibrat
