【正文】 earch(bstlist t,keytype k) { bstlist p 。 /*左右孩子指針域 */ }bstnode。 /*關(guān)鍵字域 */ elemtype other。 ?又如檢索 k=15的記錄時(shí) ， 由于 15小于根結(jié)點(diǎn) 50， 在其左子樹繼續(xù)檢索； 15又小于左子樹的根結(jié)點(diǎn) 40， 繼續(xù)在當(dāng)前根結(jié)點(diǎn) 40的左子樹中檢索； 15也小于當(dāng)前根結(jié)點(diǎn) 40的左子樹的根結(jié)點(diǎn) 20， 當(dāng)在 20的左子樹中繼續(xù)檢索時(shí)發(fā)現(xiàn) 20的左子樹為空 ， 檢索失敗返回 NULL。 二叉檢索樹的檢索過程 ? 如果把檢索表中各記錄按關(guān)鍵字值大小組織為上述的二叉檢索樹 ， 則檢索關(guān)鍵字值等于給定值 k的記錄的過程為： ⑴ 若二叉檢索樹為空 ， 檢索失敗 ， 返回特定值 NULL； ⑵ 若二叉檢索樹非空 ， 用給定值 k與根結(jié)點(diǎn)的關(guān)鍵字值比較： ① 相等時(shí) ， 檢索成功 ， 返回指向當(dāng)前根結(jié)點(diǎn)的指針； ② k小時(shí) ， 繼續(xù)在根的左子樹中檢索 ， 即轉(zhuǎn) ⑴ ； ③ k大時(shí) ， 繼續(xù)在根的右子樹中檢索 ， 即轉(zhuǎn) ⑴ 。 樹表的檢索 二叉檢索樹 二叉檢索樹的平衡性調(diào)整 B樹和 B+樹 ?二叉檢索樹 （ binary search tree） ， 又稱作二叉排序樹 （ binary sort tree） ；它或者是一棵空樹 ， 或者是具有下列性質(zhì)的二叉樹： ?若左子樹不空 ， 則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； ?若右子樹不空 ， 右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； ?其左 、 右子樹也都是二叉檢索樹 。 第 7章 檢索及基本算法 檢索的概念 線性表的檢索 樹表的檢索 哈希檢索 樹表的檢索 ?在上一節(jié)介紹的線性表的檢索 ， 主要討論了檢索表為順序表和有序表的幾種檢索方法；由于順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn) ， 不適用于對(duì)檢索表中的記錄多做插入和刪除操作 ， 所以統(tǒng)稱作 靜態(tài)檢索 。 例如當(dāng) n＝ 1024時(shí) ， ， 分塊檢索 、 順序檢索和二分法檢索的平均檢索長度分別如下： 精算點(diǎn)檢索算法分析（續(xù)） ?若用二分法檢索確定所在的塊 ， 則分塊檢索的平均檢索長度為： ?其平均檢索長度 ASL仍是介于二分法檢索和順序檢索之間 。 即 。 ?若順序檢索確定所在的塊 ， 則分塊檢索的平均檢索長度為： 精算點(diǎn)檢索算法分析（續(xù)） ?由上式可知 ， ASL不僅與檢索表的長度 n有關(guān) ， 而且和每一塊中的記錄個(gè)數(shù) s有關(guān) 。 精算點(diǎn)檢索算法分析（續(xù)） ? 一般情況下 ， 為了分塊檢索 ， 把長度為 n的檢索表均勻分成 b塊 ， 每塊含 s個(gè)記錄 ， 即 。 精算點(diǎn)檢索算法分析 ?由分塊檢索的思想可知 ， 分塊檢索算法是對(duì)索引表的二分法檢索或順序檢索和對(duì)塊中檢索的順序檢索這兩部分檢索算法的簡單合成 。 精算點(diǎn)檢索舉例 ?例如 ， 要在前例 “ 塊間升序的檢索表及其索引表示例 ” 中檢索 k=38的記錄： ?先將 k依次和索引表中各個(gè)最大關(guān)鍵字進(jìn)行比較 ， 由于22k48， 所以 k=38的記錄若存在必在第二個(gè)塊中； ?然后從第二個(gè)塊的起始地址開始順序檢索 ， 直到R[10].key=k時(shí)檢索成功 。 精算點(diǎn)檢索的基本思想 ?分塊檢索的基本思想是： ?首先依據(jù)給定值在索引表中檢索 ， 以確定待查找記錄所屬的塊； ?由于索引表是有序表 ， 所以可以用二分法檢索 ，也可以用順序檢索或其它檢索方法進(jìn)行 。 精算點(diǎn)檢索算法分析（續(xù)） ?下圖中給出了一張塊間降序的檢索表的索引表 ， 每個(gè)塊在索引表中也是一個(gè)索引項(xiàng) ， 但索引項(xiàng)中包含的是塊中最小的關(guān)鍵字值和該塊第一個(gè)記錄在檢索表中的位置 。 如下圖給出了一張塊間升序的檢索表的索引表 ， 每個(gè)塊在索引表中有一個(gè)索引項(xiàng) ， 每個(gè)索引項(xiàng)中包含有該塊中最大的關(guān)鍵字值和該塊第一個(gè)記錄在檢索表中的位置 。 ?在塊間升序時(shí) ， 每一塊中所有記錄的關(guān)鍵字值均大于和該塊相鄰的前一塊中最大的關(guān)鍵字值； ?在塊間降序時(shí) ， 每一塊中所有記錄的關(guān)鍵字值均小于和該塊相鄰的前一塊中最小的關(guān)鍵字值 。 ?即分塊檢索要求檢索表的 特點(diǎn) 是：塊間有序 ， 塊內(nèi)無序 。 線性表的檢索 順序檢索 二分法檢索 黃金分割點(diǎn)檢索 精算點(diǎn)檢索 分塊檢索 精算點(diǎn)檢索算法分析 ? 分塊檢索 （ blocking search） ， 又稱作索引檢索 ，它是順序檢索的一種改進(jìn)方法 ， 其效率介于順序檢索和二分法檢索之間 。 /*檢索成功返回位置 */ else return 0。 /*若給定值大于 mid時(shí)在 mid后檢索 */ while(R[mid].keyk) /*向后順序檢索 */ mid++。 /*檢索成功返回位置 */ else return 0。 while(R[mid].keyk) mid。 if(k==R[mid].key) return mid。 high=n。 精算點(diǎn)檢索算法描述 ?這種與順序檢索相結(jié)合的精算點(diǎn)檢索算法可描述如下： int precisesearch(sqlist R[],keytype k) {int low,mid,high。 精算點(diǎn)檢索舉例（續(xù)） ?既然在關(guān)鍵字值分布較均勻時(shí) ， 即使一次比較不能檢索成功也會(huì)在 mid位置附近 ， 在算法設(shè)計(jì)時(shí)就只需一次計(jì)算 mid的值 。 ?如果關(guān)鍵字值 分布不均勻 ， 可縮小檢索區(qū)間繼續(xù)用前面的估算公式確定檢索點(diǎn)檢索 ， 其檢索性能也優(yōu)于黃金分割點(diǎn)檢索和二分法檢索 。 精算點(diǎn)檢索（續(xù)） ?當(dāng)關(guān)鍵字值分布均勻時(shí)應(yīng)滿足下式： ?其中 k為給定值 ， mid為估算位置 ， low和 high分別為檢索區(qū)間下界和上界位置 ， 經(jīng)整理可得估算公式為： ?當(dāng)給定值 k等于 R[mid].key則檢索成功；否則若kR[mid].key則在 mid之前檢索 ， 若 kR[mid].key則在 mid之后檢索 。 ?所謂 精算點(diǎn)檢索 （ precise puting search） ，也稱作插值檢索 。 ?然而 ， 檢索表的長度很難是某個(gè) Fibonacci數(shù)列或接近Fibonacci數(shù)的值；其次即就是 Fibonacci數(shù) ， 也還得為Fibonacci檢索準(zhǔn)備一張 Fibonacci數(shù)表或通過循環(huán)遞推求出每次要用的 Fibonacci數(shù) ， 所以說利用 Fibonacci數(shù)列設(shè)計(jì)檢索算法不如直接使用黃金分割數(shù) 便 。 Fibonacci數(shù)列的定義為： 黃金分割點(diǎn)檢索（續(xù)） ?注意觀察 “ Fibonacci數(shù)列及其相鄰項(xiàng)的比值 ” 表中給出的F(n)/F(n+1)的值 ， 從 n=6之后基本上穩(wěn)定在 。} 黃金分割點(diǎn)檢索（續(xù)） ? 該算法的時(shí)間性能與二分法相比 ， 在平均性能上優(yōu)于二分法 ，但仍然是；在最壞情況下 ， 每次比較之后都在較大的區(qū)間內(nèi)繼續(xù)檢索 ， 比二分法差；在最好情況下 ， 每次比較之后都在小區(qū)間內(nèi)繼續(xù)檢索 ， 比二分法好 。 /*修改區(qū)間上界 */ else low=mid+1。 if(k==R[mid].key) return mid。 high=n。 黃金分割點(diǎn)檢索算法描述 int goldpartsearch(sqlist R[],keytype k) { int low,mid,high。 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 ↑ ↑ ↑ low=10 mid=13 high=15 ? 由于 k=46=R[13].key 檢索成功 。 給定值 k=4631=R[9].key， 在黃 金 點(diǎn) 之 后 的 區(qū) 間 繼 續(xù) 檢 索 。 ?通過黃金點(diǎn)逐次縮小檢索區(qū)間 ， 直到檢索成功 ，或區(qū)間已無記錄檢索失敗時(shí)止 。 它是利用我國著名數(shù)學(xué)家華羅庚院士當(dāng)年推廣優(yōu)選法時(shí)介紹的黃金分割點(diǎn)的概念 ， 即利用黃金分割數(shù) 。 ?二分法檢索只適用于檢索表為順序存儲(chǔ)結(jié)構(gòu)之下的有序表 ， 即這種較高的檢索效率是以對(duì)檢索表預(yù)先按關(guān)鍵字值大小排序?yàn)榇鷥r(jià)的 ， 所以二分法檢索適合于一旦建立很少變動(dòng)而又需要經(jīng)常檢索的檢索表 。 因此檢索失敗時(shí)和給定值的比較次數(shù)也是最多不超過 次 。 二分法檢索過程分析（續(xù)） ?二分法檢索在檢索失敗時(shí)走了一條從二叉樹根結(jié)點(diǎn)到方形結(jié)點(diǎn)的路徑和給定值的比較次數(shù)等于路徑上結(jié)點(diǎn) （ 不含方形結(jié)點(diǎn) ） 的個(gè)數(shù) 。 ?具有 n個(gè)結(jié)點(diǎn)的完全二叉樹深度為 ， 所以二分法檢索在檢索成功時(shí)的比較次數(shù)至多為 次 。 二分法檢索算法分析 ?因此 ， 二分法檢索在檢索成功時(shí)給定值與關(guān)鍵字的比較次數(shù)不超過二叉樹的深度 。 } 二分法檢索過程分析 ? 為了分析二分法檢索算法的性能 ， 我們先注意前述 15個(gè)元素的檢索表的檢索過程：為了找到第 8個(gè)記錄僅需一次比較；為了找到第 4， 12個(gè)記錄需二次比較；為了找到第 2， 6，10， 14個(gè)記錄需要三次比較；為了找到第 1， 3， 5， 7， 9，11， 13， 15個(gè)記錄需四次比較 。 else low =mid+1。 if(k==R[mid].key) return mid。 high=n。 二分法檢索過程可用 C語言描述 ?二分法檢索過程可用 C語言描述為如下算法： int binarysearch (sglist R[],keytype k) { int low,mid,high。 二分法檢索舉例 —— 檢索 k=46 ?檢索 46的過程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 ↑ ↑ ↑ low=1 mid=8 high=15 ?由于 k=4629=R[8].key， 所以應(yīng)在右半?yún)^(qū)繼續(xù)檢索；此時(shí) low=mid+1=8+1=9， mid= (9+15)/2=12， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 ↑ ↑ ↑ low=9 mid=12 high=15 ?由于 k=4642=R[14].key， 所以應(yīng)在當(dāng)前區(qū)間的右半?yún)^(qū)繼續(xù)檢索； 二分法檢索舉例 — 檢索 k=46(續(xù) ) ?此時(shí) low=12+1 =13， mid=(13+15)/2=14， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 ↑ ↑ ↑ low=13mid=14high=15 ?由于 k=4649=R[14].key， 所以應(yīng)在當(dāng)前區(qū)間的左半?yún)^(qū) 繼 續(xù) 檢 索 ； 此 時(shí) high=mid1= 141=13 ，mid=(13+13)/2=13， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 ↑ low=13 mid=13