streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban bemutatjuk az AVL fát, és megvizsgáljuk az értékek beszúrásának, törlésének és keresésének algoritmusait.

2. Mi az AVL Tree?

Az AVL Tree, amelyet feltalálói, Adelson-Velsky és Landis után kaptak, egy önkiegyensúlyozó bináris keresési fa (BST).

Az önkiegyensúlyozó fa egy bináris keresőfa, amely egyes kiegyensúlyozási szabályok szerint kiegyenlíti a beillesztés és törlés utáni magasságot.

A BST legrosszabb esetben az idő bonyolultsága a fa magasságának függvénye. Pontosabban, a leghosszabb út a fa gyökerétől a csomópontig. N csomópontú BST esetén tegyük fel, hogy minden csomópontnak csak nulla vagy egy gyermeke van. Ezért a magassága megegyezik N-vel, és a keresési idő legrosszabb esetben O (N). Tehát fő célunk egy BST-ben az, hogy a maximális magasságot a rönk (N) közelében tartsuk.

Az N csomópont egyensúlyi tényezője magasság (jobb (N)) - magasság (bal (N)). Az AVL-fában egy csomópont egyensúlyi tényezője csak az 1, 0 vagy -1 érték egyike lehet.

Határozzuk meg a Csomópont tárgy a fánk számára:

public class Node {int kulcs; int magasság; Csomópont maradt; Csomópont jobbra; ...}

Ezután határozzuk meg a AVLTree:

public class AVLTree {private Node root; void updateHeight (n csomópont) {n.height = 1 + Math.max (magasság (n.bal), magasság (n.jobb)); } int magasság (n csomópont) {return n == null? -1: n.magasság; } int getBalance (n csomópont) {return (n == null)? 0: magasság (n.jobb) - magasság (n.bal); } ...}

3. Hogyan lehet egyensúlyba hozni az AVL fát?

Az AVL Tree egy csomópont beillesztése vagy törlése után ellenőrzi csomópontjainak egyensúlyi tényezőjét. Ha egy csomópont egyensúlyi tényezője nagyobb, mint egy vagy kevesebb, mint -1, akkor a fa újra egyensúlyba hozza önmagát.

A fa egyensúlyának helyreállítása két művelettel történik:

• jobb forgás és
• bal forgás.

3.1. Jobb elforgatás

Kezdjük a megfelelő forgatással.

Tegyük fel, hogy van egy T1 nevű BST, Y gyökércsomóként, X Y bal bal gyermekként és Z X jobb jobb gyermekeként. Tekintettel a BST jellemzőire, tudjuk, hogy X <Z <Y.

Az Y jobb elforgatása után van egy T2 nevű fa, amelynek X gyökere X, Y pedig X és Z jobb gyermeke, Y bal bal gyermeke. T2 továbbra is BST, mert X <Z <Y sorrendet tart .

Vessünk egy pillantást a megfelelő forgatási műveletre AVLTree:

Csomópont rotateRight (y csomópont y) {Csomópont x = y.balra; Csomópont z = x.jobb; x.jobb = y; y.bal = z; updateHeight (y); updateHeight (x); visszatér x; }

3.2. Balra forgatás

Van egy balra forgatási műveletünk is.

Tegyük fel a T1 nevű BST-t, ahol Y a gyökércsomópont, X az Y jobb gyermeke és Z az X bal gyermeke. Ezt figyelembe véve tudjuk, hogy Y <Z <X.

Az Y bal elforgatása után van egy T2 nevű fa, amelynek gyökere X, Y pedig X bal gyermeke, Z pedig Y jobb gyermeke. T2 továbbra is BST, mert megtartja az Y <Z <X sorrendet. .

Vessünk egy pillantást a bal oldali forgatási műveletre AVLTree:

Csomópont rotateBal (y csomópont) {Csomópont x = y.jobb; Csomópont z = x.bal; x.bal = y; y.jobb = z; updateHeight (y); updateHeight (x); visszatér x; }

3.3. Kiegyensúlyozó technikák

A jobb és bal forgatás műveleteket összetettebb kombinációkban használhatjuk a a csomópontokban bekövetkező bármilyen változás után tartsa egyensúlyban az AVL fát. Kiegyensúlyozatlan struktúrában legalább egy csomópont egyensúlyi tényezője 2 vagy -2. Lássuk, hogyan tudjuk egyensúlyba hozni a fát ezekben a helyzetekben.

Ha a Z csomópont egyensúlytényezője 2, akkor a Z mint gyökér részfája e két állapot egyikében van, Y-t Z-nek a megfelelő gyermekének tekintve.

Az első esetben Y (X) jobb gyermekében a magasság nagyobb, mint a bal gyermek magassága (T2). A fa balos forgatásával könnyen egyensúlyba hozhatjuk a fát.

A második esetben Y (T4) jobb gyermekének magassága kisebb, mint a bal gyermek magassága (X). Ehhez a helyzethez forgatási műveletek kombinációjára van szükség.

Ebben az esetben először Y-t forgatjuk jobbra, így a fa ugyanolyan alakú lesz, mint az előző eset. Ezután a bal oldali Z forgatással egyensúlyba hozhatjuk a fát.

Továbbá, ha a Z csomópont egyensúlytényezője -2, részfája e két állapot egyikében van, tehát Z-t gyöknek, Y-t pedig bal gyermekének tekintjük.

Y bal gyermekében a magasság nagyobb, mint a jobb gyermeké, ezért egyensúlyba hozzuk a fát a Z jobb elforgatásával.

Vagy a második esetben Y jobb gyermekének magasabb a magassága, mint a bal gyermekénél.

Tehát először Y alakzat balra forgatásával alakítjuk át az előbbi alakzattá, majd kiegyensúlyozzuk a fát a Z jobb elfordulásával.

Vessünk egy pillantást a kiegyensúlyozási műveletre AVLTree:

Csomópont kiegyensúlyozása (csomópont z) {updateHeight (z); int egyensúly = getBalance (z); if (egyensúly> 1) {if (magasság (z.jobb.jobb)> magasság (z.jobb.bal)) {z = rotateLeft (z); } else {z.right = rotateRight (z.right); z = forgatásBal (z); }} else if (mérlegmagasság (z.balra.jobbra)) z = rotateRight (z); else {z.balra = rotateLeft (z.balra); z = rotateRight (z); }} visszatér z; }

Majd használjuk egyensúly helyreállítása csomópont beszúrása vagy törlése után a megváltozott csomóponttól a gyökérig vezető út összes csomópontjához.

4. Helyezzen be egy csomópontot

Amikor be akarunk illeszteni egy kulcsot a fába, meg kell találnunk a megfelelő pozíciót a BST szabályok átadásához. Tehát a gyökérből indulunk ki, és összehasonlítjuk az értékét az új kulccsal. Ha a kulcs nagyobb, akkor haladunk jobbra - ellenkező esetben a bal gyermekhez megyünk.

Ha megtaláljuk a megfelelő szülőcsomópontot, akkor az értéktől függően csomópontként hozzáadjuk az új kulcsot balra vagy jobbra.

A csomópont behelyezése után van egy BST, de lehet, hogy nem AVL fa. Ezért ellenőrizzük az egyensúlyi tényezőket, és újraegyensúlyozzuk a BST-t az új csomóponttól a gyökérig vezető út minden csomópontjánál.

Vessünk egy pillantást a beszúrási műveletre:

Csomópont beszúrása (Csomópont csomópont, int kulcs) {if (csomópont == null) {return new Csomópont (kulcs); } else if (csomópont.kulcs> kulcs) {csomópont.balra = beillesztés (csomópont.balra, kulcs); } else if (csomópont.kulcs <kulcs) {csomópont.jobb = beillesztés (csomópont.jobb, kulcs); } else {dobjon új RuntimeException-t ("duplikált kulcs!"); } visszatérési egyensúly (csomópont); }

Fontos megjegyezni, hogy egy kulcs egyedi a fán - két csomópont nem osztja ugyanazt a kulcsot.

A beszúrási algoritmus időbeli összetettsége a magasság függvénye. Mivel a fánk kiegyensúlyozott, feltételezhetjük, hogy az idő komplexitása a legrosszabb esetben O (log (N)).

5. Töröljön egy csomópontot

Egy kulcs törléséhez a fáról először meg kell találnunk a BST-ben.

Miután megtaláltuk a csomópontot (az úgynevezett Z), be kell mutatnunk az új jelöltet, hogy helyettesítse a fában. Ha Z levél, akkor a jelölt üres. Ha Z-nek csak egy gyermeke van, akkor ez a gyermek a jelölt, de ha Z-nek két gyermeke van, a folyamat kissé bonyolultabb.

Tegyük fel, hogy Z jobb gyermeke Y. Először is megtaláljuk az Y bal szélső csomópontját, és X-nek hívjuk. Ezután beállítjuk az új Z értéket, amely megegyezik az X értékével, és folytatjuk az X törlését Y-ből.

Végül a rebalance módszert hívjuk a végén, hogy a BST-t AVL-fának tartsuk.

Itt van a törlési módszerünk:

Csomópont törlése (Csomópont csomópont, int kulcs) {if (csomópont == null) {visszatérési csomópont; } else if (csomópont.kulcs> kulcs) {csomópont.balra = törlés (csomópont.balra, kulcs); } else if (csomópont.kulcs <kulcs) {csomópont.jobb = törlés (csomópont.jobb, kulcs); } else {if (node.left == null || node.right == null) {node = (node.left == null)? csomópont.jobb: csomópont.balra; } else {Csomópont mostLeftChild = mostLeftChild (csomópont.jobb); node.key = mostLeftChild.key; node.right = törlés (node.right, node.key); }} if (csomópont! = null) {csomópont = egyensúly helyreállítása (csomópont); } visszatér csomópont; }

A törlés algoritmus időbeli összetettsége a fa magasságának függvénye. A beszúrási módszerhez hasonlóan feltételezhetjük, hogy az idő komplexitása legrosszabb esetben O (log (N)).

6. Keressen egy csomópontot

Csomópont keresése egy AVL fában a ugyanaz, mint bármelyik BST-nél.

Kezdje a fa gyökerétől, és hasonlítsa össze a kulcsot a csomópont értékével. Ha a kulcs megegyezik az értékkel, adja vissza a csomópontot. Ha a kulcs nagyobb, keressen a jobb gyermektől, különben folytassa a keresést a bal gyermektől.

A keresés időbeli összetettsége a magasság függvénye. Feltételezhetjük, hogy az idő komplexitása legrosszabb esetben O (log (N)).

Lássuk a mintakódot:

Csomópontkeresés (int kulcs) {Csomópont áram = gyökér; while (aktuális! = null) {if (current.key == kulcs) {break; } current = current.key <kulcs? current.right: current.balra; } visszatérő áram; }

7. Következtetés

Ebben az oktatóanyagban egy AVL Tree-t valósítottunk meg beszúrási, törlési és keresési műveletekkel.

Mint mindig, a kódot is megtalálhatja a Githubon.