【正文】 點 A的平衡因子增到 2，造成不平衡。為使樹恢復平衡，從 A沿插入路徑 右單旋轉(zhuǎn) (RotateRight ) 96 ? 插入路徑連續(xù)取 3 個結(jié)點 A、 B和 D，以結(jié)點 B為旋轉(zhuǎn)軸，將結(jié)點 A順時針旋轉(zhuǎn)。 template class E, class K void AVLTreeE, K:: RotateR (AVLNodeE, K *amp。 ptr) { B A C E D h h h1 h 2 1 1 h 插入 h h h1 h1 A B D C E 1 0 0 h h h1 B C E A D 1 0 0 97 先左后右雙旋轉(zhuǎn) (RotationLeftRight) //左子樹比右子樹高 , 旋轉(zhuǎn)后新根在 ptr AVLNodeE, K *subR = ptr。 //要右旋轉(zhuǎn)的結(jié)點 ptr = subRleft。 subRleft = ptrright。 //轉(zhuǎn)移 ptr右邊負載 ptrright = subR。 //ptr成為新根 ptrbf = subRbf = 0。 }。 ? 在結(jié)點 A的左子女的右子樹中插入新結(jié)點，該子樹高度增 1導致結(jié)點 A的平衡因子變?yōu)?2， 98 插入 h h A C E D h1 h1 B F G 1 0 0 E 左單 旋轉(zhuǎn) G A C D B F h h h1 h 1 1 2 造成不平衡。 ? 以結(jié)點 E為旋轉(zhuǎn)軸，將結(jié)點 B反時針旋轉(zhuǎn)，以 E代替原來 B的位置。 99 ? 再以結(jié)點 E為旋轉(zhuǎn)軸 ， 將結(jié)點 A順時針旋轉(zhuǎn) 。使之平衡化 。 template class E, class K void AVLTreeE, K:: 右單 旋轉(zhuǎn) A E h h C D h1 h B F G 0 2 2 F G D h A h1 C E B 0 0 1 h h 100 RotateLR (AVLNodeE, K *amp。 ptr) { AVLNodeE, K *subR = ptr。 AVLNodeE, K *subL = subRleft。 ptr = subLright。 subLright = ptrleft。 ptrleft = subL。 if (ptrbf = 0) subLbf = 0。 else subLbf = 1。 subRleft = ptrright。 ptrright = subR。 if (ptrbf == 1) subRbf = 1。 else subRbf = 0。 101 ptrbf = 0。 }。 ? 在結(jié)點 A的右子女的左子樹中插入新結(jié)點，該子樹高度增 1。結(jié)點 A的平衡因子變?yōu)?2，發(fā)生了不平衡。 ? 首先以結(jié)點 D為旋轉(zhuǎn)軸，將結(jié)點 C順時針旋轉(zhuǎn)，以 D代替原來 C的位置。 先右后左雙旋轉(zhuǎn) (RotationRightLeft) 102 插入 h h h1 h1 A C E D B F G 1 0 0 右單旋轉(zhuǎn) A C E B F G D h h h h1 1 0 2 ? 再以結(jié)點 D為旋轉(zhuǎn)軸，將結(jié)點 A反時針旋轉(zhuǎn)， 恢復樹的平衡。 103 A C E D B F G h h h1 h 0 0 1 h h h1 h 左單 旋轉(zhuǎn) A C E B F G D 0 2 2 template class E, class K void AVLTreeE, K:: RotateRL (AVLNodeE, K *amp。 ptr) { AVLNodeE, K *subL = ptr。 104 AVLNodeE, K *subR = subLright。 ptr = subRleft。 subRleft = ptrright。 ptrright = subR。 if (ptrbf = 0) subRbf = 0。 else subRbf = 1。 subLright = ptrleft。 ptrleft = subL。 if (ptrbf == 1) subLbf = 1。 else subLbf = 0。 ptrbf = 0。 }。 105 AVL樹的插入 ? 在向一棵本來是高度平衡的 AVL樹中插入一個新結(jié)點時 ， 如果樹中某個結(jié)點的平衡因子的絕對值 |bf| 1， 則出現(xiàn)了不平衡 ， 需要做平衡化處理 。 ? AVL樹的插入算法從一棵空樹開始，通過輸入一系列對象關鍵碼，逐步建立 AVL樹。 ? 在插入新結(jié)點后，需從插入結(jié)點沿通向根的路徑向上回溯，如果發(fā)現(xiàn)有不平衡的結(jié)點，需從這個結(jié)點出發(fā)，使用平衡旋轉(zhuǎn)方法進行平衡化處理。 106 ? 設新結(jié)點 p的平衡因子為 0，其父結(jié)點為 pr。插入新結(jié)點后 pr的平衡因子值有三種情況： 1. 結(jié)點 pr的平衡因子為 0。 說明剛才是在 pr的較矮的子樹上插入了新結(jié)點，此時不需做平衡化處理，返回主程序。子樹的高度不變。 2. 結(jié)點 pr的平衡因子的絕對值 |bf| = 1。 說明插入前 pr的平衡因子是 0，插入新結(jié)點后，以 pr為根的子樹不需平衡化旋轉(zhuǎn)。但該子樹高度 1 0 插入后 pr p 107 增加，還需從結(jié)點 pr向根方向回溯，繼續(xù)考查結(jié)點 pr雙親 (pr = Parent(pr))的平衡狀態(tài)。 3. 結(jié)點 pr的平衡因子的絕對值 |bf| = 2。 說明新結(jié)點在較高的子樹上插入，造成了不平衡，需要做平衡化旋轉(zhuǎn)。此時可進一步分 2種情況討論： ? 若結(jié)點 pr的 bf = 2，說明右子樹高，結(jié)合其右子女 q 的 bf分別處理： 0 1 插入后 pr p 108 ─若 q的 bf為 1，執(zhí)行左單旋轉(zhuǎn)。 ─若 q的 bf為 1，執(zhí)行先右后左雙旋轉(zhuǎn)。 左單旋轉(zhuǎn) 插入后 2 q 1 pr p 0 pr 0 p pr=q 右左雙旋轉(zhuǎn) 插入后 2 q 1 pr p 0 pr 0 q pr=p 109 ? 若結(jié)點 pr的 bf = 2，說明左子樹高，結(jié)合其左子女 q 的 bf分別處理： ─ 若 q的 bf為 1，執(zhí)行右單旋轉(zhuǎn)； ─ 若 q的 bf為 1，執(zhí)行先左后右雙旋轉(zhuǎn)。 ? 下面舉例說明在 AVL樹上的插入過程。 2 q 1 pr p 2 q 1 pr p 右單旋轉(zhuǎn) 左右雙旋轉(zhuǎn) 110 ? 例如，輸入關鍵碼序列為 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }， 插入和調(diào)整過程如下。 16 0 16 3 1 0 左右雙旋 7 3 16 0 0 0 7 3 11 0 1 1 16 右單旋 3 7 16 9 0 0 0 1 11 16 3 7 0 1 2 7 3 16 11 9 0 1 2 2 3 7 11 26 9 16 0 1 1 2 111 右左雙旋 0 左單旋 18 16 0 0 7 3 26 11 9 0 0 0 3 16 0 9 1 7 11 26 18 3 1 1 7 16 14 26 9 1 11 2 7 3 9 0 18 26 11 1 16 1 112 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 從空樹開始的建樹過程 113 AVL樹的刪除 1. 如果 被刪結(jié)點 x最多只有一個子女 ， 可做簡單刪除 : ─ 將 結(jié)點 x從樹中刪去 。 ─ 因為結(jié)點 x最多有一個子女 ， 可以簡單地把 x的雙親中原來指向 x的指針改指到這個子女結(jié)點； ─ 如果結(jié)點 x沒有子女 ， x雙親原來指向 x的指針置為 NULL。 ─ 將原來以結(jié)點 x為根的子樹的高度減 1。 114 2. 如果 被刪結(jié)點 x 有兩個子女 : ─ 搜索 x 在中序次序下的 直接前驅(qū) y (同樣可以找直接后繼 )。 ─ 把 結(jié)點 y 的內(nèi)容傳送給結(jié)點 x， 現(xiàn)在問題轉(zhuǎn)移到刪除 結(jié)點 y。 把結(jié)點 y 當作被刪結(jié)點 x。 ─ 因為結(jié)點 y 最多有一個子女 ， 可以簡單地用 1. 給出的方法進行刪除 。 ? 必須沿結(jié)點 x 通向根的路徑反向追蹤高度的變化對路徑上各個結(jié)點的影響。 115 ? 用一個布爾變量 shorter（縮短） 來指明子樹高度是否被縮短。在每個結(jié)點上要做的操作取決于 shorter的值和結(jié)點的 bf，有時還要依賴子女的 bf。 ? 布爾變量 shorter的值初始化為 True。然后對于從 x的雙親到根的路徑上的各個結(jié)點 p，在 shorter保持為 True時執(zhí)行下面操作。如果 shorter變成 False，算法終止。 ? 當前結(jié)點 p 的 bf為 0。 如果它的左子樹或右子樹被縮短，則它的 bf改為 1或 1，同時 shorter置為 False。 116 刪除后不旋轉(zhuǎn) ? 結(jié)點 p 的 bf 不為 0且較高的子樹被縮短。則 p 的 bf 改為 0，同時 shorter置為 True。 p 0 h h h1 p 1 h h1 刪除后不旋轉(zhuǎn) p 1 h h1 p 0 h1 h1 117 ? 結(jié)點 p 的 bf 不為 0，且較矮的子樹又被縮短。 則在結(jié)點 p 發(fā)生不平衡。需要進行平衡化旋轉(zhuǎn)來恢復平衡。 ─ 令 p 的較高的子樹的根為 q（該子樹未被縮短），根據(jù) q 的 bf，有如下 3 種平衡化操作。 ─ 旋轉(zhuǎn)的方向取決于是結(jié)點 p 的哪一棵子樹被縮短。 118 a) 如果 q（較高的子樹）的 bf 為 0，執(zhí)行一個單旋轉(zhuǎn)來恢復結(jié)點 p 的平衡，置shorter為 False。 無需檢查上層結(jié)點的平衡因子。 左單旋轉(zhuǎn) 1 h h1 p h q 1 1 h h h1 p h 0 q 119 b) 如果 q 的 bf 與 p 的 bf 相同，則執(zhí)行一個單旋轉(zhuǎn)來恢復平衡，結(jié)點 p 和 q 的 bf 均改為 0，同時置 shorter為 True。 還要繼續(xù)檢查上層結(jié)點的平衡因子。 左單旋轉(zhuǎn) 0 h1 h1 p h q 0 1 h h1 h1 p h 1 q 120 c) 如果 p 與 q 的 bf 相反，則執(zhí)行一個雙旋轉(zhuǎn)來恢復平衡。先圍繞 q 轉(zhuǎn)再圍繞 p 轉(zhuǎn)。新根結(jié)點的 bf 置為 0，其他結(jié)點的 bf 相應處理，同時置 shorter為 True。 0 h1 h1 h1 h1 0 0 p q r 右左雙旋轉(zhuǎn) 高度減 1 1 h h1 p 1 q h1 或 h2 h1 或 h2 h1 r 121 A B C D E F G H I J K L M N O P Q R S T 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 樹的初始狀態(tài) 舉例 122 刪除結(jié)點 P 尋找結(jié)點 P的中序直接前驅(qū) O, 用