streamalism.org

1. Introduksjon

I denne opplæringen vil vi introdusere AVL-treet, og vi vil se på algoritmer for å sette inn, slette og søke etter verdier.

2. Hva er AVL Tree?

AVL-treet, oppkalt etter oppfinnerne Adelson-Velsky og Landis, er et selvbalanserende binært søketre (BST).

Et selvbalanserende tre er et binært søketre som balanserer høyden etter innsetting og sletting i henhold til noen balanseringsregler.

Den verste fallkompleksiteten til en BST er en funksjon av treets høyde. Nærmere bestemt den lengste stien fra roten til treet til en node. For en BST med N-noder, la oss si at hver node bare har null eller ett barn. Derfor er høyden lik N, og søketiden er i verste fall O (N). Så vårt hovedmål i en BST er å holde maksimal høyde nær loggen (N).

Balansefaktoren til node N er høyde (høyre (N)) - høyde (venstre (N)). I et AVL-tre kan balansefaktoren til en node bare være en av 1, 0 eller -1 verdier.

La oss definere en Node objekt for treet vårt:

offentlig klasse Node {int-nøkkel; int høyde; Node igjen; Node høyre; ...}

Deretter la oss definere AVLTree:

offentlig klasse AVLTree {private Node root; void updateHeight (Node n) {n.height = 1 + Math.max (height (n.left), height (n.right)); } int høyde (Node n) {return n == null? -1: n. Høyde; } int getBalance (Node n) {return (n == null)? 0: høyde (n. Høyre) - høyde (n. Venstre); } ...}

3. Hvordan balansere et AVL-tre?

AVL-treet sjekker balansefaktoren til nodene etter innsetting eller sletting av en node. Hvis balansefaktoren til en node er større enn en eller mindre enn -1, balanserer treet seg selv.

Det er to operasjoner for å balansere et tre på nytt:

• høyre rotasjon og
• venstre rotasjon.

3.1. Høyre rotasjon

La oss starte med riktig rotasjon.

Anta at vi har en BST kalt T1, med Y som rotnode, X som venstre barn av Y, og Z som høyre barn av X. Gitt egenskapene til en BST, vet vi at X <Z <Y.

Etter en høyre rotasjon av Y har vi et tre som heter T2 med X som rot og Y som høyre barn av X og Z som venstre barn av Y. T2 er fremdeles en BST fordi den holder rekkefølgen X <Z <Y .

La oss ta en titt på riktig rotasjonsoperasjon for vår 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 rotasjonsoperasjon

Vi har også en venstre rotasjonsoperasjon.

Anta en BST kalt T1, med Y som rotnode, X som høyre barn av Y, og Z som venstre barn av X. Gitt dette vet vi at Y <Z <X.

Etter en venstre rotasjon av Y har vi et tre som heter T2 med X som rot og Y som venstre barn av X og Z som høyre barn av Y. T2 er fremdeles en BST fordi den holder rekkefølgen Y <Z <X .

La oss ta en titt på venstre rotasjonsoperasjon for vår AVLTree:

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

3.3. Rebalanseringsteknikker

Vi kan bruke høyre rotasjon og venstre rotasjonsoperasjon i mer komplekse kombinasjoner til hold AVL-treet balansert etter endringer i nodene. I en ubalansert struktur har minst en node en balansefaktor lik 2 eller -2. La oss se hvordan vi kan balansere treet i disse situasjonene.

Når balansefaktoren til node Z er 2, er undertreet med Z som rot i en av disse to tilstandene, med tanke på Y som det rette barnet til Z.

For det første tilfellet er høyden i høyre barn av Y (X) større enn høyden til det venstre barnet (T2). Vi kan balansere treet enkelt ved å vri Z til venstre.

For det andre tilfellet er høyden på det høyre barnet til Y (T4) mindre enn høyden på det venstre barnet (X). Denne situasjonen trenger en kombinasjon av rotasjonsoperasjoner.

I dette tilfellet roterer vi først Y til høyre, slik at treet kommer i samme form som det forrige tilfellet. Da kan vi balansere treet igjen ved å vri Z til venstre.

Når balansefaktoren til node Z er -2, er dens undertre i en av disse to tilstandene, så vi anser Z som roten og Y som sitt venstre barn.

Høyden i venstre barn av Y er større enn høyre barn, så vi balanserer treet med høyre rotasjon av Z.

Eller i det andre tilfellet har det høyre barnet til Y større høyde enn det venstre barnet.

Så først og fremst transformerer vi den til den tidligere formen med en venstre rotasjon av Y, deretter balanserer vi treet med den høyre rotasjonen av Z.

La oss ta en titt på ombalanseringsoperasjonen for vår AVLTree:

Ombalanse av node (Node z) {updateHeight (z); int balanse = getBalance (z); hvis (balanse> 1) {hvis (høyde (z.høyre.høyre)> høyde (z.høyre. venstre)) {z = rotereLinks (z); } annet {z.right = rotateRight (z.right); z = roter venstre (z); }} ellers hvis (balansehøyde (z.left.right)) z = rotateRight (z); annet {z.left = rotateLeft (z.left); z = rotateRight (z); }} returner z; }

Vi bruker ombalanse etter å ha satt inn eller slettet en node for alle nodene i banen fra den endrede noden til roten.

4. Sett inn en node

Når vi skal sette inn en nøkkel i treet, må vi finne riktig posisjon for å overholde BST-reglene. Så vi starter fra roten og sammenligner verdien med den nye nøkkelen. Hvis nøkkelen er større, fortsetter vi til høyre - ellers går vi til venstre barn.

Når vi har funnet riktig foreldrenode, legger vi til den nye nøkkelen som en node til venstre eller høyre, avhengig av verdien.

Etter å ha satt inn noden har vi en BST, men det kan ikke være et AVL-tre. Derfor sjekker vi balansefaktorene og balanserer BST for alle nodene i banen fra den nye noden til roten.

La oss ta en titt på innsatsoperasjonen:

Nodeinnsetting (Node node, int-nøkkel) {if (node ​​== null) {return new Node (key); } annet hvis (node.key> key) {node.left = insert (node.left, key); } annet hvis (node.key <key) {node.right = insert (node.right, key); } annet {kast ny RuntimeException ("duplikatnøkkel!"); } returner ombalanse (node); }

Det er viktig å huske at en nøkkel er unik i treet - ingen to noder deler den samme nøkkelen.

Tidskompleksiteten til innsettingsalgoritmen er en funksjon av høyden. Siden treet vårt er balansert, kan vi anta at tidskompleksitet i verste fall er O (log (N)).

5. Slett en node

For å slette en nøkkel fra treet, må vi først finne den i BST.

Etter at vi har funnet noden (kalt Z), må vi introdusere den nye kandidaten som erstatning for den i treet. Hvis Z er et blad, er kandidaten tom. Hvis Z bare har ett barn, er dette barnet kandidaten, men hvis Z har to barn, er prosessen litt mer komplisert.

Anta det høyre barnet til Z som heter Y. Først finner vi Y-noden lengst til venstre og kaller det X. Deretter setter vi den nye verdien av Z lik X ’s verdi og fortsetter å slette X fra Y.

Til slutt kaller vi rebalansemetoden på slutten for å holde BST et AVL-tre.

Her er vår slettemetode:

Noder sletting (Node node, int key) {if (node ​​== null) {return node; } annet hvis (node.key> key) {node.left = delete (node.left, key); } annet hvis (node.key <key) {node.right = delete (node.right, key); } annet {if (node.left == null || node.right == null) {node = (node.left == null)? node.right: node.left; } annet {Node mostLeftChild = mostLeftChild (node.right); node.key = mostLeftChild.key; node.right = slett (node.right, node.key); }} if (node! = null) {node = rebalance (node); } retur node; }

Tidskompleksiteten til slettealgoritmen er en funksjon av høyden på treet. I likhet med innsettingsmetoden kan vi anta at tidskompleksitet i verste fall er O (log (N)).

6. Søk etter en node

Å søke etter en node i et AVL-tre er det samme som med hvilken som helst BST.

Start fra roten av treet og sammenlign nøkkelen med verdien på noden. Hvis nøkkelen er lik verdien, returnerer du noden. Hvis nøkkelen er større, søk fra høyre barn, ellers fortsett søket fra venstre barn.

Tidskompleksiteten til søket er en funksjon av høyden. Vi kan anta at tidskompleksitet i verste fall er O (log (N)).

La oss se eksempelkoden:

Node finne (int-nøkkel) {Node current = root; mens (gjeldende! = null) {if (gjeldende.tast == nøkkel) {pause; } gjeldende = gjeldende.tast <tast? gjeldende. høyre: gjeldende. venstre; } returstrøm; }

7. Konklusjon

I denne opplæringen har vi implementert et AVL-tre med innsettings-, slettings- og søkeoperasjoner.

Som alltid kan du finne koden på Github.