Příklady 13. 10. 2021

Př. 0: Splay your way to the top!

Na následujícím splay stromu odsimulujte operace:
  1. Splay(14)
  2. Splay(6)
  3. Insert(11)
  4. Delete(6)
  5. Delete(10)
  6. Delete(4)
Zde si představte splay strom

Př. 1: Binární počítadlo

Analyzujte složitost binárního počítadla. Binární počítadlo se skládá z jednoho binárního čísla (s potenciálně libovolným počtem cifer) a umí jedinou operaci "přičti jedničku". Počítadlo začíná nastavené na nulu (všechny cifry jsou nastaveny na nulu) a složitost počítáme jako počet operací "přečti cifru" a "změň cifru".
Jakou celkovou složitost bude mít \(n\) operací na počítadle, začínaje s vynulovaným počítadlem? A co kdybychom chtěli podporovat i operaci "odečti jedničku"? Dalo by se počítadlo upravit tak, aby složitost zůstala stejná?

Př. 2: Následník v BST

V domácím úkolu jste měli za úkol naimplementovat funkci následníka v obecném nevyvažovaném binárním vyhledávacím stromě. Jakou má tato operace worst-case složitost? Dokažte, projití všech prvků stromu od minima k maximu pomocí volání následníka trvá \( \mathcal{O}(n) \).

Př. 3: Líně vyvažované stromy

Na přednášce jste viděli binární vyhledávací stromy vyvažované líně pomocí lokálního přestavování. Analyzujte detaily přestavby a navrhněte implementaci operace delete.
  1. Ukažte, že libovolný BST lze přestavět na perfektně vyvážený v lineárním čase. Pro labužníky: Ukažte, že to jde jen s konstantním prostorem navíc.
  2. Potenciál v amortizované analýze byl definován skrz součet potenciálu vrcholů a potenciál vrcholu \( r(v) \) je buď \( |s(L_v) - s(R_v)| \), nebo nula, pokud je předchozí rozdíl přesně jedna. Co by se rozbilo, kdybychom pro rozdíl jedna prostě nastavili potenciál na jedničku?
  3. Přidejte delete tak, jak funguje v obyčejném BST spolu s vhodným lokálním přestavením a analyzujte složitost.
  4. Přidejte delete pomocí pomníčků a globálního přestavby. Tj., mazané vrcholy necháme ve stromě, ale označíme je jako smazané (pomníček). Je-li pomníčků ve stromě moc, celý strom přestavíme a přitom pomníčky zlikvidujeme. Doplňte detaily (kolik je "moc" atp.) a konstrukci analyzujte.