Algorytm DSW

Algorytm DSW – algorytm równoważący binarne drzewa poszukiwań (BST) tak, że wysokość drzewa jest rzędu (ściśle: ), gdzie to liczba węzłów drzewa. Algorytm działa w czasie proporcjonalnym do liczby węzłów

Rodzaj wyważanie drzewa
Złożoność
Czasowa
Pamięciowa

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łanieEdytuj

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.

RotacjaEdytuj

Osobny artykuł: Rotacja drzewa.

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 drzewaEdytuj

Faza IEdytuj

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 (bd) drzewa (a), aż do momentu otrzymania listy (e).

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

Faza IIEdytuj

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 =   // [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   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żEdytuj

BibliografiaEdytuj

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

Linki zewnętrzneEdytuj