AVL Tree is uitgevonden door GM Adelson - Velsky en EM Landis in 1962. De boom wordt AVL genoemd ter ere van zijn uitvinders.
AVL Tree kan worden gedefinieerd als een in hoogte gebalanceerde binaire zoekboom waarin elk knooppunt wordt geassocieerd met een balansfactor die wordt berekend door de hoogte van zijn rechter subboom af te trekken van die van zijn linker subboom.
Er wordt gezegd dat de boom in balans is als de balansfactor van elk knooppunt tussen -1 en 1 ligt, anders is de boom uit balans en moet deze in balans zijn.
Balansfactor (k) = hoogte (links(k)) - hoogte (rechts(k))
Als de balansfactor van een knooppunt 1 is, betekent dit dat de linker subboom één niveau hoger is dan de rechter subboom.
Als de balansfactor van een knooppunt 0 is, betekent dit dat de linker subboom en de rechter subboom dezelfde hoogte hebben.
Als de balansfactor van een knooppunt -1 is, betekent dit dat de linker subboom één niveau lager is dan de rechter subboom.
In de volgende afbeelding wordt een AVL-boom weergegeven. We kunnen zien dat de balansfactor die aan elk knooppunt is gekoppeld, tussen -1 en +1 ligt. daarom is het een voorbeeld van een AVL-boom.
Complexiteit
| Algoritme | Gemiddeld geval | Het slechtste geval |
|---|---|---|
| Ruimte | op) | op) |
| Zoekopdracht | o(log n) | o(log n) |
| Invoegen | o(log n) | o(log n) |
| Verwijderen | o(log n) | o(log n) |
Bewerkingen op de AVL-boom
Vanwege het feit dat de AVL-boom ook een binaire zoekboom is, worden alle bewerkingen op dezelfde manier uitgevoerd als in een binaire zoekboom. Het zoeken en doorkruisen leidt niet tot inbreuk op het eigendomsrecht van de AVL-boom. Invoegen en verwijderen zijn echter handelingen die deze eigenschap kunnen schenden en moeten daarom opnieuw worden bekeken.
array-java
| SN | Operatie | Beschrijving |
|---|---|---|
| 1 | Plaatsing | Het invoegen in de AVL-boom wordt op dezelfde manier uitgevoerd als in een binaire zoekboom. Dit kan echter leiden tot een schending van de AVL-boomeigenschap en daarom moet de boom mogelijk worden uitgebalanceerd. De boom kan in evenwicht worden gebracht door rotaties toe te passen. |
| 2 | Verwijdering | Het verwijderen kan ook op dezelfde manier worden uitgevoerd als in een binaire zoekboom. Het verwijderen kan ook de balans van de boom verstoren. Daarom worden er verschillende soorten rotaties gebruikt om de boom opnieuw in evenwicht te brengen. |
Waarom AVL Boom?
De AVL-boom regelt de hoogte van de binaire zoekboom door deze niet scheef te laten staan. De tijd die nodig is voor alle bewerkingen in een binaire zoekboom met hoogte h is Oh) . Het kan echter worden uitgebreid tot Op) als de BST scheef wordt (d.w.z. in het slechtste geval). Door deze hoogte te beperken tot log n, legt de AVL-boom een bovengrens op aan elke bewerking O(logboek n) waarbij n het aantal knooppunten is.
AVL-rotaties
We voeren alleen rotatie in de AVL-boom uit als de balansfactor anders is dan -1, 0 en 1 . Er zijn in principe vier soorten rotaties:
- L L-rotatie: het ingevoegde knooppunt bevindt zich in de linker deelboom van de linker deelboom van A
- R R-rotatie: het ingevoegde knooppunt bevindt zich in de rechter deelboom van de rechter deelboom van A
- LR-rotatie: het ingevoegde knooppunt bevindt zich in de rechter deelboom van de linker deelboom van A
- R L-rotatie: het ingevoegde knooppunt bevindt zich in de linker deelboom van de rechter deelboom van A
Waar knooppunt A het knooppunt is waarvan de balansfactor anders is dan -1, 0, 1.
De eerste twee rotaties LL en RR zijn enkele rotaties en de volgende twee rotaties LR en RL zijn dubbele rotaties. Om een boom uit balans te brengen, moet de minimale hoogte minimaal 2 zijn. Laten we elke rotatie begrijpen
1. RR-rotatie
Wanneer BST uit balans raakt, doordat een knooppunt in de rechter deelboom van de rechter deelboom van A wordt ingevoegd, voeren we RR-rotatie uit, RR-rotatie is een rotatie tegen de klok in, die wordt toegepast op de rand onder een knooppunt met balansfactor -2
In het bovenstaande voorbeeld heeft knooppunt A een balansfactor -2 omdat een knooppunt C in de rechterdeelboom van de rechterdeelboom A is ingevoegd. We voeren de RR-rotatie uit op de rand onder A.
2. LL-rotatie
Wanneer BST uit balans raakt, doordat een knooppunt in de linker subboom van de linker subboom van C wordt ingevoegd, voeren we LL-rotatie uit, LL-rotatie is rotatie met de klok mee, die wordt toegepast op de rand onder een knooppunt met balansfactor 2.
algoritme voor rsa
In het bovenstaande voorbeeld heeft knooppunt C een balansfactor 2 omdat een knooppunt A in de linkerdeelboom van de linkerdeelboom C is ingevoegd. We voeren de LL-rotatie uit op de rand onder A.
3. LR-rotatie
Dubbele rotaties zijn iets moeilijker dan enkele rotatie, zoals hierboven al is uitgelegd. LR-rotatie = RR-rotatie + LL-rotatie, d.w.z. de eerste RR-rotatie wordt uitgevoerd op de subboom en vervolgens wordt LL-rotatie uitgevoerd op de volledige boom. Met volledige boom bedoelen we het eerste knooppunt uit het pad van het ingevoegde knooppunt waarvan de balansfactor anders is dan -1 , 0 of 1.
Laten we elke stap heel duidelijk begrijpen:
| Staat | Actie |
|---|---|
 | Een knooppunt B is ingevoegd in de rechter deelboom van A, de linker deelboom van C, waardoor C een ongebalanceerd knooppunt is geworden met een balansfactor 2. Dit geval is LR-rotatie waarbij: Het ingevoegde knooppunt zich in de rechter deelboom van de linker deelboom van C |
 | Omdat LR-rotatie = RR + LL-rotatie, wordt daarom eerst RR (tegen de klok in) op de subboom met wortels in A uitgevoerd. Door RR-rotatie uit te voeren, node A , is de linker subboom geworden van B . |
 | Na het uitvoeren van RR-rotatie is knooppunt C nog steeds uit balans, d.w.z. het heeft een balansfactor 2, aangezien het ingevoegde knooppunt A zich links of links van het knooppunt bevindt. C |
 | Nu voeren we LL rotatie met de klok mee uit op de volledige boom, d.w.z. op knooppunt C. knooppunt C is nu de rechter deelboom van knooppunt B geworden, A is de linker deelboom van B |
 | De balansfactor van elk knooppunt is nu -1, 0 of 1, dat wil zeggen dat de BST nu in evenwicht is. |
4. RL-rotatie
Zoals al besproken, zijn dubbele rotaties iets moeilijker dan enkele rotatie, wat hierboven al is uitgelegd. RL-rotatie = LL-rotatie + RR-rotatie, d.w.z. de eerste LL-rotatie wordt uitgevoerd op de subboom en vervolgens wordt RR-rotatie uitgevoerd op de volledige boom. Met volledige boom bedoelen we het eerste knooppunt uit het pad van het ingevoegde knooppunt waarvan de balansfactor anders is dan -1 , 0 of 1.
| Staat | Actie |
|---|---|
 | Een knooppunt B is ingevoegd in de linker subboom van C de rechter deelboom van A , waardoor A een ongebalanceerd knooppunt is geworden met een balansfactor - 2. Dit geval is RL-rotatie waarbij: Het ingevoegde knooppunt bevindt zich in de linker subboom van de rechter subboom van A |
 | Omdat RL-rotatie = LL-rotatie + RR-rotatie, dus LL (met de klok mee) op de subboom geworteld in C wordt als eerste uitgevoerd. Door RR-rotatie uit te voeren, node C is de juiste subboom geworden van B . |
 | Na het uitvoeren van LL-rotatie, node A is nog steeds onevenwichtig, dat wil zeggen met een balansfactor -2, wat komt door de rechterdeelboom van het rechterdeelboomknooppunt A. |
 | Nu voeren we RR-rotatie uit (rotatie tegen de klok in) op de volledige boom, d.w.z. op knooppunt A. knooppunt C is nu de rechter deelboom van knooppunt B geworden, en knooppunt A is de linker deelboom van B geworden. |
 | De balansfactor van elk knooppunt is nu -1, 0 of 1, dat wil zeggen dat de BST nu in evenwicht is. |
Vraag: Construeer een AVL-boom met de volgende elementen
H, I, J, B, A, E, C, F, D, G, K, L
1. Voeg H, I, J in
Python schrijft json naar bestand
Bij het invoegen van de bovenstaande elementen, vooral in het geval van H, raakt de BST uit balans omdat de balansfactor van H -2 is. Omdat de BST naar rechts scheef is, zullen we RR-rotatie uitvoeren op knooppunt H.
De resulterende balansboom is:
2. B, A invoegen
Bij het invoegen van de bovenstaande elementen, vooral in het geval van A, raakt de BST uit balans omdat de balansfactor van H en I 2 is. We beschouwen het eerste knooppunt van het laatst ingevoegde knooppunt, d.w.z. H. Omdat de BST van H naar links scheef is, we zullen LL-rotatie uitvoeren op knooppunt H.
De resulterende balansboom is:
3. E invoegen
Bij het invoegen van E raakt BST uit balans omdat de balansfactor van I 2 is, aangezien als we van E naar I reizen, we ontdekken dat deze in de linker deelboom van de rechter deelboom van I is ingevoegd, we LR-rotatie zullen uitvoeren op knooppunt I. LR = RR + LL rotatie
3 a) We voeren eerst RR-rotatie uit op knooppunt B
De resulterende boom na RR-rotatie is:
3b) We voeren eerst LL-rotatie uit op knooppunt I
De resulterende evenwichtige boom na LL-rotatie is:
4. C, F, D invoegen
Bij het invoegen van C, F, D raakt BST uit balans omdat de balansfactor van B en H -2 is, aangezien als we van D naar B reizen, we ontdekken dat deze in de rechter deelboom van de linker deelboom van B is ingevoegd, zullen we uitvoeren RL Rotatie op knooppunt I. RL = LL + RR rotatie.
zoekmachine en voorbeelden
4a) We voeren eerst LL-rotatie uit op knooppunt E
De resulterende boom na LL-rotatie is:
4b) Vervolgens voeren we RR-rotatie uit op knooppunt B
De resulterende evenwichtige boom na RR-rotatie is:
5. G invoegen
Bij het invoegen van G raakt BST uit balans omdat de balansfactor van H 2 is, aangezien als we van G naar H reizen, we ontdekken dat deze in de linker deelboom van de rechter deelboom van H is ingevoegd, we LR-rotatie op knooppunt I zullen uitvoeren. LR = RR + LL rotatie.
tekenreeks java vervangen
5 a) We voeren eerst RR-rotatie uit op knooppunt C
De resulterende boom na RR-rotatie is:
5 b) Vervolgens voeren we LL-rotatie uit op knooppunt H
De resulterende evenwichtige boom na LL-rotatie is:
6. K invoegen
Bij het invoegen van K raakt BST uit balans omdat de balansfactor van I -2 is. Omdat de BST rechtsscheef is van I naar K, zullen we daarom RR-rotatie uitvoeren op knooppunt I.
De resulterende evenwichtige boom na RR-rotatie is:
7. Plaats L
Bij het invoegen is de L-boom nog steeds in evenwicht, aangezien de balansfactor van elk knooppunt nu -1, 0, +1 is. Daarom is de boom een gebalanceerde AVL-boom
