Kľúčový rozdiel – binárny strom a binárny vyhľadávací strom
Údajová štruktúra je systematický spôsob, ako organizovať údaje a efektívne ich využívať. Usporiadanie údajov pomocou štruktúry údajov by malo skrátiť čas chodu alebo čas vykonania. Štruktúra údajov by tiež mala vyžadovať minimálne množstvo pamäte. Niekedy môžu byť údaje usporiadané do stromovej štruktúry. Strom predstavuje uzol spojený hranami. Najvyšší uzol je koreň. Každý uzol môže mať maximálne dva uzly. Sú známe ako detské uzly. Uzol naľavo od nadradeného uzla je ľavý podriadený uzol, zatiaľ čo uzol napravo od nadradeného uzla je pravý uzol. Binárny strom a binárny vyhľadávací strom sú dve stromové dátové štruktúry. Binárny strom je typ dátovej štruktúry, kde každý nadradený uzol môže mať najviac dva podriadené uzly. Binárny vyhľadávací strom je binárny strom, kde ľavý potomok obsahuje iba uzly s hodnotami menšími alebo rovnými rodičovskému uzlu a kde pravý potomok obsahuje iba uzly s hodnotami väčšími ako nadradený uzol. To je kľúčový rozdiel. Na rozdiel od dátových štruktúr, ako sú polia, binárny strom a binárny vyhľadávací strom nemajú horný limit na ukladanie dát.
Čo je binárny strom?
Pri usporiadaní údajov do stromovej štruktúry je uzol v hornej časti stromu známy ako koreňový uzol. Pre celý strom môže byť len jeden koreň. Každý uzol okrem koreňového má jednu hranu smerom nahor k uzlu. Nazýva sa rodičovský uzol. Uzol pod nadradeným kódom sa nazýva jeho dcérsky uzol. Každý nadradený uzol môže mať maximálne dva podriadené uzly. Označujú sa ako ľavý detský uzol a pravý detský uzol. Uzol bez akéhokoľvek dcérskeho uzla sa nazýva listový uzol. Neexistuje žiadny konkrétny spôsob usporiadania údajov v binárnom strome. Od koreňového uzla ku každému uzlu existuje cesta.
Obrázok 01: Príklad binárneho stromu
Vyššie je uvedený príklad binárneho stromu. Prvok 2 v hornej časti stromu je koreň. Každý uzol má maximálne dva uzly. Ak strom obsahuje slučky alebo ak jeden uzol obsahuje viac ako dva uzly, nemôže byť klasifikovaný ako binárny strom. Na prechod z jedného uzla do druhého vždy existuje jedna cesta. Podriadené uzly koreňového uzla 2 sú 7 a 5. Je tiež možné, že uzol nebude mať žiadne uzly. Žiadny uzol však nemôže mať viac ako dva uzly. Pravý prvok koreňa je 5. Tento prvok 5 je rodičovským uzlom pre podriadený uzol 9. Uzol 4 a 11 nemá žiadne podradené prvky. Preto sú to listové uzly.
Binárny strom sa používa na ukladanie údajov v hierarchickom poradí. Je podobná štruktúre súborov v počítači. Dátová štruktúra ako pole môže uchovávať špecifické množstvo údajov. Ale v binárnom strome neexistuje horná hranica počtu uzlov.
Čo je binárny vyhľadávací strom?
Binárny vyhľadávací strom je binárna stromová dátová štruktúra. Podobne ako binárny strom, aj binárny vyhľadávací strom môže mať dva uzly. Každý uzol okrem koreňového má jednu hranu smerom nahor k uzlu. Nazýva sa rodičovský uzol. Uzol pod daným pripojeným okrajom smerom nadol sa nazýva jeho dcérsky uzol. Uzol bez akéhokoľvek dcérskeho uzla sa nazýva listový uzol. Každý nadradený uzol môže mať maximálne dva uzly. Existujú podradené uzly odkazujúce na ľavý podriadený uzol a pravý podriadený uzol. Najvyšší prvok sa nazýva koreňový uzol. Ľavý potomok obsahuje iba uzly s hodnotami menšími alebo rovnakými ako nadradený uzol. Pravý potomok obsahuje iba uzly s hodnotami väčšími alebo rovnými nadradeným uzlom.
Obrázok 02: Príklad binárneho vyhľadávacieho stromu
Prvok 8 je najvyšší prvok. Preto je to koreňový uzol. Ak je 3 nadradený uzol, potom 1 a 6 sú podriadené uzly. 1 je ľavý podriadený uzol, zatiaľ čo 6 je pravý podriadený uzol. Ľavý potomok obsahuje hodnoty menšie alebo rovné nadradenému uzlu. Keď je 3 nadradený uzol, ľavá strana by mala obsahovať prvok, ktorý je menší alebo rovný 3. V tomto príklade je to 1. Pravý potomok obsahuje len uzly s hodnotami väčšími ako nadradený uzol. Keď je 3 nadradený uzol, pravý podriadený uzol by mal mať vyššiu hodnotu ako 3. V tomto príklade je to 6. Podobne existuje určité poradie usporiadania každého dátového prvku do binárneho vyhľadávacieho stromu. Ide o dátovú štruktúru, ktorá poskytuje efektívny spôsob triedenia, získavania a vyhľadávania dát.
Aké sú podobnosti medzi binárnym stromom a binárnym vyhľadávacím stromom?
- Binárny strom aj binárny vyhľadávací strom sú hierarchické dátové štruktúry.
- Binárny strom aj binárny vyhľadávací strom majú koreň.
- Binárny strom aj binárny vyhľadávací strom môžu mať maximálne dva podradené uzly.
Aký je rozdiel medzi binárnym stromom a binárnym vyhľadávacím stromom?
Binárny strom vs binárny vyhľadávací strom |
|
| Binárny strom je typ dátovej štruktúry, kde každý nadradený uzol môže mať maximálne dva podradené uzly. | Binárny vyhľadávací strom je binárny strom, kde ľavý potomok obsahuje iba uzly s hodnotami menšími alebo rovnými nadradeným uzlom a kde pravý potomok obsahuje len uzly s hodnotami väčšími ako nadradený uzol. |
| Objednávka na usporiadanie údajov | |
| Binárny strom nemá špecifické poradie na usporiadanie dátových prvkov. | Binárny vyhľadávací strom má špecifické poradie usporiadania dátových prvkov. |
| Použitie | |
| Binárny strom sa používa ako efektívne vyhľadávanie údajov a informácií v stromovej štruktúre. | Na vkladanie, mazanie a vyhľadávanie údajov sa používa binárny vyhľadávací strom. |
Summary – Binary Tree vs. Binary Search Tree
Dátová štruktúra je spôsob organizácie údajov. Niekedy môžu byť údaje usporiadané do stromovej štruktúry. Dva z nich sú binárny strom a binárny vyhľadávací strom. Tento článok diskutoval o rozdieloch medzi binárnym stromom a binárnym vyhľadávacím stromom. Binárny strom je typ dátovej štruktúry, kde každý nadradený uzol môže mať najviac dva podriadené uzly. Binárny vyhľadávací strom je binárny strom, kde ľavý potomok obsahuje iba uzly s hodnotami menšími alebo rovnými rodičovskému uzlu a kde pravý potomok obsahuje len uzly s hodnotami väčšími ako nadradený uzol.
Stiahnite si PDF binárny strom vs binárny vyhľadávací strom
Verziu tohto článku si môžete stiahnuť vo formáte PDF a použiť ju na offline účely podľa citácie. Stiahnite si PDF verziu tu: Rozdiel medzi binárnym stromom a binárnym vyhľadávacím stromom
