Home-theater-designersAk ste absolvovali kurz dátových štruktúr na hodine informatiky alebo ste programátor samouk, je pravdepodobné, že ste sa stretli s pojmom binárne stromy. Aj keď to môže znieť trochu zdrvujúco a zložito, koncept binárneho stromu je celkom jednoduchý.
Windows 10 hovorí, že nie som pripojený k internetu, ale ja som
Prečítajte si, ako rozoberáme binárne stromy, a prečo sú nevyhnutným základným konceptom pre programátorov.
Č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ť kódovať zadarmo
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 je 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.
ako zistiť, kto vás zablokoval na instagrame
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 štruktúrnych 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.
máme problém s prehrávaním tohto titulu
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ď.
Dôrazne odporúčame porozumieť konceptu binárnych stromov a zoznámiť sa s typickými problémami s rozhovormi.
zdieľam zdieľam Tweet E -mail TreeViz: Jednoduchý spôsob vizualizácie dátových štruktúr Čítajte ďalej Súvisiace témy- Programovanie
- Analýza dát
- Programovanie
Fahad je spisovateľ v MakeUseOf a v súčasnosti sa špecializuje na počítačovú vedu. Ako zanietený technický spisovateľ dbá na to, aby bol informovaný o najnovších technológiách. Zvlášť sa zaujíma o futbal a technológie.
Viac od M. Fahada Khawajaprihlásiť sa ku odberu noviniek
Pripojte sa k nášmu bulletinu a získajte technické tipy, recenzie, bezplatné elektronické knihy a exkluzívne ponuky!
Kliknutím sem sa prihlásite na odber