【正文】 平衡 A B C A B C D E D E 68 結點的平衡因子 balance (balance factor) ? 每個結點附加一個數字 , 給出該結點 右子樹的高度減去左子樹的高度 所得的 高度差 ,這個數字即為結點的平衡因子 balance ? AVL樹任一結點平衡因子只能取 1, 0, 1 ? 如果一個結點的平衡因子的絕對值大于 1,則這棵二叉搜索樹就失去了平衡 , 不再是AVL樹。 ? 如果一棵二叉搜索樹是高度平衡的 , 且有 n 個結點，其高度可保持在 O(log2n),平均搜索長度也可保持在 O(log2n)。 69 AVL樹的結構定義 typedef int DataType。 //結點數據類型 typedef struct node { //AVL樹結點定義 DataType data。 //結點數據域 int balance。 //結點平衡因子域 struct node *leftChild, *rightChild。 //結點左、右子女指針域 } AVLNode。 typedef AVLNode * AVLTree。 //AVL樹 70 平衡化旋轉 ? 如果在一棵平衡的二叉搜索樹中插入一個新結點，造成了不平衡。此時必須調整樹的結構，使之平衡化。 ? 平衡化旋轉有兩類： ? 單旋轉 (左旋和右旋 ) ? 雙旋轉 (左平衡和右平衡 ) ? 每插入一個新結點時 , AVL 樹中相關結點的平衡狀態(tài)會發(fā)生改變。因此 , 在插入一 個新結點后，需要 從插入位置沿通向根的路徑回溯 ， 檢查各結點的平衡因子 。 71 ? 如果在某一結點發(fā)現高度不平衡，停止回溯。從發(fā)生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點。 ? 如果這三個結點處于一條直線上，則采用單旋轉進行平衡化 。 單旋轉可按其方向分為左單旋轉和右單旋轉 , 其中一個是另一 個的鏡像，其方向與不平衡的形狀相關。 ? 如果這三個結點處于一條折線上，則采用雙旋轉進行平衡化 。 雙旋轉分為先左后右和先右后左兩類。 72 右單旋轉 左單旋轉 左右雙旋轉 右左雙旋轉 左單旋轉 (RotateLeft ) h h h A C E B D h h h + 1 B A C E D h h h + 1 C E A B D +1 +2 0 +1 0 0 73 右單旋轉 左單旋轉 左右雙旋轉 右左雙旋轉 左單旋轉 (RotateLeft ) h h h A C E B D h h h + 1 B A C E D h h h + 1 C E A B D +1 +2 0 +1 0 0 74 ? 在子樹 E中插入新結點 ， 該子樹高度增 1導致結點 A的平衡因子變成 +2， 出現不平衡 。 ? 沿插入路徑檢查三個結點 A、 C和 E。 它們處于方向為 “ \”的直線上 ， 需做左單旋轉 。 ? 以結點 C為旋轉軸 ， 讓結點 A反時針旋轉 。 右單旋轉 (RotateRight ) ? 在左子樹 D上插入新結點使其高度增 1，導致結點 A的平衡因子增到 2，造成不平衡。 ? 為使樹恢復平衡，從 A沿插入路徑連續(xù)取 3 個結點 A、 B和 D，它們處于一條方向為“ /”的直線上，需要做右單旋轉。 75 h h h A C E B D h h + 1 B A C E D h h h + 1 C E A B D ? 以結點 B為旋轉軸，將結點 A順時針旋轉。 h 0 0 0 1 1 2 先左后右雙旋轉 (RotationLeftRight) ? 在子樹 F或 G中插入新結點 ， 該子樹的高度增 1。 結點 A的平衡因子變?yōu)? 2， 發(fā)生了不平衡 。 76 插入 0 0 1 2 +1 1 h h A C E D h1 h1 h h A h1 h B C E D B 左單 旋轉 F G F G ? 從結點 A起沿插入路徑選取 3個結點 A、 B和 E， 它們位于一條形如 “ ?” 的折線上 ，因此需要進行先左后右的雙旋轉 。 ? 以結點 E為旋轉軸 ， 將結點 B反時針旋轉 。 77 0 0 2 0 0 +1 h h A C E D 2 h1 h h h A h1 h B C E D B 右單 旋轉 F G F G 78 先右后左雙旋轉 (RotationRightLeft) ? 右左雙旋轉是左右雙旋轉的鏡像 。 ? 在子樹 F或 G中插入新結點 ， 該子樹高度增1。 結點 A的平衡因子變?yōu)?2， 發(fā)生了不平衡 。 ? 從 結點 A起沿插入路徑選取 3個結點 A、 C和 D， 它們位于一條形如 “ ?” 的折線上 ，需要進行先右后左的雙旋轉 。 79 插入 右單旋轉 +1 0 0 0 1 +1 0 h h A C E D h1 B F G h1 +2 0 0 0 h h A C E h B F G h1 D ? 首先做右單旋轉：以結點 D為旋轉軸 ， 將結點 C順時針旋轉 ， 以 D代替原來 C的位置 。 80 0 0 +2 0 1 0 h h A C E +2 h1 h h h A h1 h B C E D B 左單 旋轉 F G F G D ? 再做左單旋轉：以結點 D為旋轉軸 ， 將結點A反時針旋轉 ， 恢復樹的平衡 。 81 AVL樹的插入 ? 在向一棵本來是高度平衡的 AVL樹中插入一個新結點時 ， 如果樹中某個結點的平衡因子的絕對值 |balance| 1， 則出現了不平衡 ， 需要做平衡化處理 。 ? 算法 從一棵空樹開始 ，通過輸入一系列對象關鍵碼， 逐步建立 AVL樹 。在插入新結點時 使用平衡旋轉方法進行平衡化處理 。 82 16 16 例，輸入關鍵碼序列為 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }， 插入和調整過程如下。 0 3 16 3 1 0 7 0 1 2 左右雙旋 7 3 16 0 0 0 7 3 11 0 1 1 7 3 16 16 11 9 0 1 2 右單旋 3 7 16 9 0 0 0 1 3 7 11 26 9 16 11 0 1 1 2 2 83 18 18 0 3 16 3 1 0 16 0 2 右左雙旋 7 3 9 0 0 0 18 26 11 1 7 3 26 16 11 9 1 左單旋 9 7 16 14 0 0 1 7 11 26 26 9 1 1 11 84 15 18 2 3 18 16 2 左右雙旋 7 3 0 0 0 11 7 14 9 1 16 15 0 1 11 26 26 14 1 2 9 從空樹開始的建樹過程 85 AVL樹的高度 ? 設在新結點插入前 AVL樹的高度為 h， 結點個數為 n， 則插入一個新結點的時間是O(h)。 對于 AVL樹來說 ， h 多大 ？ ? 設 Nh 是高度為 h 的 AVL樹的最小結點數 。根的 一棵子樹的高度為 h1， 另一棵子樹的高度為 h2， 這兩棵子樹也是高度平衡的 。 因此有 ? N1 = 0 (空樹 ) ? N0 = 1 (僅有根結點 ) ? Nh = Nh1 + Nh2 +1 , h 0 86 ? 可以證明 , 對于 h ? 0, 有 Nh = Fh+3 1 成立。 其中，斐波那契數列 F0 = 0, F1 = 1, Fn = Fn1 + Fn2, n 1時 ? 有 n 個結點的 AVL樹的高度不超過 *log2(n+1)1 ? 在 AVL樹刪除一個結點并做平衡化旋轉所需時間為 O(log2n)。 ? 二叉搜索樹適合于組織在內存中的較小的索引 (或目錄 )。對于存放在外存中的較大的文件系統，用二叉搜索樹來組織索引不太合適。