【文章內(nèi)容簡(jiǎn)介】 E, class K BSTE, K::BST (K value) { //輸入一個(gè)元素序列 , 建立一棵二叉搜索樹 E x。 root = NULL。 RefValue = value。 //置空樹 cin x。 //輸入數(shù)據(jù) while ( != RefValue) { //RefValue是一個(gè)輸入結(jié)束標(biāo)志 Insert (x, root)。 cin x。 //插入，再輸入數(shù)據(jù) } }。 42 二叉搜索樹的刪除算法 ? 在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí) ， 必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來 ，同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去 。 ? 為保證在刪除后樹的搜索性能不至于降低 ，還需要防止重新鏈接后樹的高度增加 。 ?刪除葉結(jié)點(diǎn) ， 只需將其雙親結(jié)點(diǎn)指向它的指針清零 ， 再釋放它即可 。 ?被刪結(jié)點(diǎn)右子樹為空 ， 可以拿它的左子女結(jié)點(diǎn)頂替它的位置 ， 再釋放它 。 43 ?被刪結(jié)點(diǎn)左子樹為空 ， 可以拿它的右子女結(jié)點(diǎn) 頂替它的位置 ， 再釋放它 。 ?被刪結(jié)點(diǎn)左 、 右子樹都不為空 ， 可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn) (關(guān)鍵碼最小 ),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中 ， 再來處理這個(gè)結(jié)點(diǎn)的刪除問題 。 53 78 65 17 87 09 23 45 刪除 45 右子樹空 , 用左子女頂替 53 78 65 17 87 09 23 44 88 53 78 88 17 94 09 23 刪除 78 左子樹空 , 用右子女頂替 53 94 88 17 09 23 53 78 81 17 94 09 45 刪除 78 在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ) 23 65 53 81 88 17 94 09 45 23 65 45 二叉搜索樹的刪除算法 template class E, class K bool BSTE, K::Remove (const K x, BstNodeE, K *amp。 ptr) { //在以 ptr 為根的二叉搜索樹中刪除含 x 的結(jié)點(diǎn) BstNodeE, K *temp。 if (ptr != NULL) { if (x ptrdata) Remove (x, ptrleft)。 //在左子樹中執(zhí)行刪除 else if (x ptrdata) Remove (x, ptrright)。 //在右子樹中執(zhí)行刪除 46 else if (ptrleft != NULL amp。amp。 ptrright != NULL) { //ptr指示關(guān)鍵碼為 x的結(jié)點(diǎn) ， 它有兩個(gè)子女 temp = ptrright。 //到右子樹搜尋中序下第一個(gè)結(jié)點(diǎn) while (templeft != NULL) temp = templeft。 ptrdata = tempdata。 //用該結(jié)點(diǎn)數(shù)據(jù)代替根結(jié)點(diǎn)數(shù)據(jù) Remove (ptrdata, ptrright)。 } else { //ptr指示關(guān)鍵碼為 x的結(jié)點(diǎn)有一個(gè)子女 47 temp = ptr。 if (ptrleft == NULL) ptr = ptrright。 else ptr = ptrleft。 delete temp。 return true。 } } return false。 }。 ? 注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。 48 二叉搜索樹性能分析 ? 對(duì)于有 n 個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有 n! 種不同排列，可構(gòu)成不同二叉搜索樹有 (棵 ) C n nn 21 1? {2, 1, 3} {1, 2, 3} {1, 3, 2} {2, 3, 1} {3, 1, 2} {3, 2, 1} 1 2 3 1 1 1 1 3 2 2 2 3 3 2 3 49 ? 同樣 3 個(gè)數(shù)據(jù) { 1, 2, 3 }，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。 ? 如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。 ? 用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。 ? 為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。 ? 這樣的判定樹即為 擴(kuò)充的二叉搜索樹 。 50 ? 舉例說明。已知關(guān)鍵碼集合 {a1, a2, a3} = {do, if, to}，對(duì)應(yīng)搜索概率 p1, p2, p3, 在各搜索不成功間隔內(nèi)搜索概率分別為 q0, q1, q2, q3?？赡艿亩嫠阉鳂淙缦滤尽? do if to do if to q0 q1 p1 q2 p2 q3 p3 q0 q1 q2 q3 p1 p2 p3 (a) (b) 51 判定樹 do if to q0 q1 p1 q2 p2 q3 p3 do if to q0 q1 p1 q2 p2 q3 p3 (d) (c) do if to q0 q1 p1 q2 p2 q3 p3 (e) 52 ].[*][ i lipA S Lnis u c c ???1? 在判定樹中 ? ○ 表示 內(nèi)部結(jié)點(diǎn) ， 包含了關(guān)鍵碼集合中的某一個(gè)關(guān)鍵碼； ? □ 表示 外部結(jié)點(diǎn) ， 代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼 。 ? 在每?jī)蓚€(gè)外部結(jié)點(diǎn)間必存在一個(gè)內(nèi)部結(jié)點(diǎn) 。 ? 一棵判定樹上的搜索成功的平均搜索長(zhǎng)度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜索概率 p[i]與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù) c[i] (= l[i], 即結(jié)點(diǎn)所在層次 ) 乘積之和： 53 ? 設(shè)各關(guān)鍵碼的搜索概率相等： p[i] = 1/n ? 搜索不成功的平均搜索長(zhǎng)度 ASLunsucc為樹中所有外部結(jié)點(diǎn)上搜索概率 q[j]與到達(dá)外部結(jié)點(diǎn)所需關(guān)鍵碼比較次數(shù) c39。[j](= l39。[j])乘積之和： ? 設(shè)外部結(jié)點(diǎn)搜索概率相等： q[j] = 1/(n+1)： .][???nis u c c i lnA S L11????nju n s u c c jljqA S L0).1][39。 (*][?????nju n s u c c jl39。nA S L0(11 ).1][54 ? 設(shè)樹中所有內(nèi) 、 外部結(jié)點(diǎn)的搜索概率都相等： p[i] = 1/3, 1≤ i≤ 3, q[j] = 1/4, 0≤ j≤ 3 圖 (a): ASLsucc = 1/3*3+1/3*2+1/3*1 = 6/3, ASLunsucc = 1/4*3*2+1/4*2+1/4*1 = 9/4。 圖 (b): ASLsucc = 1/3*2*2+1/3*1 = 5/3, ASLunsucc = 1/4*2*4 = 8/4。 圖 (c): ASLsucc = 1/3*1+1/3*2+1/3*3 = 6/3, ASLunsucc = 1/4*1+1/4*2+1/4*3*2 = 9/4。 圖 (d): ASLsucc = 1/3*2+1/3*3+1/3*1 = 6/3, ASLunsucc = 1/4*2+1/4*3*2+1/4*1 = 9/4。 (1) 相等搜索概率的情形 55 圖 (e): ASLsucc = 1/3*1+1/3*3+1/3*2 = 6/3, ASLunsucc = 1/4*1+1/4*3*2+1/4*2 = 9/4。 ? 圖 (b)的情形所得的平均搜索長(zhǎng)度最小。 ? 一般把平均搜索長(zhǎng)度達(dá)到最小的擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。 ? 在 相等搜索概率 的情形下，所有內(nèi)部、外部結(jié)點(diǎn)的搜索概率都相等，視它們的權(quán)值都為 1。同時(shí)，第 k 層有 2k1個(gè)結(jié)點(diǎn)， k = 1, 2, ? 。則有 n 個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉搜索樹的內(nèi)部路徑長(zhǎng)度 I 至少等于序列 56 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, … 的前 n 項(xiàng)的和。 ? 因此，最優(yōu)二叉搜索樹的搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度分別為 : ? ?? ?.?????112l o g2nniu n s u c c iA S L? ?? ?.????nis u c c iA S L12 1l o g57 ? 設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等。 p[1] = , p[2] = , p[3] = q[0] = , q[1] = , q[2] = , q[3] = ? 分別計(jì)算各個(gè)可能的擴(kuò)充二叉搜索樹的搜索性能，判斷哪些擴(kuò)充二叉搜索樹的平均搜索長(zhǎng)度最小。 (2) 不相等搜索概率的情形 58 do if to do if to q0= q1= p1= q2= p2= q3= p3= q0= q1= q2= q3= p1= p2= p3= (a) (b) 圖 (a): ASLsucc = *3+*2+*1 = ， ASLunsucc = *3+*3+*2+ *1 = 。 圖 (b): ASLsucc = *2+*1+*2 = ， ASLunsucc = (+++)*2 = 。 59 do if to q0= q1= p1= q2= p2= q3= p3= do if to q0= q1= p1= q2= p2= q3= p3= (d) (c) 圖 (c): ASLsucc = *1+*2+*3 = , ASLunsucc = *1+*2+*3+*3 = . 圖 (d) : ASLsucc = *2+*3+*1 = , ASLunsucc = *2+*3+*3+*1 = . 60 ? 由此可知，圖 (c)和圖 (e)的情形下樹的平均搜索長(zhǎng)度達(dá)到最小，因此，圖 (c)和圖 (e)的情形是最優(yōu)二叉搜索樹。 do if to q0= q1= p1= q2= p2= q3= p3= (e) 圖 (e) : ASLsucc = *1+ *3+*2 = 。 ASLunsucc = *1+ *3+*3+*2 = 。 74 AVL樹 高度平衡的二叉搜索樹 高度不平衡 高度平衡 A B C A B C D E D E ? AVL 樹的定義 一棵 AVL 樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是 AVL 樹，且左子樹和右子樹的高度之差的絕對(duì)值不超過 1。 75 結(jié)點(diǎn)的平衡因子 bf (balance factor) ? 每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差，這個(gè)數(shù)字即為結(jié)點(diǎn)