Algorytm DSW

Algorytm DSW to metoda równoważenia binarnego drzewa poszukiwań (BST), która sprawia, że wysokość drzewa wynosi około

O(log n)
(ściślej: h < log₂(n + 1)), gdzie n to liczba węzłów w drzewie. Algorytm ten działa w czasie proporcjonalnym do liczby węzłów O(n).

Został opracowany przez Colina Daya w 1976 roku, a następnie udoskonalony przez Quentina F. Stouta oraz Bette L. Warren w 1986 roku. Nazwa algorytmu powstała od pierwszych liter nazwisk jego twórców.

Działanie

DSW jest używany do operacji na strukturach danych w postaci drzew. Głównym celem algorytmu DSW jest zrównoważenie binarnego drzewa. Jego zaletą jest stosunkowo niewielkie zapotrzebowanie na dodatkową pamięć oraz brak konieczności przeprowadzania sortowania czy pełnej dekompozycji drzewa, co bywa nieoptymalne dla dużych struktur. Zamiast tego, algorytm wykorzystuje rotację węzłów względem ich rodziców.

Rotacja

Rotacja poddrzewa z danym korzeniem polega na przekształceniu jego struktury w taki sposób, że wysokość jednego z poddrzew zmniejsza się o jeden, podczas gdy drugie rośnie o jeden. Wyróżniamy rotacje lewo- i prawostronne.

Operacja ta nie wpływa na kolejność odwiedzania węzłów w trakcie przechodzenia drzewa metodą in-order, co oznacza, że podstawowa właściwość drzewa BST pozostaje zachowana.

Równoważenie drzewa

Faza I

Aby zrównoważyć drzewo, DSW w pierwszej kolejności przekształca je w listę przy pomocy wielokrotnych rotacji w prawo. Taki typ drzewa, przekształcony do formy listy, nazywany jest kręgosłupem.

Proces tworzenia kręgosłupa ilustruje 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; // Lewy potomek staje się 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 zobrazować na przykładzie:

W tej fazie złożoność obliczeniowa działania algorytmu wynosi O(n). Maksymalna liczba iteracji pętli while to 2n – 1, co skutkuje wykonaniem n – 1 rotacji (gdzie n to całkowita liczba węzłów w drzewie).

Faza II

W drugiej fazie DSW przywraca kształt drzewa nowo utworzonej liście poprzez wielokrotne rotacje w lewo. Rotacje te wykonuje się na co drugim węźle względem jego rodzica podczas każdego przebiegu wzdłuż skrajnej prawej ścieżki drzewa. Każdy z tych przebiegów zmniejsza długość linii o połowę, co prowadzi do uzyskania doskonale zrównoważonego drzewa.

Poniższy pseudokod przedstawia tę fazę algorytmu:

/* Pseudokod ilustrujący powstawanie idealnie wyważonego drzewa, wskutek działania drugiej fazy DSW */
TworzWywazoneDrzewo(liczba całkowita n)
    m = 2[log₂(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 można zobrazować na przykładzie. W powyższym przykładzie, przed uruchomieniem pętli while, nie zostanie wykonana żadna rotacja (ze względu na to, że m – n wyniesie 0). Po pierwszym przebiegu pętli wykonają się 3 rotacje, a po drugim tylko jedna. Po tej operacji algorytm zakończy swoje działanie, a drzewo będzie doskonale zrównoważone. Złożoność obliczeniowa tej fazy również wynosi O(n), co czyni algorytm optymalnym zarówno pod względem czasu, jak i wykorzystania pamięci, ponieważ czas rośnie liniowo w zależności od n, a dodatkowe zasoby pamięciowe są stałe i niewielkie.