Drzewo splay

Ten artykuł od 2014-06 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Drzewo splay (drzewo rozchylane, drzewo Sleatora-Tarjana^[1]) – struktura danych w formie samodostosowującego się drzewa poszukiwań binarnych (BST), wynaleziona przez Daniela Sleatora i Roberta Tarjana, reprezentująca zbiór elementów z porządkiem liniowym.

Wykonywanie podstawowych operacji na drzewie splay wiąże się z wykonaniem procedury ${\displaystyle \mathrm {Splay} (T,x),}$ która powoduje taką zmianę struktury drzewa ${\displaystyle T,}$ że węzeł ${\displaystyle x}$ zostaje umieszczony w korzeniu przy zachowaniu porządku charakterystycznego dla drzewa BST.

W porównaniu do innych drzew BST, drzewa splay zmieniają swoją strukturę również podczas wyszukiwana kluczy (a nie tylko dodawania lub usuwania), przesuwając znaleziony węzeł w kierunku korzenia, dzięki temu często wyszukiwane węzły stają się szybsze do znalezienia. Z tego powodu drzewa splay bywają wykorzystywane w systemach typu cache. Drzewa splay nie są samorównoważące, ponieważ ich wysokość nie jest ograniczona przez ${\displaystyle {\mathcal {O}}(\log n)}$ – można np. tak wykonać operacje, że drzewo zdegeneruje się do listy.

Podstawowe operacje na drzewie splay, tj. wyszukiwanie elementu oraz wstawianie i usuwanie, są wykonywane w zamortyzowanym czasie ${\displaystyle {\mathcal {O}}(\log n),}$ gdzie ${\displaystyle n}$ jest liczbą elementów w drzewie^[2]. Oznacza to, że dla dowolnego ciągu ${\displaystyle m}$ operacji na drzewie splay, łączny koszt wykonania tych operacji jest rzędu ${\displaystyle {\mathcal {O}}(m\log n).}$

Operacja Splay jest procedurą kluczową dla działania drzewa typu splay. Polega ona na wykonaniu sekwencji kroków, z których każdy przybliża element ${\displaystyle x}$ do korzenia. Każdy krok polega na wykonaniu jednej lub dwóch rotacji względem krawędzi wchodzących w skład początkowej ścieżki od ${\displaystyle x}$ do korzenia.

W każdym kroku procedury ${\displaystyle \mathrm {Splay} (T,x)}$ niech ${\displaystyle p}$ oznacza ojca węzła ${\displaystyle x,}$ a jeśli ${\displaystyle p}$ nie jest korzeniem, niech ${\displaystyle g}$ oznacza z kolei jego ojca (i dziadka ${\displaystyle x}$). Wyróżniamy trzy przypadki kroków procedury Splay, w zależności od tego czy ${\displaystyle p}$ jest korzeniem i od wzajemnego położenia węzłów ${\displaystyle x,}$ ${\displaystyle p}$ i ${\displaystyle g}$^[2]:

Wykonywany kiedy ${\displaystyle p}$ jest korzeniem, polega na rotacji drzewa względem krawędzi ${\displaystyle (p,x).}$ Ten krok może być wykonany tylko jako ostatni krok procedury Splay.

Wykonywany kiedy ${\displaystyle p}$ nie jest korzeniem, a ${\displaystyle (p,x)}$ i ${\displaystyle (g,p)}$ są krawędziami w jedną stronę, tj. ${\displaystyle x}$ jest lewym synem ${\displaystyle p,}$ który jest lewym synem ${\displaystyle g,}$ albo ${\displaystyle x}$ jest prawym synem ${\displaystyle p,}$ a ${\displaystyle p}$ – prawym synem ${\displaystyle g.}$ Polega na rotacji względem krawędzi ${\displaystyle (g,p)}$ łączącej ojca i dziadka wierzchołka ${\displaystyle x,}$ a potem względem krawędzi ${\displaystyle (p,x)}$ łączącej ${\displaystyle x}$ z jego ojcem.

Wykonywany kiedy ${\displaystyle p}$ nie jest korzeniem, oraz ${\displaystyle x}$ jest lewym synem ${\displaystyle p,}$ a ${\displaystyle p}$ – prawym synem ${\displaystyle g}$ lub odwrotnie. W tym kroku najpierw wykonuje się rotację względem krawędzi ${\displaystyle (p,x),}$ a następnie względem krawędzi ${\displaystyle (g,x),}$ która powstaje w wyniku pierwszej rotacji.

W opisie implementacji operacji na drzewie splay będziemy utożsamiali wierzchołek z przechowywaną w nim wartością.

Wyszukiwanie wierzchołka zawierającego daną wartość odbywa się jak w drzewie BST, przy czym jeżeli wyszukiwanie zakończyło się powodzeniem, a szukana wartość znajduje się w węźle ${\displaystyle x,}$ to wywołujemy ${\displaystyle \mathrm {Splay} (T,x).}$ W przeciwnym wypadku wykonujemy ${\displaystyle \mathrm {Splay} (T,y),}$ gdzie ${\displaystyle y}$ jest ostatnim węzłem drzewa odwiedzonym przy wyszukiwaniu.

Aby wstawić do drzewa ${\displaystyle T}$ wartość ${\displaystyle x,}$ wyszukujemy ${\displaystyle x}$ w ${\displaystyle T}$ jak powyżej, wskutek czego w korzeniu znajduje się wartość ${\displaystyle y.}$ Jeżeli ${\displaystyle x=y,}$ to wstawienie jest zakończone, ponieważ oznacza to, że przed wstawieniem w ${\displaystyle T}$ już znajdowało się ${\displaystyle x.}$ W przeciwnym wypadku przyjmijmy, że ${\displaystyle y<x}$ (sytuacja odwrotna jest symetryczna). Odcinamy od ${\displaystyle y}$ jego prawe poddrzewo ${\displaystyle R}$ i tworzymy nowy węzeł zawierający ${\displaystyle x,}$ którego lewym synem czynimy ${\displaystyle y,}$ a prawym – korzeń poddrzewa ${\displaystyle R}$^[3].

Aby usunąć z drzewa ${\displaystyle T}$ wartość ${\displaystyle x,}$ wyszukujemy ${\displaystyle x}$ jak powyżej. Teraz ${\displaystyle x}$ znajduje się w korzeniu i ma poddrzewa: lewe ${\displaystyle L}$ i prawe ${\displaystyle R.}$ Usuwamy wierzchołek ${\displaystyle x,}$ a następnie wyszukujemy w ${\displaystyle L}$ wartości ${\displaystyle x,}$ co powoduje przemieszczenie do korzenia ${\displaystyle L}$ największej wartości w poddrzewie ${\displaystyle L.}$ Do korzenia ${\displaystyle L}$ podłączamy ${\displaystyle R}$ jako prawe poddrzewo^[3].

W drzewach splay szczególnie łatwo jest zaimplementować operacje split – dzielenia drzewa ${\displaystyle T}$ na dwa drzewa ${\displaystyle A}$ i ${\displaystyle B}$ tak, że wszystkie elementy w ${\displaystyle A}$ są mniejsze, a w ${\displaystyle B}$ – większe od zadanej wartości ${\displaystyle x,}$ oraz join – połączenia dwóch drzew ${\displaystyle A}$ i ${\displaystyle B}$ takich, że każdy element w ${\displaystyle A}$ jest mniejszy niż każdy element w ${\displaystyle B.}$

${\displaystyle \mathrm {Split} (T,x){:}}$ wyszukaj w ${\displaystyle T}$ element ${\displaystyle x}$ zgodnie z algorytmem podanym powyżej, następnie w zależności od tego, czy w korzeniu jest obecnie wartość większa czy mniejsza od ${\displaystyle x}$ dzielimy drzewo, usuwając krawędź z korzenia do lewego bądź prawego syna.

${\displaystyle \mathrm {Join} (T_{1},T_{2}){:}}$ W ${\displaystyle T_{1}}$ wyszukujemy dowolny element z ${\displaystyle T_{2},}$ w wyniku czego w korzeniu ${\displaystyle T_{1}}$ pojawia się wierzchołek z największą wartością z ${\displaystyle T_{1},}$ który nie ma prawego syna. Jako jego prawego syna podłączamy korzeń drzewa ${\displaystyle T_{2}.}$

Drzewo splay charakteryzuje się asymptotycznie takim samym średnim kosztem dostępu, co samorównoważące się drzewa BST, w tym drzewa AVL oraz drzewa czerwono-czarne. Mimo to, w przypadku jednakowych prawdopodobieństw dostępu do poszczególnych elementów, drzewa splay działają w praktyce (choć nie asymptotycznie) wolniej niż inne tego typu drzewa, które dodatkowo posiadają ograniczenia na pesymistyczny koszt operacji. Zaletą drzew splay jest optymalizowanie dostępu przez przesuwanie wartości, do których ostatnio uzyskiwano dostęp, blisko korzenia, co powoduje ich dużą przydatność w implementacji pamięci cache i algorytmów odśmiecania.

Inną zaletą drzew splay w stosunku do drzew AVL i czerwono-czarnych jest łatwiejsza implementacja oraz niski nakład pamięciowy na przechowywanie drzewa. Sleator i Tarjan w swojej pracy^[2] o drzewach typu splay opracowali sposób implementacji drzew splay wymagający takiej samej pamięci, jak standardowa implementacja drzew BST, w której w węźle przechowywane są jedynie: przechowywany element oraz dwa wskaźniki.

W przeciwieństwie do innych wyważonych drzew BST łatwo zaimplementować wariant drzew typu splay, który może przechowywać powtarzające się wartości (reprezentuje multizbiór).

• binarne drzewo poszukiwań (drzewo BST)
• drzewo AVL
• drzewo czerwono-czarne

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.

• Oryginalna praca Sleatora i Tarjana (pdf)
• Wizualizacja drzew splay
• Implementacje w C i Javie autorstwa Daniela Sleatora.