Cvičení 3. 11. 2021: (a,b)-stromy znovu, lépe a radostněji!
Př. 1: (2,4)-stromy vs červeno-černé stromy
Červeno-černé stromy jsou BST vyvažované udržováním následujících invariantů:
- Každý vrchol je buď černý nebo červený
- Kořen a null pointery jsou černé
- Červený vrchol smí mít pouze černého rodiče.
- Všechny cesty z kořene do listu obsahují stejný počet černých vrcholů.
Může být užitečné spíš uvažovat barevné hrany: Barva hrany je barva jejího spodního
konce. Tj. hrana do rodiče z červeného kořene je červená, z černého černá.
-
Ukažte, že každý (2,4)-strom je vlastně červeno-černým stromem. To jest, navrhněte
jednoduchoučké zobrazení, které libovolný validní (2,4)-strom zobrazí na ekvivalentní
červeno-černý strom. Máte-li rádi algebru, plusmínus hledáme homomorfismus z
(2,4)-stromů do červenočerných stromů s operacemi insert a delete.
Hint: Zkuste reprezentovat vrchol (2,4)-stromu jako červeno-černý strom.
- A co naopak?
- Dá se z obou předchozích zobrazení získat isomorfismus, tj. že červeno-černé a
(2,4)-stromy jsou jen rozdílné reprezentace téhož? A pokud ne, pomohlo by přidání
nějakých dalších omezení k některým ze stromů, aby to už šlo?
Př. 2: Amortizované (a, 2a-1)-stromy
Na přednášce jsme viděli, že libovolná posloupnost \(m\) insertů and deletů ve (a,
2a)-stromě celkem změní (split/merge) jen \( \mathcal{O}(m)\) vrcholů (začínaje s
prázdným stromem).
Ukažte, že toto neplatí pro (a, 2a-1)-stromy. To jest, pro libovolné \(n\) a
\(m\) navrhněte posloupnost \(m\) operací na stromě s \(\Theta(n)\) vrcholy, která
celkem změní \(\Omega(m\log(n))\) vrcholů.
Začněte s (2,3)-stromy, a potom zobecněte vaši konstrukci pro libovolné \(a\).
Můžete začít s libovolným (validním) \(n\) vrcholovým stromem a až úplně na konci
ukažte, že opravdu může vzniknout z prázdného stromu.
Př. 3: Split a join
- Navrhněte join operaci pro (a,b)-stromy. To jest, máte dva stromy \(T_1, T_2\),
přičemž vše v \(T_1\) je menší než cokoliv v \(T_2\), a cílem je spojit \(T_1\) a
\(T_2\) do jednoho stromu. Pozor, strom můžou být různě vysoké. Pro další příklad se
vám bude hodit udělat přesnější analýzu složitosti než jen \(\mathcal{O}(\log n)\).
Hint: Začněte tím, že si pořídíte klíč, které stromy odděluje. A pak už je to jen
vlastně insert.
-
Navrhněte operaci split, která je inverzní k join. To jest, máte strom \(T\) a klíč
\(k\) a chcete \(T\) rozdělit na dva stromy tak, že v jednom je vše měnší než \(k\) a
ve druhém zbytek.
Hint: Nejdřív rozdělte \(T\) na hromadu stromů a pak použijte join.