AVL Tree er opfundet af GM Adelson - Velsky og EM Landis i 1962. Træet er navngivet AVL til ære for dets opfindere.
AVL-træ kan defineres som et højdebalanceret binært søgetræ, hvor hver knude er forbundet med en balancefaktor, som beregnes ved at trække højden af dets højre undertræ fra højden af dets venstre undertræ.
Træet siges at være afbalanceret, hvis balancefaktoren for hver knude er mellem -1 til 1, ellers vil træet være ubalanceret og skal balanceres.
Balancefaktor (k) = højde (venstre(k)) - højde (højre(k))
Hvis balancefaktoren for en knude er 1, betyder det, at det venstre undertræ er et niveau højere end det højre undertræ.
Hvis balancefaktoren for en knude er 0, betyder det, at venstre undertræ og højre undertræ har samme højde.
Hvis balancefaktoren for en knude er -1, betyder det, at det venstre undertræ er et niveau lavere end det højre undertræ.
Et AVL-træ er vist i den følgende figur. Vi kan se, at balancefaktoren forbundet med hver node er mellem -1 og +1. derfor er det et eksempel på AVL-træ.
Kompleksitet
| Algoritme | Gennemsnitligt tilfælde | Værste tilfælde |
|---|---|---|
| Plads | på) | på) |
| Søg | o(log n) | o(log n) |
| Indsæt | o(log n) | o(log n) |
| Slet | o(log n) | o(log n) |
Operationer på AVL-træet
På grund af det faktum, at AVL-træet også er et binært søgetræ, udføres alle operationerne på samme måde, som de udføres i et binært søgetræ. Eftersøgning og krydsning fører ikke til krænkelse af ejendomsretten til AVL-træet. Indsættelse og sletning er dog de handlinger, der kan krænke denne egenskab, og de skal derfor revurderes.
| SN | Operation | Beskrivelse |
|---|---|---|
| 1 | Indskud | Indsættelse i AVL-træ udføres på samme måde, som det udføres i et binært søgetræ. Det kan dog føre til krænkelse i AVL træejendommen og derfor kan træet trænge til afbalancering. Træet kan afbalanceres ved at anvende rotationer. |
| 2 | Sletning | Sletning kan også udføres på samme måde, som det udføres i et binært søgetræ. Sletning kan også forstyrre balancen i træet, derfor bruges forskellige typer rotationer til at genbalancere træet. |
Hvorfor AVL-træ?
AVL-træet styrer højden af det binære søgetræ ved ikke at lade det blive skævt. Den tid, det tager for alle operationer i et binært søgetræ med højden h er O(h) . Det kan dog udvides til På) hvis BST bliver skæv (dvs. worst case). Ved at begrænse denne højde til log n, pålægger AVL-træet en øvre grænse for hver operation, der skal være O(log n) hvor n er antallet af noder.
AVL rotationer
Vi udfører rotation i AVL-træet kun i tilfælde af, at Balance Factor er andet end -1, 0 og 1 . Der er grundlæggende fire typer rotationer, som er som følger:
hvordan man parrer beats hovedtelefoner
- L L rotation: Indsat knude er i venstre undertræ af venstre undertræ af A
- R R rotation: Indsat knude er i højre undertræ af højre undertræ af A
- L R-rotation: Indsat knude er i højre undertræ af venstre undertræ af A
- R L rotation: Indsat knude er i venstre undertræ af højre undertræ af A
Hvor node A er den node, hvis balancefaktor er en anden end -1, 0, 1.
De første to rotationer LL og RR er enkeltrotationer og de næste to rotationer LR og RL er dobbeltrotationer. For at et træ skal være ubalanceret, skal minimumshøjden være mindst 2. Lad os forstå hver rotation
1. RR Rotation
Når BST bliver ubalanceret, på grund af at en knude er indsat i højre undertræ af højre undertræ af A, så udfører vi RR-rotation, RR-rotation er en rotation mod uret, som påføres på kanten under en knude med balancefaktor -2
I ovenstående eksempel har node A balancefaktor -2, fordi en node C er indsat i højre undertræ af et højre undertræ. Vi udfører RR-rotationen på kanten under A.
2. LL Rotation
Når BST bliver ubalanceret, på grund af at en knude er indsat i venstre undertræ i venstre undertræ af C, så udfører vi LL-rotation, LL-rotation er rotation med uret, som påføres på kanten under en knude med balancefaktor 2.
I ovenstående eksempel har node C balancefaktor 2, fordi en node A er indsat i venstre undertræ af C venstre undertræ. Vi udfører LL-rotationen på kanten under A.
3. LR Rotation
Dobbelt rotation er lidt hårdere end enkelt rotation, som allerede er forklaret ovenfor. LR-rotation = RR-rotation + LL-rotation, dvs. først RR-rotation udføres på undertræ og derefter LL-rotation udføres på fuldt træ, med fuldt træ mener vi den første knude fra stien til indsat knude, hvis balancefaktor er en anden end -1 , 0 eller 1.
Lad os forstå hvert eneste trin meget klart:
| Stat | Handling |
|---|---|
 | En knude B er blevet indsat i højre undertræ af A, venstre undertræ af C, på grund af hvilken C er blevet en ubalanceret knude med balancefaktor 2. Dette tilfælde er L R rotation, hvor: Indsat knude er i højre undertræ af venstre undertræ af C |
 | Da LR-rotation = RR + LL-rotation, udføres derfor RR (mod uret) på undertræ med rod til A først. Ved at udføre RR-rotation, node EN , er blevet det venstre undertræ af B . |
 | Efter at have udført RR-rotation er node C stadig ubalanceret, dvs. har balancefaktor 2, da indsat node A er til venstre for venstre for C |
 | Nu udfører vi LL rotation med uret på fuldt træ, dvs. på node C. node C er nu blevet det højre undertræ af node B, A er venstre undertræ af B |
 | Balancefaktoren for hver knude er nu enten -1, 0 eller 1, dvs. BST er nu balanceret. |
4. RL Rotation
Som allerede diskuteret, er dobbeltrotationer en smule hårdere end enkeltrotationer, som allerede er forklaret ovenfor. RL rotation = LL rotation + RR rotation, dvs. først udføres LL rotation på undertræ og derefter udføres RR rotation på fuldt træ, med fuldt træ mener vi den første knude fra stien for indsat knude, hvis balancefaktor er en anden end -1 , 0 eller 1.
| Stat | Handling |
|---|---|
 | En knude B er blevet indsat i venstre undertræ af C det højre undertræ af EN , på grund af hvilken A er blevet en ubalanceret knude med balancefaktor - 2. Dette tilfælde er RL-rotation, hvor: Indsat knude er i venstre undertræ af højre undertræ af A |
 | Som RL-rotation = LL-rotation + RR-rotation, dermed LL (med uret) på undertræet med rod til C udføres først. Ved at udføre RR-rotation, node C er blevet det rigtige undertræ af B . |
 | Efter at have udført LL-rotation, node EN er stadig ubalanceret, dvs. har balancefaktor -2, hvilket er på grund af højre-undertræet i højre-undertræsknuden A. |
 | Nu udfører vi RR-rotation (rotation mod uret) på fuldt træ, dvs. på node A. node C er nu blevet det højre undertræ af node B, og node A er blevet det venstre undertræ af B. |
 | Balancefaktoren for hver knude er nu enten -1, 0 eller 1, dvs. BST er nu balanceret. |
Q: Konstruer et AVL-træ med følgende elementer
H, I, J, B, A, E, C, F, D, G, K, L
1. Indsæt H, I, J
Ved indsættelse af ovenstående elementer, især i tilfælde af H, bliver BST ubalanceret, da balancefaktoren for H er -2. Da BST er højreskæv, vil vi udføre RR-rotation på knude H.
Det resulterende balancetræ er:
2. Indsæt B, A
Ved indsættelse af ovenstående elementer, især i tilfælde af A, bliver BST'en ubalanceret, da balancefaktoren for H og I er 2, betragter vi den første knude fra den sidst indsatte knude, dvs. H. Da BST'en fra H er venstreskæv, vi udfører LL Rotation på node H.
Det resulterende balancetræ er:
3. Indsæt E
Ved indsættelse af E bliver BST ubalanceret, da balancefaktoren for I er 2, da hvis vi rejser fra E til I, finder vi ud af, at den er indsat i venstre undertræ af højre undertræ af I, vi vil udføre LR-rotation på knude I. LR = RR + LL rotation
3 a) Vi udfører først RR-rotation på node B
Det resulterende træ efter RR-rotation er:
3b) Vi udfører først LL-rotation på knudepunktet I
Det resulterende afbalancerede træ efter LL-rotation er:
uri vs url
4. Indsæt C, F, D
Ved indsættelse af C, F, D bliver BST ubalanceret, da balancefaktoren for B og H er -2, da hvis vi rejser fra D til B finder vi ud af, at den er indsat i højre undertræ af venstre undertræ af B, vil vi udføre RL Rotation på node I. RL = LL + RR rotation.
4a) Vi udfører først LL-rotation på node E
Det resulterende træ efter LL-rotation er:
4b) Vi udfører derefter RR-rotation på node B
Det resulterende afbalancerede træ efter RR-rotation er:
5. Indsæt G
Ved indsættelse af G bliver BST ubalanceret, da balancefaktoren for H er 2, da hvis vi rejser fra G til H, finder vi ud af, at den er indsat i venstre undertræ af højre undertræ af H, vi vil udføre LR-rotation på knude I. LR = RR + LL rotation.
5 a) Vi udfører først RR-rotation på node C
Det resulterende træ efter RR-rotation er:
5 b) Vi udfører derefter LL-rotation på knudepunkt H
Det resulterende afbalancerede træ efter LL-rotation er:
6. Indsæt K
Ved indsættelse af K bliver BST ubalanceret, da balancefaktoren for I er -2. Da BST er højreskævet fra I til K, vil vi derfor udføre RR-rotation på knudepunktet I.
Det resulterende afbalancerede træ efter RR-rotation er:
knn
7. Indsæt L
Ved indsættelse er L-træet stadig afbalanceret, da balancefaktoren for hver node nu er enten -1, 0, +1. Derfor er træet et Balanceret AVL-træ
