【正文】 pr=p 98 ? 若結(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) 99 ? 例如，輸入關鍵碼序列為 { 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 100 右左雙旋 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 101 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 從空樹開始的建樹過程 102 AVL樹的刪除 1. 如果 被刪結(jié)點 x最多只有一個子女 ， 可做簡單刪除 : ─ 將 結(jié)點 x從樹中刪去 。 ─ 因為結(jié)點 x最多有一個子女 ， 可以簡單地把 x的雙親中原來指向 x的指針改指到這個子女結(jié)點； ─ 如果結(jié)點 x沒有子女 ， x雙親原來指向 x的指針置為 NULL。 ─ 將原來以結(jié)點 x為根的子樹的高度減 1。 103 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é)點的影響。 104 ? 用一個布爾變量 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。 105 刪除后不旋轉(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 106 ? 結(jié)點 p 的 bf 不為 0，且較矮的子樹又被縮短。 則在結(jié)點 p 發(fā)生不平衡。需要進行平衡化旋轉(zhuǎn)來恢復平衡。 ─ 令 p 的較高的子樹的根為 q（該子樹未被縮短），根據(jù) q 的 bf，有如下 3 種平衡化操作。 ─ 旋轉(zhuǎn)的方向取決于是結(jié)點 p 的哪一棵子樹被縮短。 107 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 108 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 109 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 110 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) 舉例 111 刪除結(jié)點 P 尋找結(jié)點 P的中序直接前驅(qū) O, 用 O頂替 P, 刪除 O。 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 用 O取代 P 112 刪除結(jié)點 P A B C D E F G H I J K L M N O Q R S T 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 左單旋轉(zhuǎn) O與 R的平衡因子同號 , 以 R為旋轉(zhuǎn)軸做左單旋轉(zhuǎn) , M的子樹高度減 1。 113 刪除結(jié)點 P M的子樹高度減 1， M發(fā)生不平衡。 M與 E的平衡因子反號 , 做左右雙旋轉(zhuǎn)。 A B C D E F G H I J K L M N O Q R S T 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 向上繼續(xù)調(diào)整 114 刪除結(jié)點 P A B C D E F G H I J N K L M O R 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 0 T Q 0 S 115 AVL樹的高度 ? 設在新結(jié)點插入前 AVL樹的高度為 h， 結(jié)點個數(shù)為 n， 則插入一個新結(jié)點的時間是 O(h)。對于 AVL樹來說 ， h多大 ？ ? 設 Nh 是高度為 h 的 AVL樹的最小結(jié)點數(shù) 。根的一棵子樹的高度為 h1， 另一棵子樹的高度為 h2， 這兩棵子樹也是高度平衡的 。因此有 ? N0 = 0 (空樹 ) ? N1 = 1 (僅有根結(jié)點 ) ? Nh = Nh1 + Nh2 +1 , h 1 116 ? 可以證明 , 對于 h ? 0, 有 Nh = Fh+2 1 成立。 ? 有 n 個結(jié)點的 AVL樹的高度不超過 *log2(n+2) ? 在 AVL樹刪除一個結(jié)點并做平衡化旋轉(zhuǎn)所需時間為 O(log2n)。 ? 二叉搜索樹適合于組織在內(nèi)存中的較小的索引 (或目錄 )。對于存放在外存中的較大的文件系統(tǒng)，用二叉搜索樹來組織索引不太合適。 ? 在文件檢索系統(tǒng)中大量使用的是用 B樹或 B+樹做文件索引。 117 伸展樹（ Splaying Tree） ? 伸展樹、 AVL樹、并查集的用雙親表示的樹，都屬于自調(diào)整數(shù)據(jù)結(jié)構(gòu)（ selfadjusting data structure）。 ? AVL樹使得搜索樹保持高度平衡，讓葉結(jié)點只出現(xiàn)在最低的一層或兩層上，從而提高其搜索效率。 ? 伸展樹是另一種提高搜索效率的方法，其思路是： 1. 單一旋轉(zhuǎn)： 將經(jīng)常訪問的結(jié)點最終上移到靠近根的地方，使以后的訪問更快。 118 2. 移動到根部： 假設正訪問的結(jié)點將以很高的概率再次被訪問，對它反復進行子女 ―父結(jié)點旋轉(zhuǎn)，直到被訪問的結(jié)點位于根部為止。 ? 伸展樹提出了一組改進二叉搜索樹性能的一組規(guī)則，每當執(zhí)行搜索、插入、刪除等操作時，就要依據(jù)這些規(guī)則調(diào)整二叉搜索樹，從而保證操作的時間代價。 ? 每當訪問（搜索、插入或刪除）一個結(jié)點 s 時，伸展樹就執(zhí)行一次叫做 “展開 (splaying)”的過程，將 結(jié)點 s 移到二叉搜索樹的根部 。 119 ? 就像 AVL樹，一次“展開”由一組旋轉(zhuǎn)組成。 ? 旋轉(zhuǎn)有三種類型： 單旋轉(zhuǎn) 、 一字形旋轉(zhuǎn) 和 之字形旋轉(zhuǎn) 。 ? 一次旋轉(zhuǎn)的目的是通過調(diào)整 結(jié)點 s 與它的 父結(jié)點 p 和 祖父結(jié)點 g 之間位置，把它上移到樹的更高層。 1. 被訪問結(jié)點 s 的父結(jié)點 p 是 根結(jié)點 。此時執(zhí)行 單旋轉(zhuǎn) 。在保持二叉搜索樹特性的情況下，結(jié)點 s 成為新的根，原來的根 p 成為它的子女結(jié)點。 120 2. 同構(gòu)形狀（ homogeneous configuration） 。結(jié)點 s 是其父結(jié)點 p 的左子女，結(jié)點 p 又是其父結(jié)點 g 的左子女 (／ )?；蛘呓Y(jié)點 s 是其父結(jié)點 p 的右子女，結(jié)點 p 又是其父結(jié)點 g 的右子女 (＼ )。此時執(zhí)行 一字形旋轉(zhuǎn) (zigzig rotation): p ? s ? ? s ? ? ? p 右單旋轉(zhuǎn) 121 ? 異構(gòu)的形狀（ heterogeneous configuration） 。結(jié)點 s 是其父結(jié)點 p 的左子女，結(jié)點 p 又是其父結(jié)點 g 的右子女 (＞ )。或結(jié)點 s 是其父結(jié)點 p 的右子女，結(jié)點 p 又是其父結(jié)點 g 的左子女(＜ )。此時執(zhí)行 之字形旋轉(zhuǎn) (zigzag rotation)。 p g ? ? ? s ? p g ? ? ? s ? p g ? ? ? s ? 右單旋轉(zhuǎn) 右單旋轉(zhuǎn) 122 ? 因為剛訪問的 結(jié)點 s 與其父結(jié)點 p 和祖父結(jié)點g 形成折線 ，需要做與 AVL樹一樣的 雙旋轉(zhuǎn) ，首先圍繞 s 旋轉(zhuǎn) p，再圍繞 s 旋轉(zhuǎn) g，把結(jié)點 s上升到祖父結(jié)點的位置，并保持二叉搜索樹的特性。 p g ? ? ? s ? p g ? ? ? s ? s g ? ? ? p ? 左單旋轉(zhuǎn) 右單旋轉(zhuǎn) 123 將剛訪問的結(jié)點 s上移到樹根部的算法 splaying (g, p, s) { //g 是 p 的父結(jié)點， p 是 s 的父結(jié)點 //算法將 s移到根結(jié)點位置 while (s 不是樹的根結(jié)點 ) if (s 的父結(jié)點是根結(jié)點 ) 進行單旋轉(zhuǎn) , 將 s 調(diào)整為根結(jié)點 else if (s 與它的前驅(qū) p, g 是同構(gòu)形狀 ) 進行一字形雙旋轉(zhuǎn)，將 s 上移 else //s 與它的前驅(qū) p, g 是異構(gòu)形狀 進行之字形雙旋轉(zhuǎn)，將 s 上移 }。 124 伸展樹的性能分析 ? 之字形旋轉(zhuǎn) 使得樹結(jié)構(gòu)趨向于平衡化，結(jié)果常常使樹結(jié)構(gòu)的高度減少 1。而 一字形旋轉(zhuǎn) 一般不會降低樹結(jié)構(gòu)的高度，它只是把剛訪問的結(jié)點向根結(jié)點上移。 ? 伸展樹不要求每一個操作都是高效的，對于一個有 n 個結(jié)點的樹，執(zhí)行 m 次操作時可能一次插入或搜索操作需要花費 O(n)時間。 ? 例如，對于一個有 n 個結(jié)點的單支樹，訪問最底層的結(jié)點，需要時間即為 O(n)。 125 ? 當 m≥n時，所有 m個操作總共需