streamalism.org

1. Inleiding

In deze tutorial introduceren we de AVL Tree en kijken we naar algoritmen voor het invoegen, verwijderen en zoeken naar waarden.

2. Wat is AVL Tree?

De AVL Tree, genoemd naar de uitvinders Adelson-Velsky en Landis, is een zelfbalancerende binaire zoekboom (BST).

Een zelfbalancerende boom is een binaire zoekboom die de hoogte na invoeging en verwijdering in evenwicht brengt volgens enkele evenwichtsregels.

De moeilijkste tijdcomplexiteit van een BST is een functie van de hoogte van de boom. Specifiek het langste pad van de wortel van de boom naar een knooppunt. Laten we voor een BST met N-knooppunten zeggen dat elk knooppunt slechts nul of één kind heeft. Daarom is de hoogte gelijk aan N en is de zoektijd in het ergste geval O (N). Dus ons belangrijkste doel in een BST is om de maximale hoogte dicht bij log (N) te houden.

De balansfactor van knooppunt N is hoogte (rechts (N)) - hoogte (links (N)). In een AVL-structuur kan de balansfactor van een knooppunt slechts een van de 1, 0 of -1 waarden zijn.

Laten we een Knooppunt object voor onze boom:

openbare klasse Node {int key; int hoogte; Knooppunt links; Knooppunt rechts; ...}

Laten we vervolgens de AVLTree:

openbare klasse AVLTree {privéknooppunt root; ongeldige updateHeight (Node n) {n.height = 1 + Math.max (hoogte (n.links), hoogte (n.rechts)); } int hoogte (Node n) {return n == null? -1: n. Hoogte; } int getBalance (Node n) {return (n == null)? 0: hoogte (n. Rechts) - hoogte (n. Links); } ...}

3. Hoe een AVL-boom in evenwicht te brengen?

De AVL Tree controleert de balansfactor van zijn knooppunten na het invoegen of verwijderen van een knooppunt. Als de balansfactor van een knoop groter is dan één of kleiner dan -1, wordt de structuur opnieuw in evenwicht gebracht.

Er zijn twee bewerkingen om een ​​boom in evenwicht te brengen:

• rechtsom draaien en
• linksom draaien.

3.1. Rechtsom draaien

Laten we beginnen met de juiste rotatie.

Stel dat we een BST hebben met de naam T1, met Y als het wortelknooppunt, X als het linkerkind van Y en Z als het rechterkind van X. Gezien de kenmerken van een BST weten we dat X <Z <Y.

Na een rotatie naar rechts van Y hebben we een boom genaamd T2 met X als de wortel en Y als het rechterkind van X en Z als het linkerkind van Y. T2 is nog steeds een BST omdat het de volgorde X <Z <Y behoudt .

Laten we eens kijken naar de juiste rotatiebewerking voor onze AVLTree:

Knooppunt rotateRight (Knooppunt y) {Knooppunt x = y.links; Knooppunt z = x.rechts; x.rechts = y; y.links = z; updateHeight (y); updateHeight (x); geef x terug; }

3.2. Bewerking naar links draaien

We hebben ook een rotatie naar links.

Veronderstel een BST genaamd T1, met Y als het wortelknooppunt, X als het rechterkind van Y en Z als het linkerkind van X. Gegeven dit weten we dat Y <Z <X.

Na een rotatie naar links van Y hebben we een boom genaamd T2 met X als de wortel en Y als het linkerkind van X en Z als het rechterkind van Y. T2 is nog steeds een BST omdat het de volgorde Y <Z <X behoudt .

Laten we eens kijken naar de linkse rotatiebewerking voor onze AVLTree:

Knooppunt rotateLeft (Knooppunt y) {Knooppunt x = y.right; Knooppunt z = x.links; x.links = y; y.recht = z; updateHeight (y); updateHeight (x); geef x terug; }

3.3. Herbalanceringstechnieken

We kunnen de bewerkingen naar rechts draaien en naar links draaien in meer complexe combinaties gebruiken houd de AVL-boom in evenwicht na elke wijziging in de knooppunten. In een ongebalanceerde structuur heeft ten minste één knooppunt een balansfactor gelijk aan 2 of -2. Laten we eens kijken hoe we de boom in deze situaties in evenwicht kunnen brengen.

Wanneer de balansfactor van knooppunt Z 2 is, bevindt de substructuur met Z als de wortel zich in een van deze twee toestanden, waarbij Y wordt beschouwd als het rechterkind van Z.

Voor het eerste geval is de lengte van het rechterkind van Y (X) groter dan de lengte van het linkerkind (T2). We kunnen de boom gemakkelijk in evenwicht brengen door Z naar links te draaien.

Voor het tweede geval is de lengte van het rechterkind van Y (T4) kleiner dan de lengte van het linkerkind (X). Deze situatie vereist een combinatie van rotatiebewerkingen.

In dit geval draaien we Y eerst naar rechts, zodat de boom dezelfde vorm krijgt als in het vorige geval. Dan kunnen we de boom weer in evenwicht brengen door Z naar links te draaien.

Als de balansfactor van knooppunt Z -2 is, bevindt de substructuur zich in een van deze twee toestanden, dus beschouwen we Z als de wortel en Y als het linkerkind.

De hoogte in het linkerkind van Y is groter dan die van zijn rechterkind, dus we balanceren de boom met de juiste rotatie van Z.

Of in het tweede geval heeft het rechterkind van Y een grotere lengte dan zijn linkerkind.

Dus eerst transformeren we het in de vorige vorm met een rotatie naar links van Y, en vervolgens balanceren we de boom met de rotatie naar rechts van Z.

Laten we eens kijken naar de rebalance-bewerking voor onze AVLTree:

Herbalancering van knooppunten (knooppunt z) {updateHeight (z); int balans = getBalance (z); if (balans> 1) {if (hoogte (z.rechts.rechts)> hoogte (z.rechts.links)) {z = rotateLeft (z); } anders {z.right = rotateRight (z.right); z = rotateLeft (z); }} else if (balans hoogte (z.left.right)) z = rotateRight (z); anders {z.left = rotateLeft (z.left); z = rotateRight (z); }} return z; }

We zullen gebruiken evenwicht na het invoegen of verwijderen van een knooppunt voor alle knooppunten in het pad van het gewijzigde knooppunt naar de root.

4. Voeg een knooppunt in

Als we een sleutel in de boomstructuur gaan invoegen, moeten we de juiste positie bepalen om aan de BST-regels te voldoen. We beginnen dus bij de wortel en vergelijken de waarde met de nieuwe sleutel. Als de sleutel groter is, gaan we verder naar rechts - anders gaan we naar het linkerkind.

Zodra we het juiste bovenliggende knooppunt hebben gevonden, voegen we de nieuwe sleutel toe als knooppunt links of rechts, afhankelijk van de waarde.

Nadat we het knooppunt hebben ingevoegd, hebben we een BST, maar het is mogelijk geen AVL-structuur. Daarom controleren we de balansfactoren en brengen we de BST opnieuw in evenwicht voor alle knooppunten in het pad van het nieuwe knooppunt naar de root.

Laten we de invoegbewerking eens bekijken:

Node insert (Node node, int key) {if (node ​​== null) {return new Node (key); } else if (node.key> key) {node.left = insert (node.left, key); } else if (node.key <key) {node.right = insert (node.right, key); } else {gooi nieuwe RuntimeException ("duplicate Key!"); } return rebalance (knooppunt); }

Het is belangrijk om te onthouden dat een sleutel uniek is in de boomstructuur - geen twee knooppunten delen dezelfde sleutel.

De tijdcomplexiteit van het invoegalgoritme is een functie van de hoogte. Omdat onze boom in evenwicht is, kunnen we aannemen dat de tijdcomplexiteit in het ergste geval O (log (N)) is.

5. Verwijder een knooppunt

Om een ​​sleutel uit de boom te verwijderen, moeten we deze eerst in de BST vinden.

Nadat we het knooppunt (genaamd Z) hebben gevonden, moeten we de nieuwe kandidaat introduceren als vervanging in de boom. Als Z een blad is, is de kandidaat leeg. Als Z maar één kind heeft, is dit kind de kandidaat, maar als Z twee kinderen heeft, is het proces iets gecompliceerder.

Veronderstel dat het rechterkind van Z Y heet. Eerst zoeken we het meest linkse knooppunt van de Y en noemen het X. Vervolgens stellen we de nieuwe waarde van Z gelijk aan de waarde van X en gaan we door met het verwijderen van X uit Y.

Ten slotte noemen we de rebalance-methode aan het einde om de BST een AVL-boom te houden.

Hier is onze verwijderingsmethode:

Node delete (Node node, int key) {if (node ​​== null) {return node; } else if (node.key> key) {node.left = delete (node.left, key); } else if (node.key <key) {node.right = delete (node.right, key); } else {if (node.left == null || node.right == null) {node = (node.left == null)? node.right: node.left; } else {Node mostLeftChild = mostLeftChild (node.right); node.key = mostLeftChild.key; node.right = delete (node.right, node.key); }} if (knooppunt! = null) {knooppunt = opnieuw in evenwicht brengen (knooppunt); } terugkeerknooppunt; }

De tijdcomplexiteit van het verwijderalgoritme is een functie van de hoogte van de boom. Net als bij de invoegmethode kunnen we aannemen dat de tijdcomplexiteit in het ergste geval O (log (N)) is.

6. Zoek naar een knooppunt

Zoeken naar een knooppunt in een AVL-structuur is de hetzelfde als bij elke BST.

Begin bij de wortel van de boom en vergelijk de sleutel met de waarde van het knooppunt. Als de sleutel gelijk is aan de waarde, retourneert u het knooppunt. Als de sleutel groter is, zoek dan vanaf het rechterkind, ga anders verder met zoeken vanaf het linkerkind.

De tijdcomplexiteit van het zoeken is een functie van de hoogte. We kunnen aannemen dat de tijdcomplexiteit in het ergste geval O (log (N)) is.

Laten we de voorbeeldcode eens bekijken:

Node find (int key) {Node current = root; while (current! = null) {if (current.key == key) {break; } current = current.key <key? current.right: current.left; } retourstroom; }

7. Conclusie

In deze tutorial hebben we een AVL Tree geïmplementeerd met invoegen, verwijderen en zoeken.

Zoals altijd kun je de code vinden op Github.