Tahle otázka je docela brutálně dlouhá. Stromy jsou ale strašně důležité datové struktury, takže je to tak v pořádku; jediná škoda je, že jsme jim nemohli na hodině věnovat víc času. Nic ze zmíněného nemusíte umět naprogramovat; bylo by ale dobré umět nakreslit, o co jde.
Binární strom je graf, který je strom (tedy neobsahuje kružnice), u kterého máme jeden vrchol označený jakožto kořen, a jehož každý vrchol má nejvýše dva syny. Už jsme se s takovými stromy setkali v souvislosti s haldou; halda je ale úplný binární strom (má všechny horní vrstvy plné, jak to jde), takže jsme ji mohli pohodlně uložit do pole. Obecný binární strom může vypadat o hodně jinak, takže si jeho strukturu potřebujeme pamatovat podrobně.
Nejpohodlnější je použít k tomu objetově orientované programování: zavedeme si třídu Strom a třídu Vrchol. Každý Vrchol nese jednu hodnotu (dejme tomu, celé číslo) a dvě vlastnosti – odkazy na svého levého a svého pravého syna. Ty musíme rozlišovat; chybějící syny nastavíme jako nil. Někdy se navíc hodí, aby si vrchol pamatoval svého otce, ale v našem případě by to bylo jen plýtvání pamětí. V Ruby by tedy dotyčná třída vypadala třeba takhle:
class Vrchol
attr_accessor :levy_syn, :pravy_syn
attr_reader :hodnota, :otec
def initialize(hodnota)
@hodnota = hodnota
@levy_syn = @pravy_syn = nil
end
end
Strom si bude předvším pamatovat jeden kořenový Vrchol a krom toho bude mít různé metody pro přidávání, hledání a mazání prvků.
Přidání prvku do obecného binárního stromu je trochu stupidní úloha, protože můžeme nový vrchol pověsit úplně kamkoliv. Možné řešení je tedy začít v kořeni a z aktuálního vrcholu postupovat vždy na levého syna, dokud to není nil. Až ten nil najdeme, nastavíme místo něj nový vrchol. Všimněte si, že strom, který takhle vznikne, bude zároveň cesta.
Binární vyhledávací strom má vrcholy seřazené zleva doprava podle hodnoty. Podrobněji platí, že @levy_syn < @hodnota < @pravy_syn (žádné dvě hodnoty tedy nesmí být stejné). Když máme zadanou hodnotu a chceme najít k ní příslušný vrchol, nemusíme díky tomu procházet strom celý; můžeme jít přímo po cestě z kořene do hledaného vrcholu, vždy víme, kam pokračovat.
Vyhledávací stromy můžou umět spoustu operací – přidávání a odebírání prvků, hledání nejbližšího souseda, hledání nejmenšího prvku, vyříznutí stromu s prvky v zadaném rozsahu. Všechny operace mívají složitost O(hloubka stromu), což opravdu může být O(log(N)) podle počtu prvků ve stromu. Složité ale je zajistit, aby se ani po přidávání a odebírání vrcholů strom nezkazil a jeho hloubka nepřerostla rozumné meze (například aby se ze stromu nestala cesta). Je na to spousta algoritmů, ale žádný není zvlášť hezký a naštěstí se na ně tahle maturitní otázka neptá.
Nový vrchol do vyhledávacího stromu budeme přidávat nejlépe jako list; potom má jednoznačně určené místo. Jako minule, začneme v kořeni, ale pokračujeme vždy na toho syna, kam spadá přidávaná hodnota (tedy pravého, pokud novy_vrchol.hodnota > @hodnota). Zapsáno v Ruby:
class Strom
attr_accessor :koren
def initialize
@koren = nil
end
def pridej(hodnota)
novy = Vrchol.new(hodnota)
if @koren.nil?
@koren = novy
else
aktualni = @koren
while true
nasledujici = (hodnota < aktualni.hodnota) ? aktualni.levy_syn : aktualni.pravy_syn
if nasledujici.nil?
if hodnota < aktualni.hodnota
aktualni.levy_syn = novy
else
aktualni.pravy_syn = novy
end
break
end
aktualni = nasledujici
end
end
end
end
Odebrání vrcholu je jednoduché jenom v případě, kdy je odebíraný vrchol list stromu (tj. nemá žádné syny); pak stačí najít jeho otce a odkaz na odebíraný vrchol nastavit jako nil. Když má vrchol jen jednoho syna, můžeme ho vytrhnout a syna převěsit výš (jako ve spojovém seznamu). Potíž je, když má vrchol syny oba. Pomůže podobná finta jako u haldy: vybereme si nějaký vrchol s nejvýše jedním synem a s odebíraným vrcholem je prohodíme (ale celý zbytek stromu necháme na místě). Pak už ho můžeme smazat snadno.
S jakým vrcholem ho vyměnit? Potřebujeme, aby po dokončení celé akce nebylo porušené pravidlo vyhledávacího stromu. Nabízejí se tedy jen dva: buďto největší z levého podstromu, nebo nejmenší z pravého (jsou to sousedi odebíraného vrcholu, když celý strom seřadíme). Když libovolný z těchto dvou vrcholů dáme na místo toho odebíraného, bude pořád platit, že jeho hodnota je větší než levvý podstrom a menší než pravý. Největší prvek z levého podstromu získáme jedním krokem na levého syna a pak pořád doprava, než narazíme na nil; nejmenší z pravého zrcadlově. Kód je v souhrnném zdrojáku o vyhledávacích stromech, ale je strašně dlouhý.
Dokonale vyvážený strom v každém vrcholu splňuje, že počet prvků v levém podstromu (tj. levý syn a všechno pod ním) se liší nejvýš o 1 od počtu prvků v pravém podstromu. Prvek tedy přidáme opět nejlíp jako list. Postupujeme vlastně stejně jako u vyhledávacího stromu, ale jdeme směrem lehčí větve (syna s menším podstromem). Jakmile je některý ze synů nil, nalepíme za něj nový vrchol.
Nesmíme zapomenout, že se některým vrcholům zvětšil počet prvků v podstromu. Ve skutečnosti ale stačí přičíst jedničku každému vrcholu, kterým jsme cestou prošli.
Tuhle podotázku jsem na poslední chvíli smazal.
Otázka na přidávání vrcholů tady už je. Odebírání vrcholu z vyváženého binárního stromu dá hodně práce a samo o sobě není k ničemu užitečné.
Dívat se na aritmetický výraz jako na strom je hodně užitečné pro přehlednost, zvlášť kdybychom chtěli výraz vyhodnocovat. Listy stromu jsou čísla, vnitřní vrcholy jsou operace. Dokud budeme používat jen binární operace, vystačíme si s binárním stromem. Vezměme si třeba výraz 1/(2*3+5/4):
Metoda průchodu stromem je způsob, jak se postupně podívat na všechny jeho prvky. Jedna ze dvou nejobvyklejších je průchod do hloubky (depth-first), kdy prostě cestujeme z kořene vždy nejdřív do levého syna, pak do pravého a vracíme se až ve chvíli, když jsme oba syny navštívili. Prvky předchozího stromu při průchodu do hloubky navštívíme v tomto pořadí: /1+*23/54.
My lidé obvykle zapisujeme výrazy tak, jako bychom procházeli strom zleva doprava. To je skoro průchod do hloubky; vrchol ale nevypisujeme hned, ale až ve chvíli, kdy se do něj vrátíme z levého syna. Dávalo by to pořadí 1/2*3+5/4. Bohužel z toho není jednoznačně jasné, jak strom pro takový výraz vlastně vypadá. Abychom si správně domysleli, jak strom vypadá, musíme si vypomáhat závorkama.
Třetí podobná možnost procházení do hloubky je, že vrchol vypisujeme až po návratu z pravého syna, takže vlastně úplně nakonec. To je pro vyhodnocování výrazů náramně užitečné. Stačí výsledný řetězec číst zleva doprava, čísla házet na zásobník a když narazíme na početní operaci, vzít ze zásobníku dvě čísla a hodit tam výsledek (jen pozor na pořadí: jako první ze zásobníku vypadne pravý operand, tedy např. dělitel). Světe div se: když skončíme, je na zásobníku výsledek výrazu. V našem případě to dává řetězec 123*54/+/.
| Čtený znak | Vkládáme | Obsah zásobníku |
| 1 | 1 | ||
| 2 | 2 | 1 | |
| 3 | 3 | 2;1 | |
| * | 2*3=6 | ||
| 5 | 5 | 6;1 | |
| 4 | 4 | 5;6;1 | |
| / | 5/4=1,25 | ||
| + | 6+1,25=7,25 | 1 | |
| / | 1/7,25=0,138... |
Často je užitečnější průchod do šířky (breadth-first), což je prostě čtení po řádcích. Zrovna v souvislosti s aritmetickými výrazy se nepoužívá (ačkoliv by to asi taky šlo); dával by řetězec /1+*/2354.
Na zmíněných metodách průchodu stromem je hezké, že jejich kód vypadá skoro stejně. To je dobré i z didaktického hlediska jako ukázka toho, jak velké změny v programu může udělat jediný detail.
Začneme průchodem do hloubky, který naprogramujeme docela přímočaře: skáčeme z vrcholu na jeho sousedy a v Hashi si pamatujeme, které jsme už navštívili. Jediná potíž je v tom, že vrchol si svého otce nepamatuje. Můžeme si ale zavést zásobník a udržovat v něm celou cestu z kořene, otec potom bude vždycky navrchu. Zapsáno v Ruby:
def pruchod_do_hloubky(strom, funkce=:puts)
navstivene = Hash.new
zasobnik = [strom.koren]
while not (v = zasobnik[-1]).nil?
if not navstivene.include? v
navstivene[v] = true
self.send(funkce, v.hodnota)
end
if not v.levy_syn.nil? and not navstivene.include? v.levy_syn:
zasobnik.push(v.levy_syn)
elsif not v.pravy_syn.nil? and not navstivene.include? v.pravy_syn:
zasobnik.push(v.pravy_syn)
else
zasobnik.pop
end
end
end
K průchodu do šířky stačí v předchozím kódu nahradit zásobník frontou (v Ruby tj. odebírat ze začátku pole) a zakomentovat všechny podmínky. Rozmyslete si sami, jaktože to funguje:
def pruchod_do_sirky(strom, funkce=:puts)
navstivene = Hash.new
zasobnik = [strom.koren]
while not (v = zasobnik[0]).nil?
#if not navstivene.include? v
navstivene[v] = true
self.send(funkce, v.hodnota)
#end
#if not v.levy_syn.nil? and not navstivene.include? v.levy_syn:
zasobnik.push(v.levy_syn)
#elsif not v.pravy_syn.nil? and not navstivene.include? v.pravy_syn:
zasobnik.push(v.pravy_syn)
#else
zasobnik.shift
#end
end
end
Průchod zleva doprava je v podstatě úplně stejný jako průchod do hloubky, ale vrchol oficiálně navštívíme až poté, co jsme prošli jeho levého syna. Stačí přehodit pár řádků a elsif rozepsat na else if:
def pruchod_zleva_doprava(strom, funkce=:puts)
navstivene = Hash.new
zasobnik = [strom.koren]
while not (v = zasobnik[-1]).nil?
if not v.levy_syn.nil? and not navstivene.include? v.levy_syn:
zasobnik.push(v.levy_syn)
else
if not navstivene.include? v
navstivene[v] = true
self.send(funkce, v.hodnota)
end
if not v.pravy_syn.nil? and not navstivene.include? v.pravy_syn:
zasobnik.push(v.pravy_syn)
else
zasobnik.pop
end
end
end
end