TIN066 (a,b) stromy
Definice: Pro $ 1 \leq a < b $ 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 $ 2 \leq a, 2a-1 \leq b $ strom T nazveme (a,b)-stromem, pokud:
- Uzel (kromě kořene a listů) má aspoň a a nejvýše b potomků.
- 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ň $ 2 a^{h-1} $ a nejvýše $ b^h $ 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ň $ log_b n $ a nejvýše $ 1 + log_a \frac{n}{2} $, 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, $ S \subseteq U $. Ř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:
- $ \rho(v) $ - počet synů v
- $ S_v(i) ; i = 1..\rho(v) $ - pole ukazatelů na Syny
- $ H_v(i) ; i = 1..\rho(v)-1 $ - 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é $ s \in S $ (kromě největšího) existuje vnitřní uzel v a index i takový, že $ H_v(i) = s $. 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.
Algoritmy
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"
Štěpení t : zajistí, aby uzel t neměl víc, jak b synů
- pokud (t kořen) vytvoř nový kořen s jediným synem t
- vytvoř nový uzel t' a dej do něj pravou půlku synů z t
- připoj t' k otci t na správné místo
INSERT x : vloží x do stromu
- v = Vyhledej (x);
- pokud (hodnota v je x) konec (hodnota už je ve stromě)
- vyrob nový list t' s hodnotou x.
- pokud (v < x) připojím t' jako nejpravějšího potomka k otci v;
- jinak najdu index, kam t' patří, ostatní pošoupnu doprava
- dokud (otec t' má víc jak b synů) Štěpení(otec t'); t' = otec t';
Spojení t, y : spojí dva sousední vrcholy do jednoho
Přesun t, y : přesunu jednoho syna z y do jeho souseda t (rozliším, zda je y vlevo nebo vpravo, ...)
DELETE x: smaže list s hodnotou x
- t = Vyhledej (x); pokud (hodnota t není x) konec;
- vyjmi list t z otce
- dokud (otec t má méně jak a synů)
- y = strýc t;
- pokud (y má a synů) Spojení(otec t, y);
- jinak Přesun(otec t, y);
- t = otec t;
Amortizované odhady.
Hladinově propojené stromy s prstem.
A-sort
Třídící algoritmus A-sort je založený na (a,b)-stromech. Na předtříděných posloupnostech má lepší výsledky, než klasické algoritmy.
A-sort x1, x2, ... xn
- vytvoř jednoprvkový strom s uzlem t o hodnotě xn
- pro i = n-1 .. 1 A-insert(xi, t)
- projdi listy zleva do prava, vrať jejich hodnoty na výstup
A-insert x, t
- dokud (x mimo rozsah t) udělej krok k otci
- zanoř se do správného listu
- vlož nový list s x na vhodnou pozici
- zavolej Štěpení na cestě ke kořenu
- vrať nové t
A-sort vyžaduje čas $ O(n + n\log\frac{F}{n} $, F je míra setříděnosti posloupnosti.
