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:
- 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)
- 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