Wyważone drzewo można łatwo zbudować na bazie posortowanej tablicy, algorytmem analogicznym do wyszukiwania binarnego. Jednak to podejście jest nie najlepsze jeśli drzewo już istnieje – wymaga bowiem skopiowania wszystkich danych do dodatkowej pamięci i całkowitej przebudowy drzewa. Lepszym rozwiązaniem jest użycie algorytmu DSW, który równoważy drzewo BST poprzez szereg rotacji, co nie wymaga ani sortowania, ani dodatkowej pamięci.
Optymalne drzewo poszukiwań
Jeśli wiadomo, że dane w drzewie nie będą zmieniane, a ponadto znane są prawdopodobieństwa (częstotliwości) dostępu do poszczególnych kluczy, można utworzyć optymalne BST, w którym oczekiwany czas wyszukiwania będzie minimalny. Przy konstrukcji drzewa optymalnego bierze się pod uwagę dwa czynniki: prawdopodobieństwo wyszukiwania zakończonego powodzeniem (klucz jest w drzewie) oraz niepowodzeniem (klucza nie ma w drzewie).
Algorytm tworzący optymalne BST opiera swoje działanie na programowaniu dynamicznym i charakteryzuje się złożonością czasową lub przy niewielkich modyfikacjach pokazanych przez Knutha – złożoność pamięciowa wynosi Knuth pokazuje także metody przybliżone, o mniejszej złożoności czasowej, które dają BST gorsze o 2–5% od optymalnego rozwiązania.