Rotacja drzewa

Rotacja drzewa – w informatyce operacja polegająca na lokalnej zmianie struktury binarnego drzewa poszukiwań (BST) z zachowaniem porządku wierzchołków. Rotacje stosuje się w drzewach BST do uzyskania wyważenia drzewa i minimalizacji jego wysokości, co prowadzi do zmniejszenia kosztu operacji na drzewie.

Przebieg rotacji

Rotacja odbywa się wokół krawędzi $(x, y)$ drzewa. Jeżeli $x$ jest rodzicem $y$ (jest wyżej w drzewie), a $y$ jest jego lewym synem, mówimy o prawej rotacji (rotacji w prawo), jeżeli jest prawym synem – o lewej rotacji (rotacji w lewo).

Lewa i prawa rotacja wokół krawędzi (P, Q)

Pseudokod

W poniższym pseudokodzie $Q$ oznacza wierzchołek leżący wyżej w drzewie, $P$ – wierzchołek leżący niżej (lewego syna $Q$), a rotacja odbywa się w prawo względem krawędzi $(Q, P)$ (sytuacja przy rotacji lewej jest symetryczna). Prawy i lewy są wskaźnikami na synów wierzchołka.

Pseudokod prawej rotacji (dla $Q$)

P = Q.lewy
Q.lewy = P.prawy
P.prawy = Q
Q = P

Po wykonaniu rotacji należy zapewnić, że ojciec wierzchołka $Q$, jeśli istnieje, wskazuje po rotacji na $P$ jako na swojego odpowiedniego syna. Operacja może również powodować zmianę korzenia całego drzewa.

Własności i zastosowanie

Rotacja odbywa się w czasie stałym i powoduje zmniejszenie głębokości jednego z węzłów drzewa oraz jednego z jego poddrzew (węzeł P i poddrzewo A na rysunku powyżej) oraz zwiększenie głębokości innego wierzchołka i jednego z jego poddrzew (Q i C). Ta własność powoduje przydatność rotacji do zmniejszania głębokości (równoważenia) drzewa BST. Dlatego rotacje stosuje się w algorytmach równoważących drzewa BST (np. drzewa AVL, czerwono-czarne lub splay). Przykładem takiego algorytmu jest algorytm DSW.

Wykonanie rotacji nie zmienia kolejności przechodzenia wierzchołków drzewa w kolejności inorder.

Lewa i prawa rotacja są swoimi odwrotnościami (tzn. wykonanie lewej, a potem prawej rotacji na tym samym węźle sprowadza drzewo do stanu początkowego).

Podwójna rotacja

W niektórych algorytmach (np. drzewach o ograniczonym zrównoważeniu oraz drzewach splay) używa się również procedury podwójnej rotacji. W przypadku lewej podwójnej rotacji najpierw wykonuje się prawą rotację na prawym poddrzewie, a potem lewą rotację na wyjściowym węźle.

Linki zewnętrzne

• Wizualizacje rotacji w formie apletów Java.