Drzewo Splay

Drzewo splay (lub spalony drzewo ) jest samobalansujący binarne drzewo poszukiwań z dalszego nieruchomości, które ostatnio otwieranych elementów (dodawanie, wyświetlić lub usunąć je) są szybko dostępne. Mają zatem tłumioną złożoność O (log n) dla typowych operacji, takich jak wstawianie, wyszukiwanie lub usuwanie. Tak więc w przypadku, gdy operacje mają określoną strukturę, drzewa te stanowią bazy danych o dobrej wydajności i pozostaje to prawdą, nawet jeśli ta struktura jest a priori nieznana. Ta struktura danych została wymyślona przez Daniela Sleatora (w) i Roberta Tarjana w 1985 roku .

Po wszystkich typowych operacjach na strukturach danych następuje podstawowa operacja zwana flare ( splaying English). Rozwijanie drzewa wokół określonego elementu wiąże się z przestawieniem drzewa tak, aby element ten był umieszczony w korzeniu, zachowując uporządkowaną strukturę drzewa. Jednym ze sposobów osiągnięcia tego jest wykonanie zwykłego wyszukiwania w drzewie binarnym poprzez zapamiętanie podążanej ścieżki, a następnie wykonanie serii obrotów wału w celu doprowadzenia elementu do korzenia. Inne implementacje pozwalają na wykonanie tych dwóch operacji w jednym przebiegu.

Korzyści

Wydajność rozchylonych drzew opiera się na fakcie, że optymalizują się one samoczynnie, to znaczy często używane węzły zbliżają się do katalogu głównego, gdzie można uzyskać do nich szybki dostęp. Jednak w najgorszym przypadku większość operacji może mieć złożoność liniową; w praktyce większość ma logarytmiczną średnią złożoność.

Przybliżanie często używanych węzłów do korzenia jest korzystne w większości praktycznych sytuacji (właściwość zwana zasadą lokalności ), a zwłaszcza przy implementacji algorytmów pamięci podręcznej lub czyszczenia pamięci .

Wreszcie brak danych wtórnych (takich jak wysokość poddrzew w drzewach AVL ) umożliwia stosunkowo kompaktowe przechowywanie danych.

Niedogodności

Najbardziej oczywistą wadą wałów kielichowych jest to, że w niektórych przypadkach mogą one mieć liniową wysokość w swoim rozmiarze, co może znacząco wpłynąć na wydajność wszystkich operacji. Jednak wariant losowy umożliwia złagodzenie tej wady.

Mówiąc bardziej subtelnie, fakt, że zwykły odczyt drzewa modyfikuje jego strukturę, może stwarzać poważne trudności w przypadku, gdy do reprezentowanej bazy danych musi mieć dostęp kilku klientów jednocześnie. Czasami konieczne są wówczas konkurencyjne wdrożenia przystąpienia.

Operacje

Wprowadzenie

Aby wstawić nowy węzeł w rozwiniętym drzewie:

Zaczynamy od wstawienia tego węzła jako binarnego drzewa wyszukiwania.
Drzewo jest następnie rozszerzane na wstawionym węźle, aby umieścić je w korzeniu.

Usunięcie

Aby usunąć węzeł, postępujemy w podobny sposób jak w przypadku drzewa wyszukiwania binarnego. Jeśli węzeł ma dwoje dzieci, wymieniamy wartość tego ostatniego z jego bezpośrednim następcą w jego poddrzewach i próbujemy usunąć węzeł, którego wartość właśnie wymieniliśmy. We wszystkich przypadkach będziemy następnie rozszerzać drzewo na rodzica usuniętego węzła.

Kloszowy

Aby uzyskać rozszerzanie się na węźle , wykonuje się szereg kroków, z których każdy zbliża się do korzenia. Aby określić, który krok należy wykonać, należy wziąć pod uwagę trzy czynniki: $X$ $X$

$X$ czy jest dzieckiem po prawej czy po lewej stronie swojego rodzica , $P.$
$P.$ czy on jest korzeniem,
$P.$ czy jest dzieckiem po prawej czy po lewej stronie swojego rodzica, dziadka . $sol$

Po każdym kroku zajmie miejsce (do zakończenia u nasady). $X$ $sol$

Dwie operacje, zygzak i zag, umożliwiają wtedy uformowanie wszystkich kombinacji do wykonania: zygzak, zygzak, zygzak, zag, zag-zag i zag-zig. Trzy ostatnie, będąc symetryczne w stosunku do pierwszych trzech, skupimy się na nich.

Zig

W przypadku, gdy jest korzeniem, drzewo jest obracane na połączeniu między i . Ten krok istnieje tylko w celu rozwiązania problemów z parzystością i zostanie wykonany tylko jako ostatnia operacja (a więc po serii zig-zig i innych). $P.$ $X$ $P.$

Zig-zig

Kiedy i to zarówno dzieci po prawej stronie (. Odpowiednio po lewej), drzewo jest następnie obracana dwukrotnie: najpierw na powiązanie i , a następnie ponownie na związek pomiędzy i . $X$ $P.$ $P.$ $sol$ $X$ $P.$

Zygzak

Kiedy i to dwa różne dzieci (prawy i lewy, lub na odwrót), najpierw obraca się na związek między a następnie drugi odnośnik pomiędzy i . $X$ $P.$ $X$ $P.$ $P.$ $sol$

Bibliografia

(en) Daniel D. Sleator i Robert E. Tarjan , „ Self-Adjusting Binary Search Trees ” , Journal of the ACM , vol. 32, n o 3,1985, s. 652-686 ( DOI 10.1145 / 3828.3835 , czytaj online )