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