Algorytm DSW

Algorytm DSW

Rodzaj	wyważanie drzewa
Złożoność
Czasowa	$O(n)$
Pamięciowa	$O(1)$

Algorytm DSW – algorytm równoważący binarne drzewa poszukiwań (BST) tak, że wysokość drzewa jest rzędu $O(\log n)$ (ściśle: $h<\log _{2}(n+1)$), gdzie $n$ to liczba węzłów drzewa. Algorytm działa w czasie proporcjonalnym do liczby węzłów $(O(n)).$

Został stworzony przez Colina Daya (1976), a następnie poprawiony przez Quentina F. Stouta oraz Bette L. Warren (1986). Nazwa to skrótowiec, utworzony od pierwszych liter nazwisk twórców.

Działanie

DSW jest wykorzystywany przy operacji na drzewiastych strukturach danych. Głównym celem działania DSW jest zrównoważenie drzewa binarnego. Zaletą jest względnie mała, oraz stała pamięć potrzebna na dodatkowe zmienne, a także brak konieczności używania sortowania, oraz całkowitej dekompozycji, z późniejszą rekonstrukcją drzewa (co dla dużych drzew jest nieoptymalne). Zostało to zastąpione rotacją węzła, względem rodzica.

Rotacja

Rotacja poddrzewa o podanym korzeniu polega na przekształceniu jego struktury w takich sposób, że wysokość jednego poddrzewa maleje o jeden, drugiego zaś rośnie o jeden; istnieje rotacja lewo- i prawostronna.

Jednocześnie operacja ta nie zmienia kolejności odwiedzenia węzłów przy przechodzeniu drzewa metodą in-order – podstawowa własność drzewa BST pozostaje nienaruszona.

Równoważenie drzewa

Faza I

DSW w celu zrównoważenia drzewa najpierw – poprzez wielokrotne rotacje prawe – zamienia je w listę. Takie drzewo sprowadzone do postaci listy nazywa się kręgosłupem.

Tworzenie kręgosłupa demonstruje poniższy pseudokod:

   /* Pseudokod ilustrujący powstawanie kręgosłupa, wskutek działania pierwszej fazy DSW */
   TworzKregoslup (węzeł korzen)
       tmp = korzen; //tmp to zmienna tymczasowa
       while tmp nie jest równe NULL
           if tmp posiada lewego potomka
               wykonaj rotację tego potomka względem tmp; //Czyli lewy potomek zostaje ojcem węzła tmp
               tmp zostaje przesunięty do nowo powstałego rodzica;
           else
               tmp zostaje przesunięty w miejsce swojego prawego potomka;

Graficznie, działanie powyższego pseudokodu można przedstawić na przykładzie:

Kolejne rotacje węzłów (b – d) drzewa (a), aż do momentu otrzymania listy (e).

W tej fazie złożoność obliczeniowa działania algorytmu wynosi $O(n).$ Maksymalna liczba wykonań pętli while to: $2n-1.$ W takim przypadku wykona się $n-1$ rotacji ($n$ – całkowita liczba węzłów w drzewie).

Faza II

W tej fazie DSW przywraca kształt drzewa nowo powstałej liście, poprzez wielokrotne rotacje (tym razem lewe). Wykonuje się je na co drugim węźle, względem jego rodzica – podczas każdego przebiegu wzdłuż skrajnej prawej ścieżki drzewa. Każdy z takich przebiegów skraca długość linii o połowę. Tym razem ostatecznie otrzymamy drzewo doskonale zrównoważone. Tę fazę algorytmu opisuje poniższy pseudokod:

   /* Pseudokod ilustrujący powstawanie idealnie wyważonego drzewa, wskutek działania drugiej fazy DSW */
   TworzWywazoneDrzewo (liczba całkowita n)
       m = $2^{[\log _{2}(n+1)]}-1;$ // [x] oznacza funkcję entier – największą liczbę całkowitą, nie większą od x
       wykonaj n-m rotacji, idąc od początku linii po prawych potomkach;
       while m > 1
           m = [m/2]; // znaczenie nawiasów [] jak wyżej
           wykonaj m rotacji, idąc od początku linii po prawych potomkach;

Działanie pseudokodu w II fazie DSW graficznie przedstawia przykład (kontynuując poprzedni):

Kolejne lewe rotacje węzłów (b, c) listy (a), aż do momentu otrzymania drzewa doskonale zrównoważonego (c).

W powyższym przykładzie przed uruchomieniem się pętli while nie zostanie wykonana żadna rotacja (ze względu na to, że m-n wyniesie 0). Przy przejściu z kroku a) do b) (pierwsze obejście pętli) wykonają się 3 rotacje, a z kroku b) do c) tylko jedna. Po niej algorytm zakończy się, a drzewo będzie doskonale zrównoważone. Złożoność obliczeniowa tej fazy działania to także $O(n),$ a więc algorytm jest optymalny (ze względu na czas, ale także zużytą pamięć, gdyż czas rośnie liniowo wraz z n, a dodatkowe zasoby pamięciowe są stałe i niewielkie).

Zobacz też

• binarne drzewo poszukiwań
• drzewo AVL
• drzewo binarne
• drzewo czerwono-czarne
• drzewo splay
• rotacja drzewa
• struktura danych

Bibliografia

• A. Drozdek, L. Simon, Struktury danych w języku C (pol.)

Linki zewnętrzne

• Timothy J. Rolfe. One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm. „inroads”. 34 (4), s. 85–88, grudzień 2002. [zarchiwizowane z adresu 2017-10-12]. (ang.). 
• Wyważanie drzewa, optymalne czasowo i pamięciowo – Stout i Warren (ang.)
• Strona domowa prof. Q. Stouta – Uniwersytet w Michigan (ang.)