Algorytm DSW

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Algorytm DSW
Rodzaj wyważanie drzewa
Złożoność
Czasowa
Pamięciowa

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

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[edytuj]

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[edytuj]

 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 drzewa[edytuj]

Faza I[edytuj]

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 . Maksymalna liczba wykonań pętli while to: . W takim przypadku wykona się rotacji ( - całkowita liczba węzłów w drzewie).

Faza II[edytuj]

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 =  // [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 , 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]

Bibliografia[edytuj]

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

Linki zewnętrzne[edytuj]