Tento týden až 80% sleva na e-learning týkající se jazyka C
50 % bodů zdarma na online výuku díky naší Slevové akci!

Lekce 13 - 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ě 264 - 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 * 1019, 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...

Prémiový článek

Prémiový článek

Na itnetwork.cz se nachází největší a nejucelenější česká databáze s výukovými články, jejímž cílem je umožnit kvalitní vzdělání v oblasti IT úplně každému. Měsíčně zobrazíme k milionu článků a sklidíme desítky děkovných emailů, kde nám sdělujete, že jsme vám pomohli k lepšímu zaměstnání nebo vzdělání.

Ačkoli se snažíme držet většinu obsahu úplně zadarmo, udržovat síť v provozu a aktuální stojí obrovské úsilí. Proto je nějaký obsah, jako cvičení nebo odbornější články, přístupný pouze za body. Nebojte, nestojí to skoro nic :)

Popis článku

Požadovaný článek má následující obsah:

C tutoriál o vytváření binárních stromů a přecházení přes binární stromy. Ukážeme si, proč jsou binární stromy velmi výkonné.

Omezená nabídka: Nauč se vše a ušetři

Koupit články a funkce postupně a po jednom 130 bodů
Koupit všechny aktuálně dostupné články v sekci se všemi funkcemi za exkluzivní cenu 104 bodů
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 15 článkům s kontrolou a certifikací a ještě navíc ušetříš 65 Kč. Nabídka je časově omezená a platí pro všechny články v kurzu. Nakup teď a získej limitovanou 20% slevu.
104 bodů získáš za přidání svého článku na síť nebo odpovídá 325 Kč 260 Kč
Pro přístup k článku potřebuješ 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Koupí článku k němu získáš neomezený přístup a to napořád. Posuneš své znalosti zas kousek dopředu a zároveň nám pomůžeš udržovat celý projekt při životě a pomáhat vám tak k lepší budoucnosti.

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Body získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.

Dobít body můžeš okamžitě např.:

Kartou SMS Převodem
Kartou SMS Převodem
Článek pro vás napsal Daniel Martinko
Avatar
Aktivity (3)