TIN066 Splay stromy

Wiki-skripta pro Datové struktury I
Obsah
Základní metody hashování Univerzální a perfektní hashování (a,b) stromy Binární vyhledávací stromy AVL stromy Červeno-černé stromy Splay stromy Vyhledávání v setříděné posloupnosti Vyhledávání k-tého nejmenšího Základní haldy Binomické a Fibonacciho haldy Základní metody třídění Přihrádkové třídění

Operace

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

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

• článek s důkazem složitosti i popisem algoritmu
• wikipedie