Definícia
Binárny strom je usporiadaný strom druhého stupňa, v ktorom má každý vrchol najviac dvoch synov.
Definovaný je rekurzívne.
Binárny strom T je štruktúra definovaná na konečnej množine prvkov (vrcholov),
kde každá je buď prázdna, alebo sa skladá z koreňa (vrchola) a z dvoch disjunktných
stromov nazývaných ľavý a pravý podstrom koreňa.
Príkladom binárneho stromu je rodokmeň, kde matka a otec tvoria nasledovníkov (!) príslušnej osoby.
Vlastnosti
Strom je dokonale vyvážený, ak pre každý vrchol platí, že počet vrcholov v jeho ľavom a pravom podstrome sa líši najviac o jeden vrchol.
Pravidlo rovnomernej distribúcie známeho počtu n vrcholov sa dá najlepšie formulovať rekurzívne:
a) zvolí sa jeden vrchol za koreň stromu
b) vytvorí sa ľavý podstrom s počtom koreňov nl = n div 2
c) vytvorí sa pravý podstrom s počtom koreňov nr = n – nl – 1
Transformácia n-árneho stromu na binárny
Ak chceme reprezentovať obyčajný n-árny strom ako binárny, použijeme algoritmus priamej
transformácie z n-árneho stromu do binárneho.
Každý vrchol N v pôvodnom strome zodpovedá vrcholu N' v binárnom strome.
Ľavý syn N' je vrchol zodpovedajúci prvému synovi N a pravý syn
N' je vrchol
zodpovedajúci nasledujúcemu bratovi N'. To znamená vrcholu, ktorý je ďalší v
poradí medzi synmi otca N.
Môžeme sa na problém pozerať ako na spájaný zoznam. Synovia každého uzla N sú v
spájanom zozname spojení pomocou svojich pravých odkazov a uzol N má smerník na
tento spájaný zoznam cez svoj ľavý odkaz.
Binárne prehľadávacie stromy
Binárny vyhľadávací strom je dátová štruktúra založená na binárnom strome. Kľúče vo vrcholoch sú usporiadané tak,
že hodnota uložená v u je väčšia alebo rovná ako hodnota
uložená v ľavom podstrome u. A obdobne, hodnota uložená v u je menšia alebo rovná ako hodnota
uložená v pravom podstrome u. Takto je možné ľahko vyhľadávať jednotlivé kľúče binárnym vyhľadávaním.
Sú to taktiež dátové štruktúry podporujúce operácie na dynamických množinách vrátane Search, Minimum, Maximum, Predecessor, Successor,
Insert a Delete. Možno ich použiť ako slovník, alebo prioritný front.
Základné operácie trvajú čas úmerný výške stromu. Na úplnom binárnom strome s n uzlami tieto operácie trvajú v najhoršom prípade
čas Theta(lg n). Ak je strom lineárny (každý uzol má najviac jedného potomka) tak tieto operácie trvajú v najhoršom prípade
čas Theta(n).