平衡化旋轉

平衡化旋轉，如果在一棵平衡的二叉查找樹中插入一個新結點，造成了不平衡。此時必須調整樹的結構，使之平衡化。每插入一個新結點時，AVL樹中相關結點的平衡狀態會發生改變。因此，在插入一個新結點後，需要從插入位置沿通向根的路徑回溯，檢查各結點的平衡因子(左、右子樹的高度差)。

左單旋轉

如果在子樹E中插入一個新結點，該子樹高度增1導致結點A的平衡因子變成+2，出現不平衡。

沿插入路徑檢查三個結點A、C和E。它們處於一條方向為“\”的直線上，需要做左單旋轉。

以結點C為旋轉軸，讓結點A反時針。

void L_Rotate(BSTree &p)

{//左單旋轉的算法

BSTree rc;

rc=p->rchild;

p->rchild=rc->lchild;

rc->lchild=p;

p=rc;}

右單旋轉

在左子樹D上插入新結點使其高度增1，導致結點A的平衡因子增到-2，造成了不平衡。

為使樹恢復平衡，從A沿插入路徑連續取3個結點A、B和D，它們處於一條方向為“/”的直線上，需要做右單旋轉。

以結點B為旋轉軸，將結點A順時針旋轉。

先左後右雙旋轉

在子樹F或G中插入新結點，該子樹的高度增1。結點A的平衡因子變為-2，發生了不平衡。

從結點A起沿插入路徑選取3個結點A、B和E，它們位於一條形如“”的折線上，因此需要進行先左後右的雙旋轉。

首先以結點E為旋轉軸，將結點B反時針旋轉，以E代替原來B的位置，做左單旋轉。

再以結點E為旋轉軸，將結點A順時針旋轉，做右單旋轉。使之平衡化。

先右後左雙旋轉

右左雙旋轉是左右雙旋轉的鏡像。

在子樹F或G中插入新結點，該子樹高度增1。結點A的平衡因子變為2，發生了不平衡。

從結點A起沿插入路徑選取3個結點A、C和D，它們位於一條形如“”的折線上，需要進行先右後左的雙旋轉。

首先做右單旋轉：以結點D為旋轉軸，將結點C順時針旋轉，以D代替原來C的位置。

再做左單旋轉：以結點D為旋轉軸，將結點A反時針旋轉，恢復樹的平衡。