Lekce 14 - Binární vyhledávací stromy (BST) v jazyce C

V minulé lekci, Implementace hash tabulky v jazyce C, jsme hledali podle hash klíče.

V dnešní lekci si představíme a implementujeme binární vyhledávací strom. Nejprve si ovšem ukážeme jeden reálný příklad mocnin a logaritmů, abychom pochopili, jak moc nám tato datová struktura usnadní život.

Legenda o šachistovi

Existuje legenda, že šachista v daleké Asii si od vladaře za své šachové umění vyžádal pouze "malou" odměnu, tedy aby mu daroval "trochu" rýže. Vladař odpověděl: "Řekni, kolik rýže chceš". Jelikož šachista byl "velmi skromný", tak vladaři popsal následující algoritmus: "Na první políčko šachovnice mi dej jedno zrnko rýže, na druhé dvě zrnka, na třetí čtyři zrnka, na čtvrté osm zrnek, na páté šestnáct zrnek a takto až po políčko šedesát čtyři." Vladař odpověděl: "Pokud chceš tak málo, tak ať tě hned vyplatí". Za chvíli jeho správci z hrůzou přiběhli, že tolik rýže není v celé zemi. Asi tušíte, co se stalo.

Jde o to, že počet zrnek rýže je přesně 2⁶⁴ - 1 = 18 446 744 073 709 551 615. Tolik rýže mu nepřinesou na naší planetě ani za sto let.

S výpočtem tohoto čísla mají problémy i naše současné počítače, respektive kompilátory jazyka C, ale i jiných jazyků. Microsoft například podporuje pouze číslo unsigned long v 64bitové podobě, což nám nestačí. V jazyce jako Haskel to samozřejmě zvládneme. A pokud výsledek vyjádříme jako reálné číslo (double), které je 1.8446744073709552 * 10¹⁹, tak samozřejmě i v C.

Ale proč jsme si uvedli tento příklad v lekci o binárních stromech? Pokud umíme na 64 kroků dosáhnout tak absurdně vysoké mocniny, tak i zpětně se dá logaritmicky dostat maximálně po 64 krocích k nějaké položce, kterou hledáme v extrémně dlouhém seznamu. Na to nám pomáhá binární strom.

Binární strom

Jeho struktura je v podstatě velmi jednoduchá:

...konec náhledu článku...
Pokračuj dál