Vejledning til AVL-træer i Java

1. Introduktion

I denne vejledning introducerer vi AVL-træet, og vi ser på algoritmer til indsættelse, sletning og søgning efter værdier.

2. Hvad er AVL Tree?

AVL-træet, opkaldt efter opfinderne Adelson-Velsky og Landis, er et selvbalancerende binært søgetræ (BST).

Et selvbalancerende træ er et binært søgetræ, der afbalancerer højden efter indsættelse og sletning i henhold til nogle afbalanceringsregler.

Den værst tænkelige tidskompleksitet af en BST er en funktion af træets højde. Specifikt den længste sti fra træets rod til en knude. For en BST med N-noder, lad os sige, at hver node kun har nul eller et barn. Derfor er dens højde lig med N, og søgetiden er i værste fald O (N). Så vores hovedmål i en BST er at holde den maksimale højde tæt på log (N).

Balancefaktoren for knudepunkt N er højde (højre (N)) - højde (venstre (N)). I et AVL-træ kan balancefaktoren for en node kun være en af ​​1, 0 eller -1 værdier.

Lad os definere en Node objekt til vores træ:

offentlig klasse Node {int-nøgle; int højde; Node til venstre; Knude til højre; ...}

Lad os derefter definere AVLTree:

offentlig klasse AVLTree {private Node root; ugyldig opdateringHøjde (knude n) {n.højde = 1 + Math.max (højde (n. venstre), højde (n. højre)); } int højde (Node n) {return n == null? -1: n. Højde; } int getBalance (Node n) {return (n == null)? 0: højde (n. Højre) - højde (n. Venstre); } ...}

3. Hvordan balancerer man et AVL-træ?

AVL-træet kontrollerer balancefaktoren for dets noder efter indsættelse eller sletning af en node. Hvis balancefaktoren for en node er større end en eller mindre end -1, balancerer træet sig selv igen.

Der er to operationer til at balancere et træ igen:

  • højre rotation og
  • venstre rotation.

3.1. Højre rotation

Lad os starte med den rigtige rotation.

Antag, at vi har en BST kaldet T1, med Y som rodknude, X som venstre barn af Y og Z som højre barn af X. I betragtning af egenskaberne ved en BST ved vi, at X <Z <Y.

Efter en højre rotation af Y har vi et træ kaldet T2 med X som rod og Y som højre barn af X og Z som venstre barn af Y. T2 er stadig en BST, fordi den holder rækkefølgen X <Z <Y .

Lad os se på den rigtige rotationsoperation til vores AVLTree:

Node rotateRight (Node y) {Node x = y. venstre; Node z = x.right; x.right = y; y. venstre = z; updateHeight (y); updateHeight (x); returnere x; }

3.2. Venstre rotationsfunktion

Vi har også en venstre rotation operation.

Antag en BST kaldet T1 med Y som rodknude, X som højre barn af Y og Z som venstre barn af X. I betragtning af dette ved vi, at Y <Z <X.

Efter en venstre rotation af Y har vi et træ kaldet T2 med X som rod og Y som venstre barn af X og Z som højre barn af Y. T2 er stadig en BST, fordi den holder rækkefølgen Y <Z <X .

Lad os se på den venstre rotationsoperation for vores AVLTree:

Node rotateLeft (Node y) {Node x = y.right; Node z = x. Venstre; x. venstre = y; y.right = z; updateHeight (y); updateHeight (x); returnere x; }

3.3. Genbalanceringsteknikker

Vi kan bruge højre rotation og venstre rotation i mere komplekse kombinationer til hold AVL-træet afbalanceret efter enhver ændring i dets noder. I en ubalanceret struktur har mindst en node en balancefaktor lig med 2 eller -2. Lad os se, hvordan vi kan balancere træet i disse situationer.

Når balancefaktoren for node Z er 2, er undertræet med Z som roden i en af ​​disse to tilstande, idet man betragter Y som det rigtige barn af Z.

I det første tilfælde er højden i det højre barn på Y (X) større end højden på det venstre barn (T2). Vi kan genbalancere træet let ved en venstre rotation af Z.

I det andet tilfælde er højden på det højre barn af Y (T4) mindre end højden på det venstre barn (X). Denne situation har brug for en kombination af rotationsoperationer.

I dette tilfælde roterer vi først Y til højre, så træet kommer i samme form som det foregående tilfælde. Derefter kan vi balancere træet igen ved en venstre rotation af Z.

Når balancefaktoren for node Z er -2, er dens undertræ også i en af ​​disse to tilstande, så vi betragter Z som roden og Y som dens venstre barn.

Højden i det venstre barn af Y er større end dets højre barn, så vi afbalancerer træet med højre rotation af Z.

Eller i det andet tilfælde har Y's højre barn en større højde end sit venstre barn.

Så først og fremmest forvandler vi det til den tidligere form med en venstre rotation af Y, så afbalancerer vi træet med højre rotation af Z.

Lad os se på genopretningsoperationen for vores AVLTree:

Ombalance af node (Node z) {updateHeight (z); int balance = getBalance (z); hvis (balance> 1) {hvis (højde (z.right.right)> højde (z.right.left)) {z = rotereLinks (z); } andet {z.right = rotateRight (z.right); z = roter venstre (z); }} ellers hvis (balancehøjde (z.left.right)) z = rotateRight (z); ellers {z.left = rotateLeft (z.left); z = rotateRight (z); }} returner z; }

Vi bruger genbalancere efter indsættelse eller sletning af en node for alle noder i stien fra den ændrede node til roden.

4. Indsæt en node

Når vi skal indsætte en nøgle i træet, er vi nødt til at finde dens rette position til at passere BST-reglerne. Så vi starter fra roden og sammenligner dens værdi med den nye nøgle. Hvis nøglen er større, fortsætter vi til højre - ellers går vi til det venstre barn.

Når vi har fundet den rette overordnede node, tilføjer vi den nye nøgle som en node til venstre eller højre, afhængigt af værdien.

Efter indsættelse af noden har vi en BST, men det er muligvis ikke et AVL-træ. Derfor kontrollerer vi balancefaktorerne og genbalancerer BST for alle knudepunkter i stien fra den nye knude til roden.

Lad os se på indsatsoperationen:

Nodeindsats (knudepunkt, int-nøgle) {if (node ​​== null) {returner ny node (nøgle); } ellers hvis (node.key> key) {node.left = insert (node.left, key); } ellers hvis (node.key <key) {node.right = insert (node.right, key); } ellers {kast ny RuntimeException ("duplikatnøgle!"); } returner balance igen (node); }

Det er vigtigt at huske, at en nøgle er unik i træet - ingen to noder deler den samme nøgle.

Indsætningsalgoritmens tidskompleksitet er en funktion af højden. Da vores træ er afbalanceret, kan vi antage, at tidskompleksitet i værste fald er O (log (N)).

5. Slet en node

For at slette en nøgle fra træet skal vi først finde den i BST.

Når vi har fundet noden (kaldet Z), skal vi introducere den nye kandidat, der skal erstatte den i træet. Hvis Z er et blad, er kandidaten tom. Hvis Z kun har et barn, er dette barn kandidaten, men hvis Z har to børn, er processen lidt mere kompliceret.

Antag det højre barn af Z kaldet Y. Først finder vi yderkanten af ​​Y og kalder det X. Derefter indstiller vi den nye værdi af Z lig med X 's værdi og fortsætter med at slette X fra Y.

Endelig kalder vi rebalancemetoden i slutningen for at holde BST et AVL-træ.

Her er vores sletningsmetode:

Node-sletning (Node-node, int-nøgle) {if (node ​​== null) {return node; } ellers hvis (node.key> key) {node.left = delete (node.left, key); } ellers hvis (node.key <key) {node.right = delete (node.right, key); } andet {if (node.left == null || node.right == null) {node = (node.left == null)? node.right: node.left; } ellers {Node mostLeftChild = mostLeftChild (node.right); node.key = mostLeftChild.key; node.right = slet (node.right, node.key); }} hvis (node! = null) {node = rebalance (node); } returknude; }

Slet-algoritmens tidskompleksitet er en funktion af træets højde. I lighed med indsætningsmetoden kan vi antage, at tidskompleksitet i værste fald er O (log (N)).

6. Søg efter en node

Søgning efter en node i et AVL-træ er det samme som med enhver BST.

Start fra roden af ​​træet og sammenlign nøglen med værdien af ​​noden. Hvis nøglen er lig med værdien, skal du returnere noden. Hvis nøglen er større, skal du søge fra det højre barn, ellers fortsæt søgningen fra det venstre barn.

Søgningens tidskompleksitet er en funktion af højden. Vi kan antage, at tidskompleksitet i værste fald er O (log (N)).

Lad os se prøvekoden:

Knudesøgning (int-nøgle) {Node nuværende = rod; mens (nuværende! = null) {hvis (nuværende.tast == nøgle) {pause; } nuværende = aktuel.tast <nøgle? strøm. højre: strøm. venstre; } returstrøm; }

7. Konklusion

I denne vejledning har vi implementeret et AVL-træ med indsættelses-, sletnings- og søgefunktioner.

Som altid kan du finde koden på Github.


$config[zx-auto] not found$config[zx-overlay] not found