Vianoce v ITnetwork sú tu! Dobí si teraz kredity a získaj až 80 % extra kreditov na e-learningové kurzy ZADARMO. Zisti viac.
Hľadáme nové posily do ITnetwork tímu. Pozri sa na voľné pozície a pridaj sa k najagilnejšej firme na trhu - Viac informácií.

14. diel - Binárne vyhľadávacie stromy (BST) v jazyku C

V minulej lekcii, Implementácia hash tabuľky v jazyku C , sme hľadali podľa hash kľúča.

V dnešnej lekcii si predstavíme a implementujeme binárny vyhľadávací strom. Najprv si však ukážeme jeden reálny príklad mocnín a logaritmov, aby sme pochopili, ako veľmi nám táto dátová štruktúra uľahčí život.

Legenda o šachistovi

Existuje legenda, že šachista v ďalekej Ázii si od vladára za svoje šachové umenie vyžiadal len "malú" odmenu, teda aby mu daroval "trochu" ryža. Vladár odpovedal: "Povedz, koľko ryže chceš". Keďže šachista bol "veľmi skromný", tak vladári opísal nasledujúce algoritmus: "Na prvé políčko šachovnice mi daj jedno zrnko ryže, na druhej dve zrnká, na tretiu štyri zrnká, na štvrtej osem zrniek, na piatej šestnásť zrniek a takto až po políčko šesťdesiat štyri. " Vladár odpovedal: "Ak chceš tak málo, tak nech ťa hneď oplatí". Za chvíľu jeho správcovia z hrôzou pribehli, že toľko ryža nie je v celej krajine. Asi tušíte, čo sa stalo.

Ide o to, že počet zrniek ryže je presne 2 64 - 1 = 18 446 744 073 709 551 615. Toľko ryža mu neprinesú na našej planéte ani za sto rokov.

S výpočtom tejto položky majú problémy aj naše súčasné počítače, respektíve kompilátory jazyka C, ale aj iných jazykov. Microsoft napríklad podporuje iba číslo unsigned long v 64 bitovej podobe, čo nám nestačí. V jazyku ako Haskel to samozrejme zvládneme. A ak výsledok vyjadríme ako reálne číslo (double), ktoré je 1.8446744073709552 * 10 19, tak samozrejme aj v C.

Ale prečo sme si uviedli tento príklad v lekcii o binárnych stromoch? Pokiaľ vieme na 64 krokov dosiahnuť tak absurdne vysoké mocniny, tak i spätne sa dá logaritmicky dostať maximálne po 64 krokoch k nejakej položke, ktorú hľadáme v extrémne dlhom zozname. Na to nám pomáha binárny strom.

Binárny strom

Jeho štruktúra je v podstate veľmi jednoduchá:


 

...koniec náhľadu článku...
Pokračuj ďalej

Vedomosti v hodnote stoviek tisíc získaš za pár korún

Minul si až sem a to je super! Veríme, že ti prvé lekcie ukázali niečo nového a užitočného.
Chceš v kurze pokračovať? Prejdi do prémiové sekcie.

Obmedzená ponuka: Nauč sa všetko a ušetri

Kúpiť všetky aktuálne dostupné lekcie s funkciou odovzdávanie úloh za exkluzívnu cenu 300 kreditov
Aktuálny stav konta 0 kreditov
Kúpou tohoto výhodného balíčku získaš prístup ku všetkým 17 článkom (17 lekcií) s kontrolou a certifikáciou a ešte naviac ušetríš 76 Kč. Ponuka je časovo obmedzená a platí pro všetky lekcie v kurze. Nakúp teraz a získaj limitovanou 20% zľavu.

Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.

Čo od nás v ďalších lekciách dostaneš?
  • Neobmedzený a trvalý prístup k jednotlivým lekciím.
  • Kvalitné znalosti v oblasti IT.
  • Zručnosti, ktoré ti pomôžu získať vysnívanú a dobre platenú prácu.

Popis článku

Požadovaný článok má nasledujúci obsah:

C tutoriál o vytváraní binárnych stromov a prechádzaní cez binárne stromy. Ukážeme si, prečo sú binárne stromy veľmi výkonné.

Kredity získaš, keď podporíš našu sieť. To môžeš urobiť buď zaslaním symbolickej sumy na podporu prevádzky alebo pridaním obsahu na sieť.

Článok pre vás napísal Daniel Martinko
Avatar
Aktivity