Algorytm DSW

Algorytm DSW – algorytm równoważący binarne drzewa poszukiwań (BST), tj. powodujący że wysokość drzewa jest rzędu $O(\log n)$, 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 Day'a (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, liczba całkowita n)
                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 w dół 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, zaczynając od początku linii;
                while m > 1
                        m = [m/2]; // znaczenie nawiasów [] jak wyżej
                        wykonaj m rotacji, startując od początku linii;

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

Linki zewnętrzne

• Wyjaśnienie działania - Timothy J. Rolfe (ang.)
• Wyważanie drzewa, optymalne czasowo i pamięciowo - Stout i Warren (ang.)
• Strona domowa Prof. Q. Stouta - Uniwersytet w Michigan (ang.)

Literatura

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