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