Rotacja drzewa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]