Algorytm DSW

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

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

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

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

Faza I[edytuj | edytuj kod]

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

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

Linki zewnętrzne[edytuj | edytuj kod]

Literatura[edytuj | edytuj kod]

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