« poprzedni punkt | następny punkt » |
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 » |