Než budeme vědět o rozdílech mezi binárním vyhledávacím stromem a AVL stromem, měli bychom vědět o binárním vyhledávacím stromu a AVL stromu samostatně.
Co je binární vyhledávací strom?
The binární vyhledávací strom je strom binární strom. Jak víme, ten strom může mít 'n' počet dětí, zatímco; binární strom může obsahovat maximálně dva potomky. Takže za omezením binárního stromu následuje také binární vyhledávací strom. Každý uzel v binárním vyhledávacím stromu by měl mít maximálně dva potomky; jinými slovy, můžeme říci, že binární vyhledávací strom je variantou binárního stromu.
Binární vyhledávací strom také sleduje vlastnosti binárního vyhledávání. Při binárním vyhledávání musí být všechny prvky v poli seřazené. Střední prvek počítáme při binárním vyhledávání, ve kterém levá část prostředního prvku obsahuje hodnotu menší než střední hodnota a pravá část prostředního prvku obsahuje hodnoty větší než střední hodnota.
V binárním vyhledávacím stromu se prostřední prvek stává kořenovým uzlem, pravá část se stává pravým podstromem a levá část se stává levým podstromem. Můžeme tedy říci, že binární vyhledávací strom je kombinací a binární strom a binární vyhledávání .
Poznámka: Binární vyhledávací strom lze definovat jako binární strom, ve kterém jsou všechny prvky levého podstromu menší než kořenový uzel a všechny prvky pravého podstromu jsou větší než kořenový uzel.
Časová složitost v binárním vyhledávacím stromu
Pokud je binární vyhledávací strom téměř vyváženým stromem, pak budou mít všechny operace časovou složitost O(logn) protože hledání je rozděleno buď na levý nebo pravý podstrom.
java platné identifikátory
Pokud je binární vyhledávací strom zkosený doleva nebo doprava, pak budou všechny operace časově složité Na) protože potřebujeme přejít až k n prvkům.
Co je strom AVL?
An strom AVL je samovyrovnávací binární vyhledávací strom, kde rozdíl mezi výškami levého a pravého podstromu nemůže být větší než jedna. Tento rozdíl je známý jako faktor rovnováhy. Ve stromu AVL mohou být hodnoty balančního faktoru buď -1, 0 nebo 1.
Jak probíhá samovyvažování binárního vyhledávacího stromu?
Jak víme, AVL strom je samovyvažující binární vyhledávací strom. Pokud není binární vyhledávací strom vyvážený, lze jej pomocí některých přeuspořádání vyrovnat. Tato přeuspořádání lze provést pomocí některých rotací.
Pojďme pochopit samovyvažování prostřednictvím příkladu.
Předpokládejme, že chceme vložit 10, 20, 30 ve stromu AVL.
Níže jsou uvedeny způsoby vložení 10, 20, 30 do stromu AVL:
Krok 1: Nejprve vytvoříme binární vyhledávací strom, jak je znázorněno níže:
java znak na řetězec
Krok 2: Na výše uvedeném obrázku můžeme pozorovat, že strom je nevyvážený, protože faktor rovnováhy uzlu 30 je 2. Abychom z něj udělali AVL strom, musíme provést nějaké rotace. Pokud provedeme pravou rotaci na uzlu 20, pak se uzel 30 bude pohybovat dolů, zatímco uzel 20 se bude pohybovat nahoru, jak je znázorněno níže:
Jak můžeme pozorovat, konečný strom sleduje vlastnost stromu binárního vyhledávání a vyváženého stromu; jedná se tedy o strom AVL.
V případě byl strom nechal nevyvážený strom, tak na uzlu provedeme pravou rotaci.
Krok 1: Nejprve vytvoříme binární vyhledávací strom, jak je znázorněno níže:
Krok 2: Na výše uvedeném obrázku můžeme pozorovat, že strom je nevyvážený, protože faktor rovnováhy uzlu 10 je -2. Abychom z něj udělali AVL strom, musíme provést nějaké rotace. Je to pravý nevyvážený strom, proto provedeme rotaci vlevo. Pokud provedeme rotaci doleva na uzlu 20, pak se uzel 20 posune nahoru a uzel 10 se bude pohybovat dolů, jak je znázorněno níže:
Jak můžeme pozorovat, konečný strom sleduje vlastnost the Binární vyhledávací strom a a vyrovnaný strom ; jedná se tedy o strom AVL.
ve kterém roce byl vynalezen počítač
Krok 1: Nejprve vytvoříme strom binárního vyhledávání, jak je znázorněno níže:
Krok 2: Na obrázku výše můžeme pozorovat, že strom je nevyvážený, protože faktor rovnováhy kořenového uzlu je 2. Abychom z něj udělali AVL strom, musíme provést nějaké rotace. Výše uvedený scénář je nevyvážený zleva doprava, protože jeden uzel je nalevo od nadřazeného uzlu a další napravo od nadřazeného uzlu. Nejprve provedeme rotaci doleva a rotace nastane mezi uzly 10 a 20. Po rotaci doleva se 20 posune nahoru a 10 se bude pohybovat dolů, jak je znázorněno níže:
Přesto je strom nevyvážený, takže na stromě provádíme správnou rotaci. Jakmile je na stromě provedena správná rotace, strom by chtěl, jak je znázorněno níže:
Jak můžeme pozorovat ve výše uvedeném stromu, strom sleduje vlastnosti stromu binárního vyhledávání a vyváženého stromu; jedná se tedy o strom AVL.
Krok 1: Nejprve vytvoříme strom binárního vyhledávání, jak je znázorněno níže:
Krok 2: Na obrázku výše můžeme pozorovat, že strom je nevyvážený, protože faktor rovnováhy kořenového uzlu je 2. Abychom z něj udělali AVL strom, musíme provést nějaké rotace. Výše uvedený scénář je nevyvážený zprava doleva, protože jeden uzel je napravo od nadřazeného uzlu a další uzel je nalevo od nadřazeného uzlu. Nejprve provedeme pravou rotaci, která se stane mezi uzly 30 a 20. Po pravé rotaci se 20 posune nahoru a 30 se bude pohybovat dolů, jak je znázorněno níže:
Přesto je výše uvedený strom nevyvážený, takže musíme na uzlu provést rotaci doleva. Po provedení rotace doleva se uzel 20 posune nahoru a uzel 10 se bude pohybovat dolů, jak je znázorněno níže:
Jak můžeme pozorovat ve výše uvedeném stromu, strom sleduje vlastnosti stromu binárního vyhledávání a vyváženého stromu; jedná se tedy o strom AVL.
Rozdíly mezi stromem binárního vyhledávání a stromem AVL
| Binární vyhledávací strom | strom AVL |
|---|---|
| Každý binární vyhledávací strom je binárním stromem, protože oba stromy obsahují maximálně dva potomky. | Každý strom AVL je také binárním stromem, protože strom AVL má také maximálně dva potomky. |
| V BST neexistuje žádný termín, jako je faktor rovnováhy. | Ve stromu AVL obsahuje každý uzel faktor rovnováhy a hodnota faktoru rovnováhy musí být buď -1, 0 nebo 1. |
| Každý strom binárního vyhledávání není strom AVL, protože BST může být buď vyvážený, nebo nevyvážený strom. | Každý strom AVL je binární vyhledávací strom, protože strom AVL sleduje vlastnost BST. |
| Každý uzel ve stromu binárního vyhledávání se skládá ze tří polí, tj. levého podstromu, hodnoty uzlu a pravého podstromu. | Každý uzel ve stromu AVL se skládá ze čtyř polí, tj. levého podstromu, hodnoty uzlu, pravého podstromu a faktoru rovnováhy. |
| V případě stromu Binary Search, pokud chceme vložit jakýkoli uzel do stromu, porovnáme hodnotu uzlu s hodnotou kořene; pokud je hodnota uzlu větší než hodnota kořenového uzlu, pak se uzel vloží do pravého podstromu, jinak se uzel vloží do levého podstromu. Jakmile je uzel vložen, není třeba kontrolovat faktor vyvážení výšky, aby bylo vložení dokončeno. | V případě AVL stromu nejprve najdeme vhodné místo pro vložení uzlu. Jakmile je uzel vložen, vypočítáme faktor vyvážení každého uzlu. Pokud je vyvážený faktor každého uzlu splněn, vkládání je dokončeno. Pokud je faktor vyvážení větší než 1, musíme provést několik rotací, abychom strom vyvážili. |
| Ve stromu binárního vyhledávání je výška nebo hloubka stromu O(n), kde n je počet uzlů ve stromu binárního vyhledávání. | Ve stromu AVL je výška nebo hloubka stromu O(logn). |
| Implementace je jednoduchá, protože pro vložení uzlu musíme sledovat vlastnosti binárního vyhledávání. | Implementace je složitá, protože ve stromu AVL musíme nejprve vytvořit strom AVL a poté musíme zkontrolovat vyvážení výšky. Pokud je výška nevyvážená, musíme provést několik rotací, abychom strom vyrovnali. |
| BST není vyvážený strom, protože se neřídí konceptem faktoru rovnováhy. | AVL strom je výškově vyvážený strom, protože se řídí konceptem faktoru rovnováhy. |
| Vyhledávání je v BST neefektivní, když je ve stromu k dispozici velký počet uzlů, protože výška není vyvážená. | Vyhledávání je ve stromu AVL efektivní, i když je ve stromu velký počet uzlů, protože výška je vyvážená. |