高度平衡的二叉搜索樹的判定與調整

摘要：建立高度平衡的二叉搜索樹是為了提高二叉搜索樹的效率，減少樹的平均搜索長度。為此，向二叉搜索樹中每插入一個新結點時要調整樹的結構，使二叉搜索樹保持平衡，從而使得其高度保持在O(log2n)，平均搜索長度也可保持在O(log2n)。

關鍵詞：平衡的二叉搜索樹；判定；調整

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)14-20912-02

1 高度平衡的二叉搜索樹及其平衡判定

高度平衡的二叉搜索樹（又稱AVL樹）：一棵AVL樹或者是空樹，或者是具有下列性質的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1。

結點的平衡因子：結點右子樹的高度減去左子樹的高度所得的高度差。

根據AVL樹的定義，任一結點的平衡因子只能取-1，0和1。如果一個結點的平衡因子的絕對值大于1，則這棵二叉搜索樹就失去了平衡，不再是AVL樹。

2 平衡的二叉搜索樹的失衡與調整

如果在一棵平衡的二叉搜索樹中插入一個新結點，造成了不平衡。此時必須調整樹的結構，使之平衡化。

平衡化旋轉有兩類：單旋轉(左旋和右旋)和雙旋轉(左平衡和右平衡)。

每插入一個新結點時，AVL樹中相關結點的平衡狀態會發生改變。因此，在插入一個新結點后，需要從插入位置沿通向根的路徑回溯，檢查各結點的平衡因子(左、右子樹的高度差)。如果在某一結點發現高度不平衡，停止回溯。

從發生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點。

如果這三個結點處于一條直線上，則采用單旋轉進行平衡化。單旋轉可按其方向分為左單旋轉和右單旋轉，其中一個是另一個的鏡像，其方向與不平衡的形狀相關。

如果這三個結點處于一條折線上，則采用雙旋轉進行平衡化。雙旋轉分為先左后右和先右后左兩類。

2.1 左單旋轉(RotateLeft)

在插入新結點之前AVL樹的形狀如圖4(a)所示。圖中大寫字母用來指明結點，矩形框表示結點的子樹，其中的字母h給出子樹的高度。若h=-1，則B，C和D都是空指針；若h≥0，則這三個結點在樹中實際存在，是平衡的二叉搜索樹。如果在子樹E中插入一個新結點，該子樹高度增1導致結點A的平衡因子變成+2，出現不平衡。沿插入路徑檢查三個結點A、C和E。它們處于一條方向為“\\”的直線上，需要做左單旋轉。以結點C為旋轉軸，讓結點A反時針旋轉。

2.2 右單旋轉(RotateRight)

如果一棵AVL樹如圖5(a)所示，在左子樹D上插入新結點使其高度增1，導致結點A的平衡因子增到-2，造成了不平衡。為使樹恢復平衡，從A沿插入路徑連續取3個結點A、B和D，它們處于一條方向為“/”的直線上，需要做右單旋轉。以結點B為旋轉軸，將結點A順時針旋轉。

2.3 先左后右雙旋轉(RotationLeftRight)

雙旋轉總是考慮三個結點。在圖6(a)的子樹的F或G中插入新結點，該子樹的高度增1。結點A的平衡因子變為-2，發生了不平衡。從結點A起沿插入路徑選取3個結點A、B和E，它們位于一條形如“á”的折線上，因此需要進行先左后右的雙旋轉。

首先以結點E為旋轉軸，將結點B反時針旋轉，以E代替原來B的位置，做左單旋轉。再以結點E為旋轉軸，將結點A順時針旋轉，做右單旋轉。使之平衡化。

2.4 先右后左雙旋轉 (RotationRightLeft)

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

在下圖（a）的在子樹F或G中插入新結點，該子樹高度增1。結點A的平衡因子變為2，發生了不平衡。 從結點A起沿插入路徑選取3個結點A、C和D，它們位于一條形如“〉”的折線上，需要進行先右后左的雙旋轉。

首先做右單旋轉：以結點D為旋轉軸，將結點C順時針旋轉，以D代替原來C的位置。再做左單旋轉：以結點D為旋轉軸，將結點A反時針旋轉，恢復樹的平衡。

3 結束語

二叉搜索樹適合于組織在內存中的較小的索引（或目錄）。對于存放在外存中較大的文件系統，用二叉搜索樹來組織索引就不太合適了。若以結點這內外存交換的單位，則在搜索過程中為找到所需的關鍵碼，需對外存進行log2n次訪問，這是很費時的。因此在文件檢索系統中大量使用的是用B樹或B+樹做文件索引。

參考文獻：

[1] D E 克努特.管紀文，譯.計算機程序設計技巧3[M].北京:國防工業出版社，1999:185-190.

[2] 許卓群.數據結構[M].北京:高等教育出版社，1993:103-108.

[3] 嚴蔚敏.數據結構[M].北京:清華大學出版社，2004:207-215.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文