Podcast na Binární vyhledávací strom

Kapitoly

Mýtus o vyhledávání

Co je binární vyhledávací strom?

Stavíme si vlastní strom

Hledání a mazání

Pozor na chyby

Mazání uzlu se dvěma potomky

Proč záleží na výšce

Jak projít stromem

Shrnutí a rozloučení

Přepis

Kristýna: Většina lidí si myslí, že když chcete najít jednu konkrétní informaci v milionu záznamů, musíte v průměru projít polovinu z nich. Zní to logicky, že?

Matěj: Přesně tak. Ale co kdybych ti řekl, že se správnou organizací dat můžeš najít jednu položku z milionu v pouhých dvaceti krocích?

Kristýna: Dvacet kroků? Z milionu? To zní jako nějaké kouzlo. Jak je to možné?

Matěj: Není to kouzlo, ale geniální datová struktura. A právě o ní si dnes budeme povídat. Posloucháte Studyfi Podcast.

Kristýna: Dobře, Matěji, tak odhal to tajemství. Co je ta zázračná struktura, která tohle dokáže?

Matěj: Jmenuje se binární vyhledávací strom, nebo zkráceně BST. Představ si ho jako takový super organizovaný rodokmen, ale místo rodinných vztahů třídíme čísla nebo data.

Kristýna: Rodokmen s čísly? Dobře, to si umím představit. Jak to funguje?

Matěj: Má to jedno jednoduché, ale naprosto klíčové pravidlo. Pro každý uzel, tedy pro každý prvek ve stromu, platí, že všechno v jeho levém podstromu je menší a všechno v jeho pravém podstromu je větší.

Kristýna: Aha! Takže když stojím na nějakém čísle, vím, že všechna menší čísla najdu nalevo a všechna větší napravo. To je chytré.

Matěj: Přesně tak. A tenhle jednoduchý princip dělá vyhledávání neuvěřitelně efektivní. Pojďme si to ukázat na příkladu. Postavíme si takový strom krok za krokem.

Kristýna: Super, jdeme na to! Řekněme, že máme čísla 40, 20, 60, 10 a 30. Jak je poskládáme do stromu?

Matěj: Skvělá sada. Začneme s prvním číslem, 40. To bude náš kořen, úplný vrchol stromu. Teď přijde 20. Je 20 menší, nebo větší než 40?

Kristýna: Menší.

Matěj: Správně. Takže 20 půjde doleva a stane se levým potomkem čtyřicítky. Teď 60. Ta je větší než 40, takže půjde…?

Kristýna: Doprava! Stane se pravým potomkem.

Matěj: Přesně! Už to chápeš. Pokračujeme s desítkou. Začínáme zase od kořene, od 40. 10 je menší, jdeme doleva k 20. 10 je menší i než 20, takže jdeme zase doleva. A tam už nic není, takže 10 se stane levým potomkem dvacítky.

Kristýna: A co poslední číslo, 30? Předpokládám, že postup je stejný. Menší než 40, takže doleva. Větší než 20, takže doprava... a tam už je volno. Takže 30 bude pravý potomek dvacítky.

Matěj: Perfektní! Máme postavený základní strom. Vidíš, jak každé rozhodnutí je jen jednoduché porovnání?

Kristýna: Vidím. Takže teď, když chci v tomhle našem stromě najít třeba tu třicítku, tak prostě sleduju tu stejnou cestu. Menší než 40, větší než 20... a jsem tam. To je bleskové!

Matěj: Přesně tak. To je ta síla BST. Ale teď přichází ta nejtěžší část, kterou studenti často pletou: mazání. Mazání je trochu záludnější, protože musíme zachovat to naše zlaté pravidlo.

Kristýna: Co je na tom tak složitého? Prostě uzel vyhodím, ne?

Matěj: Kéž by to bylo tak snadné. Pokud mažeš list, tedy uzel bez potomků, tak ano. Ale co když chceš smazat uzel, který má dva potomky? Třeba naši dvacítku, která má vlevo desítku a vpravo třicítku?

Kristýna: Hmm, dobrá otázka. Když ji smažu, co se stane s těmi jejími potomky? Nemůžu je nechat jen tak viset ve vzduchu.

Matěj: Přesně. Tady je trik. Najdeme v jeho pravém podstromu ten nejmenší prvek. V případě dvacítky je její pravý podstrom třicítka. A protože třicítka nemá nic vlevo, je sama tím nejmenším prvkem.

Kristýna: Dobře, máme třicítku. A co s ní?

Matěj: Hodnotu toho uzlu, co chceme smazat, tedy 20, přepíšeme na 30. A pak smažeme tu původní třicítku z jejího místa. Tím se celá struktura zachová a pravidlo stále platí.

Kristýna: Páni, to je chytrý trik. Takže vlastně ten uzel „převlékneme“ za jeho nejbližšího většího následovníka a toho následovníka pak smažeme. Zní to složitě, ale dává to smysl.

Matěj: Přesně tak. Je to klíčový koncept, který se u zkoušek často objevuje, protože testuje hluboké pochopení.

Kristýna: Jaké jsou tedy nejčastější chyby, které studenti dělají kromě tohohle mazání?

Matěj: Velmi často zapomenou, že výkon stromu závisí na jeho tvaru. Pokud vkládáš čísla seřazeně, třeba 10, 20, 30, 40, nevytvoříš hezký košatý strom, ale takovou degenerovanou „žížalu“ – vlastně jen spojený seznam. A pak je vyhledávání stejně pomalé jako procházení pole prvek po prvku.

Kristýna: Žížala. To si budu pamatovat. Takže pořadí, v jakém vkládáme data, je kritické?

Matěj: Ano. Proto existují pokročilejší, takzvané samovyvažovací stromy, které si tenhle tvar hlídají samy. Ale to už je téma na příště. Pro začátek je nejdůležitější pochopit základní princip a operace BST.

Kristýna: Super. Takže klíčový poznatek je, že binární vyhledávací strom organizuje data na základě jednoduchého pravidla „menší vlevo, větší vpravo“, což umožňuje bleskové vyhledávání. A při mazání uzlu se dvěma potomky musíme být opatrní a použít fintu s následovníkem.

Matěj: Vystihla jsi to naprosto přesně.

Kristýna: ...a to zní docela přímočaře. Ale co se stane, když ten uzel, který chceme smazat, má potomky na obě strany? To mi přijde jako recept na katastrofu.

Matěj: Jo, to je ten nejsložitější případ. Ale není to katastrofa, jen je to trochu... mazanější. Ten uzel nemůžeme jen tak vyhodit, protože by se nám celá struktura rozpadla.

Kristýna: Takže co s tím? Najdeme mu náhradníka?

Matěj: Přesně tak! Hledáme náhradní uzel, který zachová to naše pravidlo "vlevo menší, vpravo větší". Nejčastěji se používá takzvaný "inorder následník".

Kristýna: Inorder následník? To zní hrozně chytře. Co to je?

Matěj: Je to prostě nejmenší prvek v pravém podstromu. Představ si, že mažeme kořen s hodnotou 50. Jeho pravý podstrom začíná třeba uzlem 70. My teď v tomhle pravém podstromu najdeme nejmenší hodnotu. Řekněme, že je to 60.

Kristýna: Aha, takže 60 je ten náš náhradník.

Matěj: Přesně. A teď to kouzlo... Zkopírujeme hodnotu 60 do toho původního uzlu 50. Takže náš kořen má teď hodnotu 60. A pak už jen smažeme tu původní šedesátku z jejího místa.

Kristýna: A to už je jednoduché, protože ta šedesátka buď neměla žádné potomky, nebo jen jednoho. To už umíme z minula. Chápu. Problém jsme vlastně jen přesunuli na jednodušší případ.

Matěj: Přesně tak. A když už jsme u rychlosti, rychlost operací závisí na jedné klíčové věci – a to je výška stromu. Výška je prostě nejdelší cesta od kořene k nějakému listu.

Kristýna: Takže chceme co nejnižší strom, je to tak?

Matěj: Přesně. V ideálním, dokonale vyváženém stromě s milionem prvků je výška jen kolem dvaceti. To je neuvěřitelně rychlé. Ale je tu háček...

Kristýna: Vždycky je nějaký háček.

Matěj: Pokud vkládáš prvky seřazeně, třeba 1, 2, 3, 4, 5... strom se zdeformuje do jedné dlouhé nudle. Je to jako mít v knihovně jednu polici dlouhou kilometr. Hledání pak trvá věčnost.

Kristýna: Takže se z toho stane vlastně obyčejný seznam. Co s tím?

Matěj: Na to existují chytřejší verze stromů, takzvané vyvážené stromy. Třeba AVL stromy nebo červeno-černé stromy. Ty si po každém vložení nebo smazání samy trochu "uklidí", aby zůstaly nízké a efektivní.

Kristýna: Dobře, to dává smysl. A co když chci vypsat všechny hodnoty, které ve stromě jsou? Jak ho vlastně celý "přečtu"?

Matěj: To je skvělá otázka, která nás přivádí k průchodům stromem. Jsou tři základní způsoby: Inorder, Preorder a Postorder. Každý má jiný účel.

Kristýna: Povídej, jsem zvědavá.

Matěj: Průchod Inorder – tedy levý podstrom, kořen, pravý podstrom – ti u binárního vyhledávacího stromu vždycky vrátí prvky krásně seřazené od nejmenšího po největší. Bez extra práce.

Kristýna: Počkat, vážně? Takže je to datová struktura a třídicí algoritmus v jednom?

Matěj: V podstatě ano! Preorder se zase hodí na kopírování stromů a Postorder je skvělý pro bezpečné mazání celého stromu, protože začíná od listů.

Kristýna: To je fascinující. Takže abychom to shrnuli, Matěji. Binární vyhledávací stromy jsou super efektivní pro organizaci dat, pokud si dáme pozor, aby se nám nezdeformovaly do dlouhé nudle.

Matěj: Přesně tak. Je to o hierarchii a vyváženosti. Nabízejí skvělou rychlost pro hledání, vkládání i mazání, a díky průchodům s nimi můžeme dělat další chytré operace.

Kristýna: Skvělé. Tím jsme na konci dnešního dílu i celé naší minisérie o datových strukturách. Matěji, moc ti děkuju, že jsi nám to všechno tak srozumitelně vysvětlil.

Matěj: Já děkuju za pozvání, Kristýno. Bylo to super. A doufám, že jsme posluchačům ukázali, že programování a algoritmy nejsou žádná magie.

Kristýna: Určitě ano. A vám, milí posluchači, děkujeme, že jste byli s námi. Doufáme, že se vám to líbilo a že se s námi budete učit i příště. Za mikrofonem se loučí Kristýna a Matěj. Mějte se krásně a studiu zdar!

Matěj: Na shledanou!