TechCodeview

Nejprve pochopíme binární strom a binární vyhledávací strom samostatně a pak se podíváme na rozdíly mezi binárním stromem a binárním vyhledávacím stromem.

Co je to binární strom?

A Binární strom jeUkazatel na levé dítě:Ukládá odkaz levého podřízeného uzlu.Ukazatel na správné dítě:Ukládá odkaz pravého podřízeného uzlu.Datový prvek:Datový prvek je hodnota dat, která jsou uložena uzlem.

Binární strom může být reprezentován jako:

Na obrázku výše můžeme pozorovat, že každý uzel obsahuje maximálně 2 potomky. Pokud žádný uzel neobsahuje levé nebo pravé potomky, pak by hodnota ukazatele vzhledem k tomuto potomku byla NULL.

Základní terminologie používané v binárním stromu jsou:

Kořenový uzel:Kořenový uzel je první nebo nejvyšší uzel v binárním stromu.Nadřazený uzel:Když je uzel připojen k jinému uzlu přes hrany, pak je tento uzel známý jako nadřazený uzel. V binárním stromu může mít nadřazený uzel maximálně 2 potomky.Podřízený uzel:Pokud má uzel svého předchůdce, pak se tento uzel nazývá a podřízený uzel .Listový uzel:Uzel, který neobsahuje žádné potomky známé jako a listový uzel .Vnitřní uzel:Uzel, který má alespoň 2 děti známé jako an vnitřní uzel .Hloubka uzlu:Vzdálenost od kořenového uzlu k danému uzlu je známá jako a hloubka uzlu . Poskytujeme štítky všem uzlům, jako je kořenový uzel označený 0, protože nemá žádnou hloubku, potomci kořenových uzlů jsou označeni 1, děti kořenového potomka jsou označeny 2.Výška:Nejdelší vzdálenost od kořenového uzlu k listovému uzlu je výška uzlu .

V binárním stromu existuje jeden strom známý jako a dokonalý binární strom . Je to a strom, ve kterém všechny vnitřní uzly musí obsahovat dva uzly a všechny listové uzly musí být ve stejné hloubce. V případě dokonalého binárního stromu lze celkový počet uzlů v binárním stromu vypočítat pomocí následující rovnice:

n = 2^m+1-1

kde n je počet uzlů, m je hloubka uzlu.

Co je to strom binárního vyhledávání?

A Binární vyhledávací strom je strom, který se řídí určitým pořadím pro uspořádání prvků, zatímco binární strom nesleduje žádné pořadí. Ve stromu binárního vyhledávání musí být hodnota levého uzlu menší než nadřazený uzel a hodnota pravého uzlu musí být větší než nadřazený uzel.

Pojďme pochopit koncept binárního vyhledávacího stromu prostřednictvím příkladů.

Na obrázku výše můžeme pozorovat, že hodnota kořenového uzlu je 15, což je větší než hodnota všech uzlů v levém podstromu. Hodnota kořenového uzlu je menší než hodnoty všech uzlů v pravém podstromu. Nyní se přesuneme do levého potomka kořenového uzlu. 10 je větší než 8 a menší než 12; splňuje také vlastnost binárního vyhledávacího stromu. Nyní se přesuneme do pravého potomka kořenového uzlu; hodnota 20 je větší než 17 a menší než 25; splňuje také vlastnost binárního vyhledávacího stromu. Můžeme tedy říci, že výše uvedený strom je binární vyhledávací strom.

Nyní, pokud změníme hodnotu 12 na 16 ve výše uvedeném binárním stromu, musíme zjistit, zda se stále jedná o binární vyhledávací strom nebo ne.

Hodnota kořenového uzlu je 15, což je větší než 10, ale menší než 16, takže nesplňuje vlastnost binárního vyhledávacího stromu. Nejedná se tedy o binární vyhledávací strom.

Operace na binárním vyhledávacím stromě

Na binárním vyhledávacím stromě můžeme provádět operace vkládání, mazání a vyhledávání. Pojďme pochopit, jak se provádí vyhledávání na binárním vyhledávání. Níže je zobrazen binární strom, na kterém musíme provést operaci vyhledávání:

Předpokládejme, že musíme hledat 10 ve výše uvedeném binárním stromu. K provedení binárního vyhledávání budeme uvažovat všechna celá čísla v seřazeném poli. Nejprve vytvoříme úplný seznam ve vyhledávacím prostoru a všechna čísla budou existovat ve vyhledávacím prostoru. Vyhledávací prostor je označen dvěma ukazateli, tj. začátkem a koncem. Pole výše uvedeného binárního stromu může být reprezentováno jako

Nejprve spočítáme prostřední prvek a porovnáme prostřední prvek s prvkem, který se má hledat. Střední prvek se vypočítá pomocí n/2. Hodnota n je 7; tedy prostřední prvek je 15. Prostřední prvek se nerovná hledanému prvku, tedy 10.

Poznámka: Pokud je hledaný prvek menší než prostřední prvek, bude vyhledávání provedeno v levé polovině; v opačném případě bude vyhledávání provedeno na pravé polovině. V případě rovnosti je prvek nalezen.

Vzhledem k tomu, že prvek, který má být prohledán, je menší než střední prvek, bude vyhledávání prováděno na levém poli. Nyní je vyhledávání sníženo na polovinu, jak je znázorněno níže:

Střední prvek v levém poli je 10, což se rovná hledanému prvku.

Časová složitost

V binárním vyhledávání existuje n prvků. Pokud se prostřední prvek nerovná hledanému prvku, pak se vyhledávací prostor zmenší na n/2 a budeme zmenšovat vyhledávací prostor o n/2, dokud prvek nenajdeme. V celé redukci, pokud se přesuneme z n na n/2 na n/4 a tak dále, bude trvat log₂n kroků.

Rozdíly mezi binárním stromem a binárním vyhledávacím stromem