Predtým, ako sa dozvieme o rozdieloch medzi binárnym vyhľadávacím stromom a AVL stromom, mali by sme vedieť o binárnom vyhľadávacom strome a AVL strome oddelene.
Čo je binárny vyhľadávací strom?
The binárny vyhľadávací strom je a strom binárny strom. Ako vieme, ten strom môže mať „n“ počet detí, zatiaľ čo; binárny strom môže obsahovať maximálne dve deti. Takže za obmedzením binárneho stromu nasleduje aj binárny vyhľadávací strom. Každý uzol v binárnom vyhľadávacom strome by mal mať maximálne dve deti; inými slovami, môžeme povedať, že binárny vyhľadávací strom je variantom binárneho stromu.
Binárny vyhľadávací strom tiež sleduje vlastnosti binárneho vyhľadávania. Pri binárnom vyhľadávaní musia byť všetky prvky v poli zoradené. Stredný prvok vypočítame pri binárnom vyhľadávaní, v ktorom ľavá časť stredného prvku obsahuje hodnotu menšiu ako stredná hodnota a pravá časť stredného prvku obsahuje hodnoty väčšie ako stredná hodnota.
V strome binárneho vyhľadávania sa stredný prvok stáva koreňovým uzlom, pravá časť sa stáva pravým podstromom a ľavá časť sa stáva ľavým podstromom. Preto môžeme povedať, že binárny vyhľadávací strom je kombináciou a binárny strom a binárne vyhľadávanie .
Poznámka: Binárny vyhľadávací strom možno definovať ako binárny strom, v ktorom sú všetky prvky ľavého podstromu menšie ako koreňový uzol a všetky prvky pravého podstromu sú väčšie ako koreňový uzol.
Časová zložitosť v binárnom vyhľadávacom strome
Ak je binárny vyhľadávací strom takmer vyvážený, všetky operácie budú časovo náročné O(logn) pretože vyhľadávanie je rozdelené buď na ľavý alebo pravý podstrom.
pole slicing java
Ak je binárny vyhľadávací strom skosený doľava alebo doprava, všetky operácie budú časovo zložité O(n) pretože musíme prejsť až k n prvkom.
Čo je strom AVL?
An AVL strom je samovyvažujúci binárny vyhľadávací strom, kde rozdiel medzi výškami ľavého a pravého podstromu nemôže byť väčší ako jedna. Tento rozdiel je známy ako faktor rovnováhy. V strome AVL môžu byť hodnoty balančného faktora buď -1, 0 alebo 1.
Ako prebieha samovyvažovanie binárneho vyhľadávacieho stromu?
Ako vieme, AVL strom je samovyvažujúci binárny vyhľadávací strom. Ak binárny vyhľadávací strom nie je vyvážený, môže sa pomocou niektorých preusporiadaní samovyvážiť. Tieto preusporiadania je možné vykonať pomocou niektorých rotácií.
Pochopme sebavyvažovanie prostredníctvom príkladu.
Predpokladajme, že chceme vložiť 10, 20, 30 v strome AVL.
pripojenie java mysql
Nasledujú spôsoby vloženia 10, 20, 30 do stromu AVL:
Krok 1: Najprv vytvoríme binárny vyhľadávací strom, ako je uvedené nižšie:
Krok 2: Na obrázku vyššie môžeme pozorovať, že strom je nevyvážený, pretože faktor rovnováhy uzla 30 je 2. Aby sme z neho urobili AVL strom, musíme vykonať niekoľko rotácií. Ak vykonáme pravú rotáciu na uzle 20, potom sa uzol 30 bude pohybovať nadol, zatiaľ čo uzol 20 sa bude pohybovať nahor, ako je znázornené nižšie:
Ako môžeme pozorovať, konečný strom sleduje vlastnosť stromu binárneho vyhľadávania a vyváženého stromu; teda je to AVL strom.
V prípade bol strom vľavo nevyvážený strom, tak vykonáme správnu rotáciu na uzle.
Krok 1: Najprv vytvoríme binárny vyhľadávací strom, ako je uvedené nižšie:
Krok 2: Na obrázku vyššie môžeme pozorovať, že strom je nevyvážený, pretože faktor rovnováhy uzla 10 je -2. Aby sme z neho urobili AVL strom, musíme vykonať nejaké rotácie. Je to pravý nevyvážený strom, preto vykonáme rotáciu doľava. Ak vykonáme rotáciu doľava na uzle 20, potom sa uzol 20 posunie nahor a uzol 10 sa bude pohybovať nadol, ako je znázornené nižšie:
Ako môžeme pozorovať, konečný strom sleduje vlastnosť Binárny vyhľadávací strom a a vyvážený strom ; teda je to AVL strom.
Krok 1: Najprv vytvoríme strom binárneho vyhľadávania, ako je uvedené nižšie:
Krok 2: Na obrázku vyššie môžeme pozorovať, že strom je nevyvážený, pretože faktor rovnováhy koreňového uzla je 2. Aby sme z neho urobili AVL strom, musíme vykonať nejaké rotácie. Vyššie uvedený scenár je ľavo-pravý nevyvážený, pretože jeden uzol je naľavo od svojho nadradeného uzla a ďalší je napravo od svojho nadradeného uzla. Najprv vykonáme rotáciu doľava a rotácia sa uskutoční medzi uzlami 10 a 20. Po rotácii doľava sa 20 posunie nahor a 10 nadol, ako je znázornené nižšie:
Napriek tomu je strom nevyvážený, preto na strome vykonávame správnu rotáciu. Po vykonaní správnej rotácie na strome by strom chcel, ako je uvedené nižšie:
Ako môžeme pozorovať vo vyššie uvedenom strome, strom sleduje vlastnosť stromu binárneho vyhľadávania a vyváženého stromu; teda je to AVL strom.
Krok 1: Najprv vytvoríme strom binárneho vyhľadávania, ako je uvedené nižšie:
Krok 2: Na obrázku vyššie môžeme pozorovať, že strom je nevyvážený, pretože faktor rovnováhy koreňového uzla je 2. Aby sme z neho urobili AVL strom, musíme vykonať niekoľko rotácií. Vyššie uvedený scenár je pravo-ľavý nevyvážený, pretože jeden uzol je napravo od svojho nadradeného uzla a ďalší uzol je naľavo od svojho nadradeného uzla. Najprv vykonáme pravú rotáciu, ktorá sa stane medzi uzlami 30 a 20. Po pravej rotácii sa 20 posunie nahor a 30 sa bude pohybovať nadol, ako je znázornené nižšie:
Napriek tomu je vyššie uvedený strom nevyvážený, takže musíme vykonať rotáciu doľava na uzle. Po vykonaní ľavého otáčania sa uzol 20 posunie nahor a uzol 10 sa bude pohybovať nadol, ako je znázornené nižšie:
slf4j vs log4j
Ako môžeme pozorovať vo vyššie uvedenom strome, strom sleduje vlastnosť stromu binárneho vyhľadávania a vyváženého stromu; teda je to AVL strom.
Rozdiely medzi stromom binárneho vyhľadávania a stromom AVL
| Binárny vyhľadávací strom | AVL strom |
|---|---|
| Každý binárny vyhľadávací strom je binárny strom, pretože oba stromy obsahujú maximálne dve deti. | Každý strom AVL je tiež binárny strom, pretože strom AVL má tiež maximálne dve deti. |
| V BST neexistuje žiadny termín, ako napríklad faktor rovnováhy. | V strome AVL obsahuje každý uzol faktor rovnováhy a hodnota faktora rovnováhy musí byť buď -1, 0 alebo 1. |
| Každý strom binárneho vyhľadávania nie je strom AVL, pretože BST môže byť buď vyvážený alebo nevyvážený strom. | Každý strom AVL je binárny vyhľadávací strom, pretože strom AVL sleduje vlastnosť BST. |
| Každý uzol v strome binárneho vyhľadávania pozostáva z troch polí, t. j. ľavého podstromu, hodnoty uzla a pravého podstromu. | Každý uzol v strome AVL pozostáva zo štyroch polí, t. j. ľavý podstrom, hodnota uzla, pravý podstrom a faktor rovnováhy. |
| V prípade stromu binárneho vyhľadávania, ak chceme vložiť akýkoľvek uzol do stromu, porovnáme hodnotu uzla s hodnotou koreňa; ak je hodnota uzla väčšia ako hodnota koreňového uzla, uzol sa vloží do pravého podstromu, inak sa uzol vloží do ľavého podstromu. Po vložení uzla nie je potrebné kontrolovať faktor vyváženia výšky, aby bolo vloženie dokončené. | V prípade AVL stromu najskôr nájdeme vhodné miesto na vloženie uzla. Po vložení uzla vypočítame koeficient rovnováhy každého uzla. Ak je vyvážený faktor každého uzla splnený, vkladanie je dokončené. Ak je koeficient rovnováhy väčší ako 1, potom musíme vykonať niekoľko rotácií, aby sme strom vyvážili. |
| V strome binárneho vyhľadávania je výška alebo hĺbka stromu O(n), kde n je počet uzlov v strome binárneho vyhľadávania. | V strome AVL je výška alebo hĺbka stromu O(logn). |
| Implementácia je jednoduchá, pretože na vloženie uzla musíme postupovať podľa vlastností binárneho vyhľadávania. | Implementácia je zložitá, pretože v strome AVL musíme najprv vytvoriť strom AVL a potom musíme skontrolovať vyváženie výšky. Ak je výška nevyvážená, potom musíme vykonať niekoľko rotácií, aby sme strom vyvážili. |
| BST nie je vyvážený strom, pretože sa neriadi konceptom faktora rovnováhy. | AVL strom je výškovo vyvážený strom, pretože sa riadi konceptom faktora rovnováhy. |
| Vyhľadávanie je v BST neefektívne, keď je v strome k dispozícii veľký počet uzlov, pretože výška nie je vyvážená. | Vyhľadávanie je v AVL strome efektívne, aj keď je v strome veľký počet uzlov, pretože výška je vyvážená. |