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 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
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;