{{TIN066 Skripta}}
= Stromy =
Chceme zachovávat uspořádání, mít nějaké garance přístupu. Zaveďme si navíc operace MIN, MAX, ORD (k-tý prvek), SPLIT (rozřízne na prvku), JOIN (jen tak nebo s dalším prvkem).
{{TODO|rozepsat}}
== (a,b) stromy ==
(a, b)-strom je jakási zvláštní struktura, která není nikde přehledně zdokumentovaná.
Definice: Pro <math>1 \leq a < b</math> strom T nazveme (a,b)-stromem, pokud:
* Uzel (kromě kořene a listů) má aspoň ''a'' a nejvýše ''b'' potomenků.
* Všechny cesty kořen - list jsou stejně dlouhé.
Toto je jen definice topologie a v praxi je vhodnější '''speciální definice''':
Definice: Pro <math>2 \leq a, 2a-1 \leq b</math> strom T nazveme (a,b)-stromem, pokud:
* Uzel (kromě kořene a listů) má aspoň ''a'' a nejvýše ''b'' potomenků.
* Všechny cesty kořen - list jsou stejně dlouhé.
* Kořen je buď list, nebo má 2 až b synů.
Odhad počtu listů: strom výšky ''h'' má aspoň <math>2 a^{h-1}</math> a nejvýše <math>b^h</math> listů.
Tvrzení: Pro každé a, b, n existuje (a,b)-strom s ''n'' listy.
Tvrzení: Pro (a,b)-strom s ''n'' listy je jeho výška aspoň <math>log_b n</math> a nejvýše <math>1 + log_a \frac{n}{2}</math>, výška je tedy O(log n).
Strom můžeme dělit na hladiny. Na uzlech hladiny si můžeme zavést "přirozené" lexikografické uspořádání (stále nemáme žádná čísla, jen uspořádáme uzly "zleva doprava").
Mějme lineárně uspořádané U, <math>S \subseteq U</math>. Řekneme, že strom T reprezentuje S, pokud existuje isomorfismus mezi S a listy T (= bijekce slučitelná s uspořádáními).
===Reprezentace===
U listů evidujeme pouze hodnotu z S. U vnitřích uzlů evidujeme tyto položky:
* <math>\rho(v)</math> - počet synů ''v''
* <math>S_v(i) ; i = 1..\rho(v)</math> - pole ukazatelů na Syny
* <math>H_v(i) ; i = 1..\rho(v)-1</math> - pole Hodnot z U takové, že i-tá hodnota je maximum z listů podstromu i-tého syna
Všimněme si, že pro každé <math>s \in S</math> (kromě největšího) existuje vnitřní uzel ''v'' a index ''i'' takový, že <math>H_v(i) = s</math>. Toho lze využít při implementaci stromu bez listů, čímž ušetříme místo, avšak musíme uložit někde vedle maximum z S.
===Operace===
'''Vyhledej x''' : klasicky procházíme strom od kořene, podle H(i) volíme podstromy, než se dostaneme do listu. Vrátíme list.
'''MEMBER x''' : Vyhledej(x), pokud je v listu hodnota x, vrátíme TRUE, jinak FALSE.
'''MIN, MAX''' : od kořene klasicky "jedeme doleva" nebo "jedeme doprava"
Amortizované odhady.
Hladinově propojené stromy s prstem.
== A-sort ==
{{Stub}}
