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