TechCodeview

Po prvé, pochopíme binárny strom a binárny vyhľadávací strom samostatne a potom sa pozrieme na rozdiely medzi binárnym stromom a binárnym vyhľadávacím stromom.

Čo je binárny strom?

A Binárny strom je aUkazovateľ na ľavé dieťa:Ukladá referenciu ľavého podriadeného uzla.Ukazovateľ na správne dieťa:Ukladá referenciu pravého podriadeného uzla.Dátový prvok:Údajový prvok je hodnota údajov, ktoré sú uložené uzlom.

Binárny strom môže byť reprezentovaný ako:

Na obrázku vyššie môžeme pozorovať, že každý uzol obsahuje maximálne 2 deti. Ak niektorý uzol neobsahuje ľavé alebo pravé dieťa, potom hodnota ukazovateľa vzhľadom na toto dieťa bude NULL.

Základné terminológie používané v binárnom strome sú:

Koreňový uzol:Koreňový uzol je prvý alebo najvyšší uzol v binárnom strome.Nadradený uzol:Keď je uzol pripojený k inému uzlu cez hrany, potom je tento uzol známy ako nadradený uzol. V binárnom strome môže mať nadradený uzol maximálne 2 potomkov.Podradený uzol:Ak má uzol svojho predchodcu, potom je tento uzol známy ako a detský uzol .Listový uzol:Uzol, ktorý neobsahuje žiadne dieťa známe ako a listový uzol .Vnútorný uzol:Uzol, ktorý má aspoň 2 deti, známy ako an vnútorný uzol .Hĺbka uzla:Vzdialenosť od koreňového uzla k danému uzlu je známa ako a hĺbka uzla . Poskytujeme označenia všetkým uzlom, ako napríklad koreňový uzol je označený 0, pretože nemá žiadnu hĺbku, deti koreňových uzlov sú označené 1, deti koreňového potomka sú označené 2.výška:Najdlhšia vzdialenosť od koreňového uzla po listový uzol je výška uzla .

V binárnom strome existuje jeden strom známy ako a dokonalý binárny strom . Je to a strom, v ktorom všetky vnútorné uzly musia obsahovať dva uzly a všetky listové uzly musia byť v rovnakej hĺbke. V prípade dokonalého binárneho stromu možno celkový počet uzlov v binárnom strome vypočítať pomocou nasledujúcej rovnice:

n = 2^m+1-1

kde n je počet uzlov, m je hĺbka uzla.

Čo je to strom binárneho vyhľadávania?

A Binárny vyhľadávací strom je strom, ktorý dodržiava určité poradie na usporiadanie prvkov, zatiaľ čo binárny strom nesleduje žiadne poradie. V binárnom vyhľadávacom strome musí byť hodnota ľavého uzla menšia ako rodičovský uzol a hodnota pravého uzla musí byť väčšia ako rodičovský uzol.

Poďme pochopiť koncept binárneho vyhľadávacieho stromu prostredníctvom príkladov.

Na obrázku vyššie môžeme pozorovať, že hodnota koreňového uzla je 15, čo je väčšia ako hodnota všetkých uzlov v ľavom podstrome. Hodnota koreňového uzla je menšia ako hodnoty všetkých uzlov v pravom podstrome. Teraz sa presunieme do ľavého potomka koreňového uzla. 10 je väčšie ako 8 a menšie ako 12; tiež spĺňa vlastnosti binárneho vyhľadávacieho stromu. Teraz sa presunieme do pravého potomka koreňového uzla; hodnota 20 je väčšia ako 17 a menšia ako 25; tiež spĺňa vlastnosti binárneho vyhľadávacieho stromu. Preto môžeme povedať, že strom zobrazený vyššie je binárny vyhľadávací strom.

Teraz, ak zmeníme hodnotu 12 na 16 vo vyššie uvedenom binárnom strome, musíme zistiť, či je to stále binárny vyhľadávací strom alebo nie.

Hodnota koreňového uzla je 15, čo je väčšie ako 10, ale menšie ako 16, takže nespĺňa vlastnosť binárneho vyhľadávacieho stromu. Nejde teda o binárny vyhľadávací strom.

Operácie na binárnom vyhľadávacom strome

V binárnom vyhľadávacom strome môžeme vykonávať operácie vkladania, mazania a vyhľadávania. Poďme pochopiť, ako sa vyhľadávanie vykonáva pri binárnom vyhľadávaní. Nižšie je zobrazený binárny strom, na ktorom musíme vykonať operáciu vyhľadávania:

Predpokladajme, že musíme hľadať 10 vo vyššie uvedenom binárnom strome. Ak chcete vykonať binárne vyhľadávanie, vezmeme do úvahy všetky celé čísla v zoradenom poli. Najprv vytvoríme úplný zoznam vo vyhľadávacom priestore a všetky čísla budú existovať vo vyhľadávacom priestore. Vyhľadávací priestor je označený dvoma ukazovateľmi, t. j. začiatkom a koncom. Pole vyššie uvedeného binárneho stromu môže byť reprezentované ako

Najprv vypočítame stredný prvok a porovnáme stredný prvok s prvkom, ktorý sa má hľadať. Stredný prvok sa vypočíta pomocou n/2. Hodnota n je 7; preto je stredný prvok 15. Stredný prvok sa nerovná hľadanému prvku, t. j. 10.

Poznámka: Ak je vyhľadávaný prvok menší ako stredný prvok, vyhľadávanie sa vykoná v ľavej polovici; v opačnom prípade sa vyhľadávanie vykoná na pravej polovici. V prípade rovnosti sa prvok nájde.

Keďže prvok, ktorý sa má vyhľadať, je menší ako stredný prvok, vyhľadávanie sa vykoná v ľavom poli. Teraz sa vyhľadávanie zredukuje na polovicu, ako je znázornené nižšie:

Stredný prvok v ľavom poli je 10, čo sa rovná hľadanému prvku.

Časová zložitosť

Pri binárnom vyhľadávaní je n prvkov. Ak sa prostredný prvok nerovná hľadanému prvku, potom sa priestor vyhľadávania zmenší na n/2 a budeme pokračovať v zmenšovaní priestoru vyhľadávania o n/2, kým prvok nenájdeme. V celej redukcii, ak sa presunieme z n na n/2 na n/4 a tak ďalej, tak to bude trvať log₂n krokov.

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