Rotacja drzewa

Rotacja drzewa – 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. Matematycznie rotacja jest dopuszczalna jeżeli relacja opisana drzewem jest łączna. Binarne drzewa poszukiwań są generalnie łączne ze względu na łączność relacji porządkującej klucze. Jeżeli rozpatrywane jest drzewo składniowe opisujące wyrażenie arytmetyczne to rotacje są dozwolone tylko między operacjami, które są łączne - np. dodawanie można obracać względem dodawania lub odejmowania, ale nie względem mnożenia.

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