【正文】 n 個元素，搜索第 i 個元素的概率為 pi，搜索到第 i 個元素所需比較次數(shù)為 ci，則搜索成功的平均搜索長度 : ? 在順序搜索并設(shè)置“監(jiān)視哨”情形： ci = i +1, i = 0, 1, ? , n1，因此 ?????????1010niiniiis u c c pcpA S L ) 1 ( .)(110??? ??ipA S Lniis u c c順序搜索的平均搜索長度 20 ? 一般表中各個元素的搜索概率不同，如果按搜索概率的高低排列表中的元素，從有序順序表的情況可知，能夠得到高的平均搜索長度。 int Loc。 17 使用監(jiān)視哨的順序搜索算法 template class E, class K int dataListE, K::SeqSearch (const K x) const { Element[CurrentSize].key = x。 }。 InList) { 14 cout “輸入存儲數(shù)組當(dāng)前長度 : ”。 i++) out [i1] ? ?。 return true。 i CurrentSize amp。 //插入在尾端 CurrentSize++。 in, dataListE, Kamp。 //插入 virtual bool Remove (K x, Eamp。 } //析構(gòu)函數(shù) virtual int Length() { return CurrentSize。 } //修改關(guān)鍵碼 private: K key。 ? 動態(tài)搜索表 ? 在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)元素的存放地址。 4 ? 通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象 (或記錄 )組成。這時，作為結(jié)果，可報告該對象在結(jié)構(gòu)中 的位置 , 還可給出該對象中的具體信息。 ? 實施搜索時有兩種不同的環(huán)境。 //數(shù)據(jù)表類的前視定義 template class E, class K class dataNode { //數(shù)據(jù)表中結(jié)點類的定義 friend class dataListE, K。 } dataList (dataListE, Kamp。 } virtual int SeqSearch (const K x) const。 OutList)。 template class E, class K bool dataListE, K::Insert (Eamp。 //用尾元素填補(bǔ)被刪除元素。 //未找到 e1 = Element[i].other。 OutList) { out “存儲數(shù)組大小” endl。 template class E, class K istreamamp。 i++) { //從 in輸入表的全部表項 cout “元素 ” i “ : ”。 順序搜索（ Sequential Search） 16 ? 一般的順序搜索算法在第二章已經(jīng)討論過，本章介紹一種使用“監(jiān)視哨”的順序搜索方法。 const int Size = 10。 //輸入要搜索的數(shù)據(jù) if ( (Location = (Target)) != () ) cout “找到待查元素位置在：” Loc+1 endl。 10 20 30 40 50 60 i = 1 搜索 30 10 20 30 40 50 60 i = 2 10 20 30 40 50 60 i = 3 遞 歸 順序搜索的遞歸算法 22 順序搜索的遞歸算法 template class E, class K int dataListE, K:: SeqSearch (const K x, int loc) const { //在數(shù)據(jù)表 Element[1..n] 中搜索其關(guān)鍵碼與給定值 //匹配的對象 , 函數(shù)返回其表中位置。 i++ ) if ( Element[i].key == x ) return i。 }。 x ) const { //折半搜索的迭代算法 int high = CurrentSize1, low = 0, mid。 35 15 45 50 25 10 20 30 搜索 22 搜索 45 折半搜索性能分析 ? 若設(shè) n = 2h1，則描述折半搜索的判定樹是高度為 h1 的滿二叉樹。 35 35 15 45 50 40 25 10 20 30 二叉搜索樹例 ? 結(jié)點左子樹上所有關(guān)鍵碼小于結(jié)點關(guān)鍵碼； ? 右子樹上所有關(guān)鍵碼大于結(jié)點關(guān)鍵碼； ? 注意：若從根結(jié)點到某個葉結(jié)點有一條路徑，路徑左邊的結(jié)點的關(guān)鍵碼不一定小于路徑上的結(jié)點的關(guān)鍵碼。 right = R。 x) //重載：判等于 { return == 。 R)。} 40 bool Remove (const K x) { return Remove(x, root)。 41 BSTNodeE, K* Min (BSTNodeE, K* ptr)。 ? 二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現(xiàn)與二叉樹類似。若找到，則函數(shù)返回該結(jié)點的 //地址，否則函數(shù)返回 NULL值。 if (ptr == NULL) return NULL。 ? 搜索成功，搜索指針將停留在樹上某個結(jié)點；搜索不成功，搜索指針將走到樹上某個結(jié)點的空子樹。 ptr) { //私有函數(shù)：在以 ptr為根的二叉搜索樹中插入值為 //e1的結(jié)點。 //x已在樹中 ,不再插入 }。 cin x。 53 78 65 17 87 09 23 45 刪除 45 右子樹空 , 用左子女頂替 53 78 65 17 87 09 23 55 88 53 78 88 17 94 09 23 刪除 78 左子樹空 , 用右子女頂替 53 94 88 17 09 23 53 78 81 17 94 09 45 刪除 78 在右子樹上找中序下第一個結(jié)點填補(bǔ) 23 65 53 81 88 17 94 09 45 23 65 56 二叉搜索樹的刪除算法 template class E, class K bool BSTE, K::Remove (const K x, BstNodeE, K *amp。 ptrdata = tempdata。 }。 ? 這樣的判定樹即為 擴(kuò)充的二叉搜索樹 。[j])乘積之和： ? 設(shè)外部結(jié)點搜索概率相等： q[j] = 1/(n+1)： .][???nis u c c i lnA S L11????nju n s u c c jljqA S L0).1][39。 ? 一般把平均搜索長度達(dá)到最小的擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。 70 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 = . 71 ? 由此可知，圖 (c)和圖 (e)的情形下樹的平均搜索長度達(dá)到最小，因此，圖 (c)和圖 (e)的情形是最優(yōu)二叉搜索樹。 include include “” template class E, class K struct AVLNode : public BSTNodeE, K { //AVL樹結(jié)點的類定義 int bf。 } }。 e1) { return Insert (root, e1)。 operator (ostreamamp。 ptr, K x, Eamp。 //先左后右雙旋 void RotateRL (AVLNodeE, K*amp。從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點。 ptr) { //右子樹比左子樹高 : 做左單旋轉(zhuǎn)后新根在 ptr 插入 左單 旋轉(zhuǎn) A C E B D h h h1 h1 1 0 0 B A C E D h h h1 h 2 1 1 B h h C E A D 0 0 h1 h 1 95 AVLNodeE, K *subL = ptr。 template class E, class K void AVLTreeE, K:: RotateR (AVLNodeE, K *amp。 ? 以結(jié)點 E為旋轉(zhuǎn)軸，將結(jié)點 B反時針旋轉(zhuǎn)，以 E代替原來 B的位置。 ptrleft = subL。 }。 ptr = subRleft。 else subLbf = 0。 說明剛才是在 pr的較矮的子樹上插入了新結(jié)點，此時不需做平衡化處理，返回主程序。 ─若 q的 bf為 1，執(zhí)行先右后左雙旋轉(zhuǎn)。 ─ 把 結(jié)點 y 的內(nèi)容傳送給結(jié)點 x， 現(xiàn)在問題轉(zhuǎn)移到刪除 結(jié)點 y。如果 shorter變成 False，算法終止。 ─ 令 p 的較高的子樹的根為 q（該子樹未被縮短），根據(jù) q 的 bf，有如下 3 種平衡化操作。新根結(jié)點的 bf 置為 0，其他結(jié)點的 bf 相應(yīng)處理，同時置 shorter為 True。 118 a) 如果 q（較高的子樹）的 bf 為 0，執(zhí)行一個單旋轉(zhuǎn)來恢復(fù)結(jié)點 p 的平衡，置shorter為 False。 如果它的左子樹或右子樹被縮短，則它的 bf改為 1或 1，同時 shorter置為 False。 ─ 因為結(jié)點 y 最多有一個子女 ， 可以簡單地用 1. 給出的方法進(jìn)行刪除 。 ? 下面舉例說明在 AVL樹上的插入過程。 2. 結(jié)點 pr的平衡因子的絕對值 |bf| = 1。 }。 ptrright = subR。結(jié)點 A的平衡因子變?yōu)?2，發(fā)生了不平衡。 else subLbf = 1。使之平衡化 。 //要右旋轉(zhuǎn)的結(jié)點 ptr = subRleft。 subLright = ptrleft。 單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn) , 其中一個是另一 個的鏡像，其方向與不平衡的形狀相關(guān)。 //先右后左雙旋 }。 void RotateL (AVLNodeE, K*amp。 Tree)。 e1) { return Remove (root, x, e1)。 } //構(gòu)造函數(shù) AVLTree (K Ref) { RefValue = Ref。 right = NULL。 ASLunsucc = *1+ *3+*3+*2 = 。同時，第 k 層有 2k1個結(jié)點， k = 1, 2, ? 。nA S L0(11 ).1][65 ? 設(shè)樹中所有內(nèi) 、 外部結(jié)點的搜索概率都相等： p[i]