Mielőtt megismernénk a bináris keresőfát és az AVL-fát, külön kell ismernünk a bináris keresőfát és az AVL-fát.
Mi az a bináris keresőfa?
A bináris keresőfa egy fa bináris fa. Mint tudjuk, ennek a fának 'n' számú gyermeke lehet, holott; a bináris fa legfeljebb két gyermeket tartalmazhat. Tehát a bináris fa kényszerét a bináris keresőfa is követi. A bináris keresési fa minden egyes csomópontjának a lehető legnagyobb két gyermeknek kell lennie; más szóval azt mondhatjuk, hogy a bináris keresőfa a bináris fa egy változata.
A bináris keresési fa is követi a bináris keresés tulajdonságait. A bináris keresés során a tömb összes elemének rendezett sorrendben kell lennie. A bináris keresésben azt a középső elemet számítjuk ki, amelyben a középső elem bal oldali része a középsőnél kisebb értéket, a középső elem jobb oldala pedig a középsőnél nagyobb értékeket tartalmazza.
A bináris keresőfában a középső elem a gyökércsomópont, a jobb oldali rész a jobb oldali részfa, a bal oldali rész pedig a bal oldali részfa. Ezért azt mondhatjuk, hogy a bináris keresőfa a kombinációja bináris fa és bináris keresés .
Megjegyzés: A bináris keresőfa olyan bináris faként definiálható, amelyben a bal oldali részfa összes eleme kisebb, mint a gyökércsomópont, és a jobb oldali részfa összes eleme nagyobb, mint a gyökércsomópont.
Idő összetettsége a bináris keresőfában
Ha a bináris keresési fa majdnem kiegyensúlyozott fa, akkor az összes művelet időbeli összetettsége: O(bejelentkezés) mert a keresés vagy balra, vagy jobbra oszlik.
java kapja az aktuális időt
Ha a bináris keresési fa balra vagy jobbra ferde, akkor az összes művelet időbeli összetettsége Tovább) mert az n elemig kell bejárnunk.
Mi az AVL-fa?
An AVL fa egy önkiegyensúlyozó bináris keresőfa, ahol a bal és jobb oldali részfa magassága közötti különbség nem lehet több egynél. Ezt a különbséget egyensúlyi tényezőnek nevezik. Az AVL fában az egyensúlytényező értéke -1, 0 vagy 1 lehet.
Hogyan történik a bináris keresőfa önkiegyensúlyozása?
Mint tudjuk, az AVL fa egy önkiegyensúlyozó bináris keresőfa. Ha a bináris keresési fa nem kiegyensúlyozott, néhány átrendezéssel önkiegyensúlyozható. Ezeket az átrendezéseket néhány elforgatással lehet elvégezni.
Értsük meg az önkiegyensúlyozást egy példán keresztül.
Tegyük fel, hogy be akarjuk szúrni 10, 20, 30 egy AVL fában.
Az alábbiakban bemutatjuk a 10, 20, 30 beszúrásának módjait egy AVL fába:
1. lépés: Először létrehozunk egy bináris keresési fát, az alábbiak szerint:
2. lépés: A fenti ábrán azt láthatjuk, hogy a fa kiegyensúlyozatlan, mert a 30-as csomópont egyensúlytényezője 2. Ahhoz, hogy AVL fát hozzunk létre, el kell végeznünk néhány forgatást. Ha a megfelelő elforgatást hajtjuk végre a 20-as csomóponton, akkor a 30-as csomópont lefelé, míg a 20-as csomópont felfelé mozdul el, az alábbiak szerint:
Amint azt megfigyelhetjük, a végső fa a Bináris keresőfa és a kiegyensúlyozott fa tulajdonságait követi; ezért ez egy AVL fa.
Az esetben a fa volt kiegyensúlyozatlan fa, így a megfelelő forgatást hajtjuk végre a csomóponton.
1. lépés: Először létrehozunk egy bináris keresési fát az alábbiak szerint:
tervezési minták java-ban
2. lépés: A fenti ábrán megfigyelhetjük, hogy a fa kiegyensúlyozatlan, mert a 10. csomópont egyensúlyi tényezője -2. Ahhoz, hogy AVL fát hozzunk létre, el kell végeznünk néhány forgatást. Ez egy jobb oldali kiegyensúlyozatlan fa, ezért balra forgatjuk. Ha a 20-as csomóponton balra forgatást végzünk, akkor a 20-as csomópont felfelé, a 10-es pedig lefelé fog mozogni, az alábbiak szerint:
Amint láthatjuk, a végső fa a tulajdonságát követi Bináris keresőfa és a kiegyensúlyozott fa ; ezért ez egy AVL fa.
1. lépés: Először létrehozzuk a bináris keresés fát az alábbiak szerint:
2. lépés: A fenti ábrán azt láthatjuk, hogy a fa kiegyensúlyozatlan, mert a gyökércsomópont egyensúlytényezője 2. Ahhoz, hogy AVL fává tegyük, el kell végeznünk néhány forgatást. A fenti forgatókönyv bal-jobb kiegyensúlyozatlan, mivel az egyik csomópont a szülőcsomóponttól balra, a másik pedig a szülőcsomópontjától jobbra található. Először a balra forgatást hajtjuk végre, és a forgatás a 10-es és 20-as csomópontok között történik. A balra forgatás után a 20-as felfelé, a 10-es pedig lefelé mozdul el az alábbi módon:
Ennek ellenére a fa kiegyensúlyozatlan, ezért a megfelelő forgatást hajtjuk végre a fán. Ha a megfelelő forgatást végrehajtották a fán, akkor a fa szeretné, ahogy az alábbiakban látható:
Amint a fenti fán megfigyelhetjük, a fa a Bináris Keresőfa és a kiegyensúlyozott fa tulajdonságát követi; ezért ez egy AVL fa.
ipar és gyár
1. lépés: Először létrehozzuk a bináris keresési fát, az alábbiak szerint:
2. lépés: A fenti ábrán azt láthatjuk, hogy a fa kiegyensúlyozatlan, mert a gyökércsomópont egyensúlytényezője 2. Ahhoz, hogy AVL fát hozzunk létre, el kell végeznünk néhány forgatást. A fenti forgatókönyv jobb-bal kiegyensúlyozatlan, mivel az egyik csomópont jobbra van a szülőcsomópontjától, egy másik pedig a szülőcsomóponttól balra. Először végrehajtjuk a megfelelő forgatást, amely a 30-as és 20-as csomópont között történik. A jobb elforgatás után a 20-as felfelé, a 30-as pedig lefelé mozdul el, az alábbiak szerint:
Ennek ellenére a fenti fa kiegyensúlyozatlan, ezért balra forgatást kell végrehajtanunk a csomóponton. A bal oldali elforgatás végrehajtása után a 20 csomópont felfelé, a 10 csomópont pedig lefelé mozog az alábbiak szerint:
Amint a fenti fán megfigyelhetjük, a fa a Bináris Keresőfa és a kiegyensúlyozott fa tulajdonságát követi; ezért ez egy AVL fa.
A bináris keresési fa és az AVL fa közötti különbségek
| Bináris keresőfa | AVL fa |
|---|---|
| Minden bináris keresőfa bináris fa, mert mindkét fa tartalmazza a legnagyobb két gyermeket. | Minden AVL-fa egyben bináris fa is, mert az AVL-fának is van két legnagyobb gyermeke. |
| A BST-ben nem létezik olyan kifejezés, mint például az egyensúlyi tényező. | Az AVL fában minden csomópont tartalmaz egy egyensúlytényezőt, és az egyensúlytényező értékének -1, 0 vagy 1 kell lennie. |
| Minden bináris keresési fa nem AVL fa, mert a BST lehet kiegyensúlyozott vagy kiegyensúlyozatlan fa. | Minden AVL fa bináris keresési fa, mert az AVL fa a BST tulajdonságát követi. |
| A bináris keresési fa minden csomópontja három mezőből áll, azaz a bal oldali részfából, a csomópont értékéből és a jobb oldali részfából. | Az AVL fa minden csomópontja négy mezőből áll, azaz a bal oldali részfából, a csomópont értékéből, a jobb oldali részfából és az egyensúlytényezőből. |
| Bináris keresési fa esetén, ha bármilyen csomópontot szeretnénk beszúrni a fába, akkor összehasonlítjuk a csomópont értékét a gyökérértékkel; Ha a csomópont értéke nagyobb, mint a gyökércsomópont értéke, akkor a csomópont a jobb oldali részfába kerül beillesztésre, ellenkező esetben a csomópont a bal részfába kerül be. A csomópont beillesztése után nincs szükség a magasságkiegyenlítési tényező ellenőrzésére a beillesztés befejezéséhez. | Az AVL fa esetében először meg kell találni a megfelelő helyet a csomópont beillesztéséhez. A csomópont beillesztése után kiszámítjuk az egyes csomópontok egyensúlyi tényezőjét. Ha az egyes csomópontok egyensúlytényezője teljesül, a beillesztés befejeződött. Ha az egyensúlytényező nagyobb, mint 1, akkor néhány forgatást kell végrehajtanunk a fa kiegyensúlyozásához. |
| A bináris keresés fában a fa magassága vagy mélysége O(n), ahol n a csomópontok száma a bináris keresés fában. | Az AVL fában a fa magassága vagy mélysége O(logn). |
| Megvalósítása egyszerű, mivel követnünk kell a bináris keresés tulajdonságait a csomópont beillesztéséhez. | Megvalósítása bonyolult, mert az AVL fában először meg kell alkotnunk az AVL fát, majd ellenőrizni kell a magasság egyensúlyát. Ha a magasság kiegyensúlyozatlan, akkor néhány forgatást kell végrehajtanunk, hogy kiegyensúlyozzuk a fát. |
| A BST nem egy kiegyensúlyozott fa, mert nem követi az egyensúlyi tényező fogalmát. | Az AVL fa magasságkiegyenlített fa, mert követi az egyensúlytényező fogalmát. |
| A keresés nem hatékony a BST-ben, ha nagy számú csomópont áll rendelkezésre a fában, mert a magasság nincs kiegyensúlyozott. | A keresés akkor is hatékony az AVL fában, ha sok csomópont van a fában, mert a magasság kiegyensúlyozott. |