TIN066 Splay stromy

Z ωικι.matfyz.cz
Verze z 27. 10. 2014, 14:47, kterou vytvořil 195.113.16.10 (diskuse)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání

Operace[editovat | editovat zdroj]

Insert Find a Delete jsou klasické, ale po provedení je vždy následuje operace Splay, která přesune prvek do kořene stromu pomocí rotací. Konkrétní rotace viz. wikipedie

Důkaz složitosti[editovat | editovat zdroj]

Dokazuje se amortizovaná složitos Splay - důkaz na přednášce velmi blízce kopíroval originální důkaz v článku autorů stromu Sleatora a Tarjana.

Reference[editovat | editovat zdroj]