« poprzedni punkt   następny punkt »


2. Rotacje

Operacje wstawiania i usuwania elementu z drzewa BST mogą zmienić strukturę drzewa, w taki sposób że własność wyważenia nie będzie zachowana. Aby przywrócić strukturę AVL, konieczne są lokalne operacje na atrybutach wierzchołków, tzw. rotacje.  W tym punkcie wykładu omówimy cztery typy rotacji: rotację w prawo i rotację w lewo, zwane pojedynczymi (lub prostymi) rotacjami, i rotacje podwójne w prawo i w lewo.

Dla wygody, drzewo binarne będziemy opisywać w sposób liniowy, jako trójkę <LD, r, PD>, gdzie r jest jego korzeniem, a LD i PD odpowiednio jego lewym i prawym poddrzewem.

Rotacja w prawo.

Rozważmy drzewo binarne D postaci <<X,A,Y>,B,Z>, o korzeniu B. Rotacja w prawo względem wierzchołka B polega na "obrocie" wierzchołków A, B wzdłuż zewnętrznych  krawędzi grafu, jak zaznaczono na rysunku 8.2 (a), tak by otrzymać drzewo  < X,A,<Y,B,Z>>. Korzeniem otrzymanego po rotacji drzewa jest wierzchołek A (por. rysunek 8.2(b). Zauważmy, że zmiany są lokalne. Nie zmieniamy żadnych etykiet, ani dowiązań wewnątrz poddrzew X, Y, Z. Co więcej, jeżeli h(X) = h(Y) = h(Z) = k, to wysokość drzewa też zostaje zachowana. Rzeczywiście, wysokością drzewa przed i po rotacji jest k+2. Zatem, jeśli drzewo przed rotacją było wyważone, pozostanie wyważone po rotacji. Jeśli drzewo przed rotacją było drzewem BST, po rotacji pozostanie drzewem BST: etykiety poddrzewa Y, jako mniejsze od B i większe od A (z założenia), trafiły na prawo od A i na lewo od B.

Operacja rotacji w prawo może być zrealizowana za pomocą procedury Rotacja_w_prawo z jednym parametrem w, który określa wierzchołek względem którego zostanie wykonana rotacja.

Rotacja_w_prawo(w : node){
      aux := w.left; w.left := aux.right;
      aux.right:= w; w := aux;
}


Rotacja w lewo.

Rotacja w lewo jest operacją symetryczną do operacji rotacji w prawo i polega na "obrocie" wierzchołków A, B, tak jak zaznaczono na rysunku 8.3 (a) względem zewnętrznych krawędzi grafu. Jeżeli dane drzewo jest postaci <Z,B,<Y,A,X>>, to po wykonaniu rotacji w lewo otrzymamy drzewo <<Z,B,Y>,A,X>. Wynik rotacji w lewo został przedstawiony na rysunku 8.3 (b). Podobnie jak poprzednio, rotacja w lewo zachowuje własność bycia drzewem binarnych poszukiwań. Jeśli h(X) = h(Y) = h(Z) = k, to wysokość drzewa zarówno przed jak i po rotacji wynosi k+2. Algorytm rotacji w lewo został zapisany jako procedura Rotacja_w_lewo. Parametrem tej procedury jest wierzchołek w, względem którego dokonujemy rotacji.
 

Rotacja_w_lewo(w : node){
       aux := w.right; w.right := aux.left;
       aux.left := w; w := aux;
}

 

Koszt wykonania obu rotacji prostych jest stały: wykonujemy tylko kilka instrukcji przypisania zmieniających niektóre referencje.

 

Podwójna rotacja w prawo.

Rotacja podwójna, jak sama nazwa wskazuje, jest nieco bardziej skomplikowana. Niech dane drzewo binarne D ma postać <<X,A,<Y,B,Z>>,C,U>. Rotacja podwójna względem wierzchołka C jest złożeniem dwóch rotacji prostych: rotacji w lewo względem wierzchołka A oraz rotacji w prawo względem wierzchołka C. Po pierwszej rotacji otrzymujemy drzewo <<<X,A,Y>, B,Z>,C,U>, a po drugiej, drzewo <<X,A,Y>, B,<Z,C,U>>. Drzewo przed i po rotacji podwójnej w prawo zostało przedstawione na rysunkach 8.4(a), 8.4(b). Jeżeli h(U) = h(X)= k oraz h(Y)= h(Z)= k-1, to wysokością drzewa przed rotacją i drzewa po rotacji jest k+2. Jeżeli drzewo przed rotacją było wyważone, to po rotacji będzie także drzewem wyważonym.

Uwaga. Zauważmy, że po pierwszej prostej rotacji w lewo, ta własność dla drzewa  D nie jest spełniona.

Ponadto, własność bycia drzewem BST zostanie zachowana. Rzeczywiście, etykiety wierzchołków A, B, C jak również wierzchołki wewnątrz poddrzew X, Y, Z, U, zachowują własności uporządkowania drzew binarnych poszukiwań. Etykiety wierzchołków w poddrzewie Y są mniejsze niż etykieta w wierzchołku B, ale większe niż A (o ile D jest drzewem BST). Dowiązując poddrzewo Y jako prawego syna wierzchołka A, zachowujemy własność  uporządkowania, mówiącą, że w prawym poddrzewie A, etykiety muszą być większe od etykiety w wierzchołku A. Podobnie, etykiety w poddrzewie Z są  większe od B i mniejsze niż etykieta w wierzchołku C, jako że przed rotacją znajdowały się na lewo od C. Możemy więc dowiązać Y w prawym poddrzewie B, jako lewy następnik C. Własność: wszystkie etykiety w lewym poddrzewie wierzchołka muszą być mniejsze od etykiety w tym wierzchołku, będzie zachowana.

 

Rotację podwójną w prawo można zrealizować tak jak to przedstawiono w procedurze Rotacja_w_lewo_prawo z jednym parametrem, wierzchołkiem w, względem którego wykonywana jest  rotacja.

Rotacja_w_lewo_prawo(w : node){
       Rotacja_w_lewo(w.left);
       Rotacja_w_prawo(w);
}

Podwójna rotacja w lewo.

Operacją dualną do rotacji podwójnej w prawo, jest rotacja podwójna w lewo. Niech drzewo binarne ma postać <U,C,<<Z,B,Y>,A,X>>, por. rysunek 8.5 (a). Wynik rotacji podwójnej w lewo, <<U,C,Z>,B,<Y,A,X>>, został przedstawiony na rysunku 8.5(b). Rotacja ta jest złożeniem prostej rotacji w prawo względem wierzchołka A, oraz prostej rotacji w lewo względem wierzchołka C. 

 

Rotację podwójną w lewo można zrealizować tak jak to przedstawiono w procedurze Rotacja_w_prawo_lewo. Jedynym parametrem tej procedury jest wierzchołek w, względem którego wykonywana jest  rotacja.

Rotacja_w_prawo_lewo(w : node){
       Rotacja_w_prawo(w.left);
       Rotacja_w_lewo(w);
}

Koszt obu rotacji podwójnych jest stały, jako że koszty rotacji prostych były stałe.

Pytanie 2: Czy porządek inorder etykiet wierzchołków drzewa BST jest zachowany przy rotacji w prawo?  
 


« poprzedni punkt   następny punkt »