Příklady 20. 10. 2021: Splay Stromy

Př. 1: Potenciál

Ujistěte se, že chápete, jak je definovaný potenciál ve splay stromech a že rozumíte hlavním myšlenkám analýzy amortizované složitosti splaye.
  1. Jak je definován potenciál splay stromu?
  2. Jaká je amortizovaná cena rotace (dvojité a jednoduché)?
  3. Jaká je amortizovaná cena celého splaye?
  4. Jaká je reálná cena celého splaye?

    5. Z přednášky víme, že potenciál je vždy mezi 0 a \( n\log n\). (A pokud ne, tak to budiž snadným cvičením :-))
  5. Jaký je potenciál perfektně vyváženého stromu? Pro jednoduchost předpokládejte \(n = 2^k - 1\) a do velikosti podstromu nepočítejte jeho kořen. Počítejte potenciál po vrstvách od listů.
  6. Jaký je potenciál cesty?
  7. Zkuste najít co nejlepší dolní odhad na velikost potenciálu.

Př. 2: Insert a delete

Na přednášce jsme viděli insert a delete implementovaný pomocí "klasického" insertu a deletu v BST a vysplayování nejhlubšího vrcholu, kterého jsme se dotkli.
Insert a delete lze ale naimplementovat tak, že nejdřív provedeme splay a potom vhodně rozpojíme a spojíme stromy v kořeni.
Navrhněte insert a delete tímto způsobem a anlyzujte jejich složitost.

Př. 3: Naivní splay

Správné splay stromy používají při splayi dvojrotace, je-li to možné. Co by se stalo, kdybychom naimplementovali splay naivně, pouze pomocí jednoduchých rotací?
  1. Zanořte se do analýzy správného splaye. Jaká by byla amortizovaná cena naivního splaye?
  2. Navrhněte posloupnost operací, která vytvoří splay strom s lineární hloubkou a to jak pro naivní splay tak pro správný splay. Hint: Stačí jen inserty. Při vhodném pořadí prvků lze i správná splay donutit, aby prováděl jen jednoduché rotace.
  3. S použitím stromu z předchozí úlohy sestrojte posloupnost \(k\) operací (pro libovolné \(k\)), která má v naivním splay stromě celkovou složitost \( \Omega(kn)\). Co se stane, když tutéž posloupnost operací pustíme na správném splay stromu?