Algorytm DSW
Rodzaj | |
---|---|
Złożoność | |
Czasowa |
|
Pamięciowa |
|
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
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 | 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]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) 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:
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 | 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 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):
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 | edytuj kod]- binarne drzewo poszukiwań
- drzewo AVL
- drzewo binarne
- drzewo czerwono-czarne
- drzewo splay
- rotacja drzewa
- struktura danych
Bibliografia
[edytuj | edytuj kod]- A. Drozdek, L. Simon, Struktury danych w języku C (pol.)
Linki zewnętrzne
[edytuj | edytuj kod]- Timothy J. Rolfe. One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm. „inroads”. 34 (4), s. 85–88, grudzień 2002. [zarchiwizowane z adresu 2017-10-12]. (ang.).
- Wyważanie drzewa, optymalne czasowo i pamięciowo – Stout i Warren (ang.)
- Strona domowa prof. Q. Stouta – Uniwersytet w Michigan (ang.)
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.