TIN066 Splay stromy

Z ωικι.matfyz.cz
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]