AVL Tree er oppfunnet av GM Adelson - Velsky og EM Landis i 1962. Treet heter AVL til ære for oppfinnerne.
AVL-tre kan defineres som et høydebalansert binært søketre der hver node er assosiert med en balansefaktor som beregnes ved å subtrahere høyden til høyre undertre fra høyden til venstre undertre.
Treet sies å være balansert hvis balansefaktoren for hver node er mellom -1 til 1, ellers vil treet være ubalansert og må balanseres.
Balansefaktor (k) = høyde (venstre(k)) - høyde (høyre(k))
Hvis balansefaktoren til en node er 1, betyr det at det venstre undertreet er ett nivå høyere enn det høyre undertreet.
Hvis balansefaktoren til en node er 0, betyr det at venstre undertre og høyre undertre har samme høyde.
Hvis balansefaktoren til en node er -1, betyr det at det venstre undertreet er ett nivå lavere enn det høyre undertreet.
Et AVL-tre er gitt i følgende figur. Vi kan se at balansefaktor knyttet til hver node er mellom -1 og +1. derfor er det et eksempel på AVL-tre.
Kompleksitet
| Algoritme | Gjennomsnittlig tilfelle | I verste fall |
|---|---|---|
| Rom | på) | på) |
| Søk | o(log n) | o(log n) |
| Sett inn | o(log n) | o(log n) |
| Slett | o(log n) | o(log n) |
Operasjoner på AVL-treet
På grunn av det faktum at AVL-tre også er et binært søketre, utføres derfor alle operasjonene på samme måte som de utføres i et binært søketre. Søking og kryssing fører ikke til brudd på eiendom av AVL-tre. Innsetting og sletting er imidlertid operasjonene som kan krenke denne egenskapen, og derfor må de ses på nytt.
| SN | Operasjon | Beskrivelse |
|---|---|---|
| 1 | Innsetting | Innsetting i AVL-tre utføres på samme måte som det utføres i et binært søketre. Det kan imidlertid føre til brudd på AVL-treeiendommen og derfor kan treet trenge balansering. Treet kan balanseres ved å bruke rotasjoner. |
| 2 | Sletting | Sletting kan også utføres på samme måte som det utføres i et binært søketre. Sletting kan også forstyrre balansen til treet, derfor brukes ulike typer rotasjoner for å balansere treet på nytt. |
Hvorfor AVL Tree?
AVL-treet kontrollerer høyden på det binære søketreet ved ikke å la det bli skjevt. Tiden det tar for alle operasjoner i et binært søketre med høyde h er Åh) . Den kan imidlertid utvides til På) hvis BST blir skjev (dvs. i verste fall). Ved å begrense denne høyden til log n, pålegger AVL-treet en øvre grense for hver operasjon som skal være O(log n) hvor n er antall noder.
AVL-rotasjoner
Vi utfører rotasjon i AVL-tre kun i tilfelle hvis Balansefaktor er annet enn -1, 0 og 1 . Det er i hovedsak fire typer rotasjoner som er som følger:
hvordan koble sammen beats-hodetelefoner
- L L rotasjon: Innsatt node er i venstre undertre av venstre undertre av A
- R R-rotasjon: Innsatt node er i høyre undertre av høyre undertre av A
- L R-rotasjon: Innsatt node er i høyre undertre av venstre undertre av A
- R L-rotasjon: Innsatt node er i venstre undertre av høyre undertre av A
Der node A er noden hvis balansefaktor er en annen enn -1, 0, 1.
De to første rotasjonene LL og RR er enkle rotasjoner og de to neste rotasjonene LR og RL er doble rotasjoner. For at et tre skal være ubalansert, må minimumshøyden være minst 2. La oss forstå hver rotasjon
1. RR Rotasjon
Når BST blir ubalansert, på grunn av at en node settes inn i høyre undertre til høyre undertre av A, så utfører vi RR-rotasjon, RR-rotasjon er en rotasjon mot klokken, som påføres på kanten under en node med balansefaktor -2
I eksemplet ovenfor har node A balansefaktor -2 fordi en node C er satt inn i høyre undertre av A høyre undertre. Vi utfører RR-rotasjonen på kanten under A.
2. LL Rotasjon
Når BST blir ubalansert, på grunn av at en node settes inn i venstre undertre i venstre undertre av C, utfører vi LL-rotasjon, LL-rotasjon er rotasjon med klokken, som påføres på kanten under en node med balansefaktor 2.
I eksemplet ovenfor har node C balansefaktor 2 fordi en node A er satt inn i venstre undertre av C venstre undertre. Vi utfører LL-rotasjonen på kanten under A.
3. LR Rotasjon
Doble rotasjoner er litt tøffere enn enkeltrotasjon som allerede har forklart ovenfor. LR-rotasjon = RR-rotasjon + LL-rotasjon, dvs. først RR-rotasjon utføres på undertre og deretter LL-rotasjon utføres på fullt tre, med fullt tre mener vi den første noden fra banen til innsatt node hvis balansefaktor er en annen enn -1 , 0 eller 1.
La oss forstå hvert eneste trinn veldig tydelig:
| Stat | Handling |
|---|---|
 | En node B er satt inn i det høyre undertreet til A, det venstre undertreet til C, på grunn av hvilket C har blitt en ubalansert node med balansefaktor 2. Dette tilfellet er L R-rotasjon der: Innsatt node er i høyre undertre av venstre undertre av C |
 | Ettersom LR-rotasjon = RR + LL-rotasjon, blir derfor RR (mot klokken) på undertre forankret ved A utført først. Ved å gjøre RR-rotasjon, node EN , har blitt venstre undertre av B . |
 | Etter å ha utført RR-rotasjon er node C fortsatt ubalansert, dvs. har balansefaktor 2, ettersom innsatt node A er til venstre til venstre for C |
 | Nå utfører vi LL rotasjon med klokken på fullt tre, dvs. på node C. node C har nå blitt høyre undertre av node B, A er venstre undertre av B |
 | Balansefaktoren for hver node er nå enten -1, 0 eller 1, det vil si at BST er balansert nå. |
4. RL Rotasjon
Som allerede diskutert, er at doble rotasjoner litt tøffere enn enkeltrotasjon som allerede har forklart ovenfor. RL-rotasjon = LL-rotasjon + RR-rotasjon, dvs. først utføres LL-rotasjon på undertre og deretter RR-rotasjon utføres på fullt tre, med fullt tre mener vi den første noden fra banen til den innsatte noden hvis balansefaktor er en annen enn -1 , 0 eller 1.
| Stat | Handling |
|---|---|
 | En node B har blitt satt inn i venstre undertre til C høyre undertre av EN , på grunn av hvilken A har blitt en ubalansert node med balansefaktor - 2. Dette tilfellet er RL-rotasjon der: Innsatt node er i venstre undertre av høyre undertre av A |
 | Ettersom RL-rotasjon = LL-rotasjon + RR-rotasjon, dermed LL (med klokken) på undertre med rot til C utføres først. Ved å gjøre RR-rotasjon, node C har blitt det rette undertreet av B . |
 | Etter å ha utført LL-rotasjon, node EN er fortsatt ubalansert, dvs. har balansefaktor -2, som er på grunn av høyre undertre til høyre undertre node A. |
 | Nå utfører vi RR-rotasjon (rotasjon mot klokken) på fullt tre, dvs. på node A. node C har nå blitt høyre undertre av node B, og node A har blitt venstre undertre av B. |
 | Balansefaktoren for hver node er nå enten -1, 0 eller 1, det vil si at BST er balansert nå. |
Spørsmål: Konstruer et AVL-tre med følgende elementer
H, I, J, B, A, E, C, F, D, G, K, L
1. Sett inn H, I, J
Ved å sette inn elementene ovenfor, spesielt når det gjelder H, blir BST ubalansert ettersom balansefaktoren til H er -2. Siden BST er høyreskjev, vil vi utføre RR-rotasjon på node H.
Det resulterende balansetreet er:
2. Sett inn B, A
Ved å sette inn elementene ovenfor, spesielt i tilfelle A, blir BST ubalansert ettersom balansefaktoren til H og I er 2, vurderer vi den første noden fra den sist innsatte noden, dvs. H. Siden BST fra H er venstreskjev, vi vil utføre LL-rotasjon på node H.
Det resulterende balansetreet er:
3. Insert E
Ved å sette inn E, blir BST ubalansert ettersom balansefaktoren til I er 2, siden hvis vi reiser fra E til I finner vi at den er satt inn i venstre undertre til høyre undertre av I, vi vil utføre LR-rotasjon på node I. LR = RR + LL rotasjon
3 a) Vi utfører først RR-rotasjon på node B
Det resulterende treet etter RR-rotasjon er:
3b) Vi utfører først LL-rotasjon på noden I
Det resulterende balanserte treet etter LL-rotasjon er:
btree og b tree
4. Sett inn C, F, D
Ved å sette inn C, F, D, blir BST ubalansert ettersom balansefaktoren til B og H er -2, siden hvis vi reiser fra D til B finner vi at den er satt inn i høyre undertre av venstre undertre av B, vil vi utføre RL Rotasjon på node I. RL = LL + RR rotasjon.
4a) Vi utfører først LL-rotasjon på node E
Det resulterende treet etter LL-rotasjon er:
4b) Vi utfører deretter RR-rotasjon på node B
Det resulterende balanserte treet etter RR-rotasjon er:
5. Sett inn G
Ved å sette inn G, blir BST ubalansert ettersom balansefaktoren til H er 2, siden hvis vi reiser fra G til H, finner vi at den er satt inn i venstre undertre til høyre undertre av H, vi vil utføre LR-rotasjon på node I. LR = RR + LL rotasjon.
5 a) Vi utfører først RR-rotasjon på node C
Det resulterende treet etter RR-rotasjon er:
5 b) Vi utfører deretter LL-rotasjon på node H
Det resulterende balanserte treet etter LL-rotasjon er:
6. Sett inn K
Ved å sette inn K blir BST ubalansert ettersom balansefaktoren til I er -2. Siden BST er høyreskjev fra I til K, vil vi derfor utføre RR-rotasjon på noden I.
Det resulterende balanserte treet etter RR-rotasjon er:
knn
7. Sett inn L
Ved innsetting er L-treet fortsatt balansert ettersom balansefaktoren for hver node nå er enten -1, 0, +1. Derfor er treet et balansert AVL-tre
