Klíčový rozdíl – binární strom vs binární vyhledávací strom
Struktura dat je systematický způsob, jak organizovat data tak, aby je bylo možné efektivně využívat. Uspořádání dat pomocí datové struktury by mělo zkrátit dobu běhu nebo dobu provádění. Také datová struktura by měla vyžadovat minimální množství paměti. Někdy mohou být data uspořádána do stromové struktury. Strom představuje uzel spojený hranami. Nejvyšší uzel je kořen. Každý uzel může mít maximálně dva uzly. Jsou známé jako podřízené uzly. Uzel nalevo od nadřazeného uzlu je levý podřízený uzel, zatímco uzel napravo od nadřazeného uzlu je pravý uzel. Binární strom a binární vyhledávací strom jsou dvě stromové datové struktury. Binární strom je typ datové struktury, kde každý nadřazený uzel může mít maximálně dva podřízené uzly. Binární vyhledávací strom je binární strom, kde levý potomek obsahuje pouze uzly s hodnotami menšími nebo rovnými nadřazenému uzlu a kde pravý potomek obsahuje pouze uzly s hodnotami většími než nadřazený uzel. To je klíčový rozdíl. Na rozdíl od datových struktur, jako jsou pole, binární strom a binární vyhledávací strom nemají horní limit pro ukládání dat.
Co je binární strom?
Při uspořádání dat do stromové struktury se uzel v horní části stromu nazývá kořenový uzel. Pro celý strom může být pouze jeden kořen. Jakýkoli uzel kromě kořenového má jednu hranu směrem nahoru k uzlu. Říká se mu rodičovský uzel. Uzel pod nadřazeným kódem se nazývá jeho podřízený uzel. Každý nadřazený uzel může mít maximálně dva podřízené uzly. Jsou označovány jako levý podřízený uzel a pravý podřízený uzel. Uzel bez podřízeného uzlu se nazývá listový uzel. Neexistuje žádný konkrétní způsob, jak uspořádat data v binárním stromu. Ke každému uzlu existuje cesta od kořenového uzlu.
Obrázek 01: Příklad binárního stromu
Výše je příklad binárního stromu. Prvek 2 v horní části stromu je kořen. Každý uzel má maximálně dva uzly. Pokud strom obsahuje nějaké smyčky nebo pokud jeden uzel obsahuje více než dva uzly, nelze jej klasifikovat jako binární strom. Chcete-li přejít z jednoho uzlu do druhého, vždy existuje jedna cesta. Podřízené uzly kořenového uzlu 2 jsou 7 a 5. Je také možné, aby uzel neměl žádné uzly. Žádný uzel však nemůže mít více než dva uzly. Pravý prvek kořene je 5. Tento prvek 5 je nadřazeným uzlem pro podřízený uzel 9. Uzel 4 a 11 nemají žádné podřízené prvky. Proto jsou to listové uzly.
Binární strom se používá k ukládání dat v hierarchickém pořadí. Je podobná struktuře souborů v počítači. Datová struktura jako pole může ukládat určité množství dat. Ale v binárním stromu neexistuje horní limit počtu uzlů.
Co je binární vyhledávací strom?
Binární vyhledávací strom je binární stromová datová struktura. Podobně jako binární strom může mít binární vyhledávací strom také dva uzly. Jakýkoli uzel kromě kořenového má jednu hranu směrem nahoru k uzlu. Říká se mu rodičovský uzel. Uzel pod daným připojeným okrajem směrem dolů se nazývá jeho podřízený uzel. Uzel bez podřízeného uzlu se nazývá listový uzel. Každý nadřazený uzel může mít maximálně dva uzly. Existují podřízené uzly odkazující na levý podřízený uzel a pravý podřízený uzel. Nejvyšší prvek se nazývá kořenový uzel. Levý potomek obsahuje pouze uzly s hodnotami menšími nebo rovnými nadřazenému uzlu. Pravý podřízený uzel obsahuje pouze uzly s hodnotami většími nebo rovnými nadřazenému uzlu.
Obrázek 02: Příklad binárního vyhledávacího stromu
Prvek 8 je nejvyšší prvek. Jedná se tedy o kořenový uzel. Pokud je 3 nadřazený uzel, pak 1 a 6 jsou podřízené uzly. 1 je levý podřízený uzel, zatímco 6 je pravý podřízený uzel. Levý potomek obsahuje hodnoty menší nebo rovné nadřazenému uzlu. Když je 3 nadřazený uzel, levá strana by měla mít prvek, který je menší nebo roven 3. V tomto příkladu je to 1. Pravý potomek obsahuje pouze uzly s hodnotami většími než nadřazený uzel. Když je 3 nadřazený uzel, pravý podřízený uzel by měl mít vyšší hodnotu než 3. V tomto příkladu je to 6. Podobně existuje určité pořadí pro uspořádání každého datového prvku do binárního vyhledávacího stromu. Jedná se o datovou strukturu, která poskytuje efektivní způsob, jak provádět třídění, načítání a vyhledávání dat.
Jaké jsou podobnosti mezi binárním stromem a binárním vyhledávacím stromem?
- Binární strom i binární vyhledávací strom jsou hierarchické datové struktury.
- Binární strom i binární vyhledávací strom mají kořen.
- Binární strom i binární vyhledávací strom mohou mít maximálně dva podřízené uzly.
Jaký je rozdíl mezi binárním stromem a binárním vyhledávacím stromem?
Binární strom vs binární vyhledávací strom |
|
| Binární strom je typ datové struktury, kde každý nadřazený uzel může mít maximálně dva podřízené uzly. | Binární vyhledávací strom je binární strom, kde levý potomek obsahuje pouze uzly s hodnotami menšími nebo rovnými nadřazenému uzlu a kde pravý potomek obsahuje pouze uzly s hodnotami většími než nadřazený uzel. |
| Objednávka sjednání dat | |
| Binární strom nemá konkrétní pořadí pro uspořádání datových prvků. | Binární vyhledávací strom má specifické pořadí uspořádání datových prvků. |
| Použití | |
| Binární strom se používá jako efektivní vyhledávání dat a informací ve stromové struktuře. | Pro vkládání, mazání a vyhledávání dat se používá binární vyhledávací strom. |
Shrnutí – binární strom vs binární vyhledávací strom
Datová struktura je způsob organizace dat. Někdy mohou být data uspořádána do stromové struktury. Dva z nich jsou binární strom a binární vyhledávací strom. Tento článek pojednával o rozdílu mezi binárním stromem a binárním vyhledávacím stromem. Binární strom je typ datové struktury, kde každý nadřazený uzel může mít maximálně dva podřízené uzly. Binární vyhledávací strom je binární strom, kde levý potomek obsahuje pouze uzly s hodnotami menšími nebo rovnými nadřazenému uzlu a kde pravý potomek obsahuje pouze uzly s hodnotami většími než nadřazený uzel.
Stáhněte si PDF binární strom vs binární vyhledávací strom
Verzi tohoto článku si můžete stáhnout ve formátu PDF a použít ji pro offline účely podle citace. Stáhněte si prosím PDF verzi zde: Rozdíl mezi binárním stromem a binárním vyhledávacím stromem
