【文章內(nèi)容簡介】 所有元素的關(guān)鍵字小于 B中所有元素的關(guān)鍵字。最后將 A和 B設(shè)置為空。 JYP 59 （ 3） (i, B, x, C)： 分裂為三部分： B包含 A中所有關(guān)鍵字小于 i的元素；如果 A含關(guān)鍵字為 i的元素，則將該元素復(fù)制到x，并返回 x的指針，否則返回 0； C包含 A中所有關(guān)鍵字大于 i的元素。最后將 A設(shè)置為空。 JYP 60 3路結(jié)合的實現(xiàn)： 獲得一個新結(jié)點 ， 使其成為 C的 root， 并將其 data字段設(shè)置為 x， LeftChild字段設(shè)置為 ，RightChild字段設(shè)置為 。 最后將 0。 計算時間是 O(1)， 新樹 C的高度是 max{height(A), height(B)}+1。 JYP 61 2路結(jié)合可通過 3路結(jié)合實現(xiàn)： 如果 A（ 或 B） 是空樹 ， 則將 （ 或 ） ， 并將 （ 或 ） 設(shè)置為 0即可 。 當(dāng) A和 B都不空時 ， 首先從 A中刪除關(guān)鍵字最大的元素 x， 由此得到 A?。 再執(zhí)行 3路結(jié)合操作(A?, x, B)即可完成整個操作 。 計算時間是 O(height(A))， 新樹 C的高度不超過 max{height(A), height(B)}+1。 JYP 62 分裂操作的實現(xiàn)： 在根結(jié)點 （ 即 i == ?） 的分裂很容易 。 這時 ， B是 A的左子樹 ， x是根結(jié)點元素 ， C是 A的右子樹 ， 如圖 （ a） 所示 。 如果 i小于根結(jié)點的關(guān)鍵字 ， 根結(jié)點及其右子樹應(yīng)屬于 C， 如圖 （ b） 所示 。 如果 i大于根結(jié)點的關(guān)鍵字 ， 根結(jié)點及其左子樹應(yīng)屬于 B， 如圖 （ c） 所示 。 JYP 63 JYP 64 一般地 ， 可以在 A中向下查找關(guān)鍵字為 i的元素的過程中構(gòu)造二叉查找樹 B和 C。 設(shè) t指向當(dāng)前結(jié)點 。 若 i t?， 則結(jié)點 t及其右子樹應(yīng)加入 C中 。 若 i t?， 則結(jié)點 t及其左子樹應(yīng)加入 B中 。 若 i == t?， 則應(yīng)將 t的左 、 右子樹分別加入 B、 C中 ， 并將 t?data復(fù)制到 x。 JYP 65 由于當(dāng)前 C中已有關(guān)鍵字一定大于新加入部分的關(guān)鍵字 ， 所以新加入部分應(yīng)作為當(dāng)前 C中最小關(guān)鍵字所在結(jié)點 （ 用 L指向 ） 的左子樹 ， 如下所示： JYP 66 同理 ， 新加入 B部分應(yīng)作為當(dāng)前 B中關(guān)鍵字最大元素所在結(jié)點 （ 用 R指向 ） 的右子樹 。 為了避免判斷樹為空的情況 ， 在開始時為 B和 C分別引入頭結(jié)點 Y和 Z。 下面是實現(xiàn)分裂操作的算法： template class Type ElementType* BSTType::Split(Type i, BSTTypeamp。B, ElementTypeamp。x, BSTTypeamp。C) { // 根據(jù)關(guān)鍵字 i分裂 if (!root) { = = 0。 return 0。} // 空樹 BstNodeType *Y = new BstNodeType。 // B的頭結(jié)點 BstNodeType *R = Y。 BstNodeType *Z = new BstNodeType。 // C的頭結(jié)點 BstNodeType *L = Z。 JYP 67 BstNodeType *t = root。 while (t) if (i == t?) { // 在結(jié)點 t分裂 R?RightChild = t?LeftChild。 L?LeftChild = t?RightChild。 x = t?data。 delete t。 = Y?RightChild。 delete Y。 // 刪除頭結(jié)點 = Z?LeftChild。 delete Z。 // 刪除頭結(jié)點 root = 0。 return amp。x。 } else if (i t?) { L?LeftChild = t。 L = t。 t = t?LeftChild。 } JYP 68 } else { R?RightChild = t。 R = t。 t = t?RightChild。 } R?RightChild = L?LeftChild = 0。 // 注意這是必要的 = Y?RightChild。 delete Y。 // 刪除頭結(jié)點 = Z?LeftChild。 delete Z。 // 刪除頭結(jié)點 root = 0。 return 0。 } JYP 69 對 Split的分析： while循環(huán)始終保證以 t為根的子樹中的所有關(guān)鍵字大于正在構(gòu)造的 B中關(guān)鍵字 ， 小于正在構(gòu)造的 C中的關(guān)鍵字 。 由此容易證明算法的正確性 。 算法的時間復(fù)雜性是 O(height(A))。 B和 C的高度不超過 A的高度 。 JYP 70 二叉查找樹的性能分析 （ ） 為了分析二叉查找樹的性能 ， 再次引用擴展二叉樹的概念 ， 即用方結(jié)點替代所有空二叉子樹 。 這些方結(jié)點又稱為外部結(jié)點 。 二叉樹原來的 （ 圓 ） 結(jié)點稱為內(nèi)部結(jié)點 。 JYP 71 圖 （ b） 的擴展二叉樹如下所示： JYP 72 n個結(jié)點的二叉樹有 n + 1個外部結(jié)點。不成功的查找都會在某一個外部結(jié)點結(jié)束，所以也稱外部結(jié)點為 失敗結(jié)點 。 二叉樹的 外部路徑長度 E定義為所有外部結(jié)點到根結(jié)點的路徑長度之和。 內(nèi)部路徑長度 I是所有內(nèi)部結(jié)點到根結(jié)點的路徑長度之和。 圖 I = 0 + 1 + 1 + 2 = 4 其外部路徑長度 E是 E = 2 + 2 + 2 + 3 + 3 = 12 JYP 73 引理 ： 如果二叉樹 T有 n 個（ n≥0）內(nèi)部結(jié)點，I是其內(nèi)部路徑長度， E是其外部路徑長度，則 E = I + 2n。 證明： 對 n應(yīng)用歸納法。 當(dāng) n = 0， E = I = 0，引理 。 假設(shè) n = m時引理 。 考慮一棵有 m + 1個內(nèi)部結(jié)點的樹，設(shè)該樹的內(nèi)部路徑長度為 I，外部路徑長度為 E。設(shè) v是該樹中的內(nèi)部結(jié)點，且 v的左、右子女都是外部結(jié)點。設(shè) k是結(jié)點 v到根結(jié)點的路徑長度。 JYP 74 將 v的兩個子女從樹中刪除，使 v成為新的外部結(jié)點，樹的內(nèi)部結(jié)點個數(shù)減少為 m，內(nèi)部路徑長度減少為 I – k。 v的每個子女到根結(jié)點的路徑長度是 k + 1，所以外部路徑長度應(yīng)減少 2(k + 1)再加上新外部結(jié)點 v到根結(jié)點的路徑長度 k。 因此，新樹的外部路徑長度是 E – 2(k + 1) + k = E – k – 2 根據(jù)歸納假設(shè)， E – k – 2 = (I – k) + 2m 整理可得 E = I + 2(m + 1) 因此，當(dāng) n = m + 1時引理 。 ? JYP 75 查找二叉查找樹的時間依賴于所考察的內(nèi)部結(jié)點個數(shù)，假設(shè)一個內(nèi)部結(jié)點的計算時間用 一次比較 度量，下面分析具有 n個內(nèi)部結(jié)點的二叉查找樹的性能。 JYP 76 1 最壞情況 根據(jù)引理 ，具有最大 I的擴展二叉查找樹也具有最大的 E。 在二叉樹完全偏斜時 I達到最大值。這時， I = = 因此，在最壞情況的二叉查找樹中進行成功查找的平均比較次數(shù) Sn為 Sn = = () ???10nii 2 )1( ?nn1?nI 12 1 ??nJYP 77 2 最好情況 為了使 I最小，應(yīng)使盡可能多的內(nèi)部結(jié)點靠近根結(jié)點。在與根結(jié)點的距離為 1處最多可有 2個結(jié)點，距離為 2處最多可有 4個結(jié)點，一般地，最小的 I是 0 + 2 ? 1 + 4 ? 2 + 8 ? 3 + … + 完全二叉樹就是一種具有最小內(nèi)部路徑長度的樹。采用完全二叉樹的結(jié)點編號，結(jié)點 i到根結(jié)點的距離是 ?log2i?。這樣，最小的 I是 I = ? ???nii12lo gJYP 78 利用數(shù)學(xué)推導(dǎo)可得： = (n + 1)q – 2(q + 1) + 2， 其中， q = ?log2(n + 1)? 因此，在最好情況的二叉查找樹中進行成功查找的平均比較次數(shù) Sn為 Sn = = ? log2(n + 1) –1?log2n–1 () ? ???nii12lo g1?nI 122)1( )1( ???? ?nqn q)1( 1n?JYP 79 3 平均情況 Sn — 平均成功查找所需的比較次數(shù) Un — 平均不成功查找所需的比較次數(shù) 在樹中查找到任何關(guān)鍵字所需的比較次數(shù)正好是含該關(guān)鍵字的元素首次插入所需的比較次數(shù)加 1，而插入該元素所需的比較次數(shù)與該元素不在樹中的不成功查找的相同。 該元素不在樹中的不成功查找等概率地出現(xiàn)在樹中含 0, 1, …, n – 1個結(jié)點的情況。由此可得： Sn = 1 + nUUU n 110 . . . ????JYP 80 同時， Sn = ， Un = ， E = I + 2n，所以， Sn = = 即 Sn = Un – 1 () 1?nI 1?nE)1( 1n?12)1( ??? n nUn n12 ??n nEJYP 81 又由 Sn = 和 Sn = 1 + 可得 I = U0 + U1 + …+ U n1 再由 Un = = 可得 1?nInUUU n 110 . . . ????1?nE12??nnIJYP 82 (n + 1)Un = 2n + U0 + U1 + …+ U n1 為解此遞歸式，用 n – 1替換 n： n Un1 = 2(n – 1) + U0 + U1 + …+ U n2 兩式相減，得： Un = Un1 + 12?nJYP 83 由于 U0 = 0，所以， Un = 2 = 2 Hn+1 – 2 其中， Hn+1是第 n + 1個 調(diào)和數(shù) ，即 Hn+1 = 根據(jù)調(diào)和數(shù)理論， Hn ? ln n + ， Un ? 2ln n。 由于 ln n = (ln 2) (log2n)，所以， Un ? 2 (ln 2) (log2n) ? log2n () ? ?113121 . . . ???? n1113121 ...1 ?????? nnJYP 84 由 ()式， Sn ? log2n – 1。 JYP 85 最佳二叉查找樹 （ ） 如果一個符號表固定，只對其進行查找操作，則稱其為 靜態(tài)符號表 。 電子詞典就可以看成是一個靜態(tài)符號表，且在實際應(yīng)用中人們對不同單詞的查找概率是不同的。 下面討論表示靜態(tài)符號表的二叉查找樹的構(gòu)造問題。 當(dāng)查找各標(biāo)識符的概率相同時，可以用最好情況二叉查找樹表示該符號表。 JYP 86 當(dāng)查找各標(biāo)識符的概率不相同時，完全二叉樹不一定是最佳的。 直覺上，查找概率越大的標(biāo)識符越靠近