Inleiding tot AVL-structuur in gegevensstructuur

AVL Tree in Data Structure verwijst naar Adelson, Velski & Landis Tree. Dit is een verbeterde versie van de binaire zoekboom. Het heeft alle functies vanaf de binaire zoekboom maar verschilt alleen omdat ze een verschil handhaven tussen de hoogte van de linker en de rechter subboom en zorgt er ook voor dat de waarde <= 1 in de boom is, dit wordt balans genoemd Factor.

Balance Factor = height(left-subtree) − height(right-subtree)

Voor bijvoorbeeld: Overweeg de volgende bomen

In het bovenstaande voorbeeld wordt gezegd dat de hoogte van de rechter subboom = 2 en links = 3, dus BF = 2, dat wil zeggen <= 1 dus de boom in evenwicht is.

Waarom hebben we een AVL-structuur in DS nodig?

Tijdens het werken met Binaire zoekboom komen we een scenario tegen waarin de elementen in gesorteerde volgorde staan. In dergelijke gevallen zijn alle elementen van de array aan één kant van de root gerangschikt, dit leidt tot een toename van de tijdcomplexiteit van het zoeken van een element in een array en de complexiteit wordt -O (n), dat wil zeggen de complexiteit van de boom in het slechtste geval . Om dergelijke problemen op te lossen en de zoektijd te verkorten, werden AVL-bomen uitgevonden door Adelson, Velski & Landis.

Voorbeeld:

In de bovenstaande figuur was de hoogte van de linker substructuur = 3 als

Hoogte van de rechtersubboom = 0

Aldus balansfactor = 3-0 = 3. Het zoeken naar een element in een dergelijke boom heeft dus een complexiteit die vergelijkbaar is met lineair zoeken. Om die complexe zoekactie te voorkomen, werd AVL-boom geïntroduceerd waar elk knooppunt in de boom moet worden onderhouden

balansfactor <= 1, anders moeten verschillende rotatietechnieken worden uitgevoerd om een ​​dergelijke boom in evenwicht te brengen.

Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);

Soorten rotaties

Als de balansfactor voor de boom niet voldoet aan de voorwaarde <= 1, moeten er rotaties worden uitgevoerd om er een gebalanceerde boom van te maken.

Er zijn 4 soorten rotaties:

1. Linksom draaien: als de toevoeging van een knoop rechts van de boom het evenwicht verstoort, moet in dat geval Linksom draaien worden uitgevoerd.

2. Rechtsom draaien: als de toevoeging van een knoop links van de boom de knoop onbalans maakt, moet rechtsom draaien worden uitgevoerd. Met andere woorden, wanneer het aantal knopen aan de linkerkant toeneemt, ontstaat er een behoefte om de elementen naar de rechterkant te verschuiven om het in evenwicht te brengen, dus er wordt gezegd dat het rechtsom draait.

3. Rotatie links-rechts: dit type rotatie is een combinatie van de hierboven beschreven 2 rotaties. Dit type rotatie treedt op wanneer een element wordt toegevoegd aan de rechtersubboom van een linkerboom.

Voer in een dergelijk geval eerst de linker rotatie uit op de substructuur gevolgd door een rechter rotatie van de linker boom.

4. Rotatie rechts-links: dit type rotatie bestaat ook uit een reeks van meer dan 2 rotaties. Dit type rotatie is nodig wanneer een element links van de rechter substructuur wordt toegevoegd en de boom uit balans raakt. In een dergelijk geval voeren we eerst de rechter rotatie uit op de rechter substructuur en vervolgens de linker rotatie op de rechter boom.

Bewerkingen op AVL-structuur in DS

Hieronder 3 bewerkingen die kunnen worden uitgevoerd op de AVL-structuur: -

1. Zoeken

Deze bewerking is vergelijkbaar met het uitvoeren van een zoekopdracht in de binaire zoekstructuur. De gevolgde stappen zijn als volgt:

  • Lees het element van de gebruiker, zeg x.
  • Vergelijk het element vanaf de root, als het hetzelfde is, verlaat het anders ga naar de volgende stap.
  • Als x

Anders ga naar het juiste kind en vergelijk opnieuw.

Volg de processen B en C totdat u het element vindt en verlaat.

Dit proces heeft O (log n) complexiteit.

Voorbeeld:

Beschouw deze boom, waar we moeten zoeken naar knooppuntwaarde 9.
Laat eerst x = 9, root-waarde (12)> x, dan moet de waarde in de linker substructuur van het root-element staan.
Nu wordt x vergeleken met knooppuntwaarde 3
x> 3 dus moeten we doorgaan naar de juiste substructuur.
Nu wordt x vergeleken met knooppunt (9), waarbij 9 == 9 true retourneert. Het zoeken naar elementen is dus voltooid in de boom.

2. Invoeging

Bij het invoegen van een element in de AVL-structuur moeten we het locatie-specifieke element vinden dat moet worden ingevoegd en vervolgens wordt het element op dezelfde manier bevestigd als een invoeging in BST, maar daarna wordt gecontroleerd of de boom nog steeds in balans is of niet dat wil zeggen de balansfactor van een knoop is <= 1. En bepaalde rotaties worden uitgevoerd zoals vereist.

Complexiteit is O (log n).
Voorbeeld: overweeg de onderstaande boom,

Elke knoop heeft een balansfactor als 0, -1 of 1, dus de boom is in balans. Laten we nu eens kijken wat er gebeurt als een knooppunt met waarde 1 wordt ingevoegd.
De eerste boom wordt verplaatst om de locatie te vinden waar deze moet worden ingevoegd …
1 <2 wordt dus geschreven als een linkerkind van de knoop (2).
Na het inbrengen wordt het knooppunt (9) onbalans met een balansfactor = 2. Nu wordt het onderworpen aan rechtsrotatie.
Een boom wordt balans na Rechts rotatie en dus wordt de invoegbewerking met succes voltooid.

3. Verwijderen

Het verwijderen van een element in de AVL-structuur omvat ook het zoeken naar een element in de structuur en het vervolgens verwijderen. De zoekbewerking is hetzelfde als BST en na het vinden van het element dat moet worden verwijderd, wordt het element uit de structuur verwijderd en worden de elementen aangepast om het opnieuw BST te maken. Nadat deze elementen zijn gecontroleerd om een ​​balansfactor van 0, -1 of 1 te hebben, worden geschikte rotaties uitgevoerd om deze in balans te brengen.

Complexiteit als O (log n).

Beschouw de gegeven boom, die allemaal een balansfactor van 0, -1 of 1 hebben.
Laten we nu een knooppunt met waarde 16 verwijderen.
De eerste boom wordt verplaatst om het knooppunt te vinden met waarde 16 hetzelfde als een zoekalgoritme.
Knooppunt 16 zal worden vervangen door de inordervoorganger van deze knoop die het grootste element is van de linker subtree, namelijk 12
De boom is uit balans geraakt, dus LL - rotatie moet worden uitgevoerd.
Nu is elk knooppunt in balans.

Conclusie - AVL-structuur in gegevensstructuur

AVL-structuur is een afstammeling van de binaire zoekboom, maar overwint het nadeel van toenemende complexiteit voor het geval de elementen worden gesorteerd. Het bewaakt de balansfactor van de boom als 0 of 1 of -1. In het geval dat de boom uit balans raakt, worden overeenkomstige rotatietechnieken uitgevoerd om de boom in evenwicht te brengen.

Aanbevolen artikelen

Dit is een handleiding voor AVL Tree in Data Structure. Hier bespreken we de introductie, bewerkingen op AVL-structuur in DS en soorten rotaties. U kunt ook onze andere gerelateerde artikelen lezen voor meer informatie–

  1. jQuery-elementen
  2. Wat is Data Science
  3. Soorten bomen in gegevensstructuur
  4. C # gegevenstypen

Categorie:

Big Data