Sleator-Tarjanovy stromy

Popis Sleator-Tarjanovych stromu, neboli "A Data Structure for Dynamic Trees" ze stejnojmenneho clanku http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/dynamic-trees.pdf

Zapoctak ma byt pochopitelny studentovi MFF v druhem rocniku. Ma obsahovat popis struktury, jake operace to umi, jak se ty operace provadeji, a analyza jejich slozitosti.

Krome samotne struktury bude zapoctak obsahovat jeste nekolik aplikaci:

  1. dynamicka inkrementalni minimalni kostra (do grafu mi pribyvaji hrany a ja po kazde pridane hrane musim rict, jaka je delka minimalni kostry a jak se odminula zmenila (nekdy dojde k pridani a nekdy i k odebrani hrany)
  2. hledani blokujiciho toku v case O(m log n)
Samotna struktura pouziva splay-stromy. Ty je potreba popsat, ale nic o nich neni potreba dokazovat.

Zpět