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 ⁶⁴ - 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