Rozdiel medzi binárnym stromom a stromom binárneho vyhľadávania

Čo je binárny strom?

Binárny strom je hierarchická dátová štruktúra, v ktorej má každý uzol nula, jedno alebo nanajvýš dve deti. Každý uzol obsahuje „ľavý“ ukazovateľ, „pravý“ ukazovateľ a dátový prvok. Ukazovateľ „root“ predstavuje najvyšší uzol v strome. Každý uzol v dátovej štruktúre je priamo spojený s ľubovoľným počtom uzlov na oboch stranách, označovaných ako deti. Nulový ukazovateľ predstavuje binárny strom. Neexistuje nijaké konkrétne poradie, ako majú byť uzly usporiadané v binárnom strome. Uzly bez detských uzlov sa nazývajú listové uzly alebo externé uzly.

Jednoducho povedané, definuje organizovanú funkciu označovania na uzloch, ktoré zase každému uzlu priradia nejakú náhodnú hodnotu. Všetko, čo má dve deti a jeden rodičovský uzol, je binárny strom. Binárne stromy sa používajú na ukladanie informácií, ktoré tvoria hierarchiu, napríklad systém súborov na vašom osobnom počítači. Na rozdiel od polí nemajú stromy hornú hranicu počtu uzlov, pretože sú prepojené pomocou ukazovateľov, napríklad prepojených zoznamov. Medzi hlavné funkcie binárneho stromu patrí zastupovanie hierarchických údajov, triedenie zoznamov údajov, zabezpečenie efektívnych operácií vkladania / odstraňovania atď. Stromové uzly sú zastúpené pomocou štruktúr v C.

Čo je binárny vyhľadávací strom?

Binárny vyhľadávací strom je typ štruktúry binárnych stromov, v ktorej sú uzly usporiadané v poradí, preto sa tiež nazývajú „usporiadaný binárny strom“. Je to dátová štruktúra založená na uzloch, ktorá poskytuje efektívny a rýchly spôsob triedenia, získavania a vyhľadávania údajov. Pre každý uzol musia byť prvky v ľavom podstrome menšie alebo rovnaké ako kľúč v jeho nadradenom uzle (LP). Nemali by existovať duplicitné kľúče. Jednoducho povedané, je to špeciálny druh dátovej štruktúry binárnych stromov, ktorý efektívne ukladá a spravuje položky v pamäti.

Umožňuje rýchly prístup k informáciám, vkladanie a odstraňovanie údajov a môže sa použiť na implementáciu vyhľadávacích tabuliek, ktoré umožňujú vyhľadávanie položiek podľa ich jedinečných kľúčov, napríklad vyhľadávanie telefónneho čísla osoby podľa mena. Unikátne kľúče sú usporiadané usporiadaným spôsobom, takže vyhľadávanie a ďalšie dynamické operácie by sa mohli vykonávať pomocou binárneho vyhľadávania. Podporuje tri hlavné operácie: vyhľadávanie prvkov, vkladanie prvkov a odstraňovanie prvkov. Binárny vyhľadávací strom umožňuje rýchle načítanie prvkov uložených v strome, pretože každý kľúč uzla je dôkladne porovnávaný s koreňovým uzlom, ktorý zahodí polovicu stromu.

Rozdiel medzi binárnym stromom a binárnym vyhľadávacím stromom

1. Definícia binárneho stromu a binárneho vyhľadávacieho stromu - Binárny strom je hierarchická dátová štruktúra, v ktorej dieťa môže mať nula, jeden alebo maximálne dva podriadené uzly; každý uzol obsahuje ľavý ukazovateľ, pravý ukazovateľ a dátový prvok. Neexistuje žiadny konkrétny poriadok, ako by mali byť uzly usporiadané v strome. Binárny vyhľadávací strom, na druhej strane, je usporiadaný binárny strom, v ktorom je relatívne poradie usporiadania uzlov..
2. štruktúra z Binárny strom a binárny vyhľadávací strom- Najvyšší uzol v strome predstavuje koreňový ukazovateľ v binárnom strome a ľavý a pravý ukazovateľ predstavujú menšie stromy na oboch stranách. Je to špecializovaná forma stromu, ktorá predstavuje údaje v stromovej štruktúre. Na druhej strane strom binárneho vyhľadávania je typom binárneho stromu, v ktorom všetky uzly v ľavom podstrome sú menšie alebo sa rovnajú hodnote koreňového uzla a hodnota pravého podstromu je väčšia alebo sa rovná hodnote koreňového uzla.
3. operácie z Binárny strom a binárny vyhľadávací strom- Binárny strom môže byť čokoľvek, čo má dve deti a jedného rodiča. Bežné operácie, ktoré je možné vykonávať na binárnom strome, sú vkladanie, mazanie a prechod. Binárne vyhľadávacie stromy sú skôr triedené binárne stromy, ktoré umožňujú rýchle a efektívne vyhľadávanie, vkladanie a mazanie položiek. Na rozdiel od binárnych stromov si binárne vyhľadávacie stromy zachovávajú svoje kľúče zoradené, takže vyhľadávanie zvyčajne implementuje binárne vyhľadávanie operácií.
4. druhy z Binárny strom a binárny vyhľadávací strom- Existujú rôzne typy binárnych stromov, ktoré sú spoločné ako „úplný binárny strom“, „kompletný binárny strom“, „perfektný binárny strom“ a „rozšírený binárny strom“. Medzi bežné typy binárnych vyhľadávacích stromov patria T-stromy, AVL stromy, stromové stromy, stromy Tango, červeno-čierne stromy atď..

Binárny strom verzus binárny vyhľadávací strom: porovnávacia tabuľka

Zhrnutie binárneho stromu a binárneho vyhľadávacieho stromu

Zatiaľ čo obidva simulujú hierarchickú stromovú štruktúru predstavujúcu kolekciu uzlov, pričom každý uzol predstavuje určitú hodnotu, navzájom sa od seba líšia v tom, ako sa dajú implementovať a využívať. Binárny strom sa riadi jedným jednoduchým pravidlom, že každý rodičovský uzol nemá viac ako dva podriadené uzly, zatiaľ čo strom binárneho vyhľadávania je iba variantom binárneho stromu, ktorý sleduje relatívne poradie usporiadania uzlov v strome..