Sprievodca pre binárne stromy pre začiatočníkov

Ak ste absolvovali kurz dátových štruktúr v odbore počítačová veda alebo ste samouk, pravdepodobne ste sa stretli s pojmom „binárne stromy“. Aj keď môžu znieť trochu zdrvujúco a zložito, koncept binárneho stromu je celkom jednoduchý.

Prečítajte si, ako rozoberáme binárne stromy, a prečo sú pre programátorov nevyhnutným základným konceptom.

Čo sú to binárne stromy?

Binárne stromy patria medzi jednu z prvých dátových štruktúr, ktoré sú študenti vyučovaní v kurze dátových štruktúr. Binárny strom je tvorený mnohými uzlami a každý uzol binárneho stromu obsahuje dva ukazovatele, ktoré označujú ľavý a pravý podradený údajový uzol.

Prvý uzol v binárnom strome sa nazýva „koreň“. Uzly poslednej úrovne na strome sa nazývajú listy.

Každý uzol obsahuje údajovú položku a dva ukazovatele uzlov. Prázdny binárny strom je reprezentovaný nulovým ukazovateľom. Ako ste už mohli prísť na to, binárne stromy môžu mať iba dve deti (odtiaľ názov).

Typy binárnych štruktúr stromov

Existuje niekoľko rôznych binárnych stromových štruktúr v závislosti od spôsobu umiestnenia uzlov. Binárny strom sa nazýva úplný binárny strom, ak má každý uzol v strome buď nulu alebo dve deti. V perfektnom binárnom strome majú všetky uzly dve deti a listy sú všetky v rovnakej hĺbke.

Súvisiace: Najlepšie spôsoby, ako sa naučiť zadarmo kódovať

Kompletný binárny strom má uzly vyplnené na každej úrovni, s výnimkou poslednej úrovne. V úplných binárnych stromoch sú uzly sústredené na ľavej strane koreňa. Ďalšou bežnou štruktúrou je vyvážený binárny strom; v tejto štruktúre sa výšky pravého a ľavého podstromu musia líšiť maximálne o jeden. Tiež sa požaduje, aby bol vyvážený aj ľavý a pravý podstrom.

Je dôležité si uvedomiť, že výška vyváženého binárneho stromu je O (logn), kde n je počet uzlov v strome.

V niektorých prípadoch, ak má každý uzol iba jedno ľavé alebo pravé dieťa, potom sa z binárneho stromu môže stať šikmý binárny strom. Potom sa bude správať ako prepojený zoznam, takýmto stromom sa hovorí aj degenerovaný strom.

Čo sú binárne vyhľadávacie stromy?

Binárny vyhľadávací strom (BST) je v podstate usporiadaný binárny strom so špeciálnou vlastnosťou známou ako vlastnosť „binárny vyhľadávací strom“. Vlastnosť BST znamená, že uzly s hodnotou kľúča menšou ako koreň sú umiestnené v ľavom podstrome a uzly s hodnotou kľúča vyššou ako koreň sú súčasťou pravého podstromu.

Vlastnosť BST musí byť pravdivá pre každý nasledujúci nadradený uzol v strome.

Binárne vyhľadávacie stromy ponúkajú rýchle vkladanie a vyhľadávanie. Operácie vkladania, mazania a vyhľadávania majú v najhoršom prípade časovú zložitosť O (n), ktorá je podobná prepojenému zoznamu.

Výhody binárnych stromov

Binárne stromy ponúkajú mnoho výhod, a preto zostávajú veľmi užitočnou štruktúrou údajov. Môžu byť použité na zobrazenie štrukturálnych vzťahov a hierarchií v súbore údajov. Ešte dôležitejšie je, že binárne stromy umožňujú efektívne vyhľadávanie, mazanie a vkladanie.

Je tiež veľmi jednoduché implementovať a udržiavať binárny strom. Binárny strom ponúka programátorom výhody usporiadaného poľa a prepojeného zoznamu; vyhľadávanie v binárnom strome je rovnako rýchle ako v triedenom poli a operácie vkladania alebo odstraňovania sú rovnako účinné ako v prepojených zoznamoch.

Binárne stromy sú dôležité dátové štruktúry

Binárne stromy sú veľmi dôležitou štruktúrou údajov a je veľmi dôležité, aby ich programátori mohli pohodlne používať vo svojich programoch. Anketári sa často pýtajú na jednoduché problémy s binárnymi stromami, ako sú traverzy, maximálna hĺbka, zrkadlenie atď.

Odporúčame porozumieť konceptu binárnych stromov a zoznámiť sa s typickými problémami s rozhovormi.

TreeViz: Jednoduchý spôsob vizualizácie dátových štruktúr

Čítajte ďalej

O autorovi