Działanie pseudokodu w II fazie DSW graficznie przedstawia przykład (kontynuując poprzedni): thumb|300px|center|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 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ż binarne drzewo poszukiwań drzewo AVL drzewo binarne drzewo czerwono-czarne drzewo splay rotacja drzewa struktura danych
Bibliografia A. Drozdek, L. Simon, Struktury danych w języku C
Linki zewnętrzne
Wyważanie drzewa, optymalne czasowo i pamięciowo – Stout i Warren Strona domowa prof. Q. Stouta – Uniwersytet w Michigan
Kategoria:Drzewa (informatyka) Kategoria:Algorytmy