【文章內容簡介】 檢索成功；又如檢索 k=29 時 ， ， 一次比較R[n].key=29等于給定值檢索成功；再如檢索 k=46時 ， ， 一次比較 R[13].key=46等于給定值檢索成功；等等 。 精算點檢索舉例（續(xù)） ?既然在關鍵字值分布較均勻時 ， 即使一次比較不能檢索成功也會在 mid位置附近 ， 在算法設計時就只需一次計算 mid的值 。 ?若 k=R[mid].key， 則一次比較檢索成功； ?若 kR[mid].key， 則可由 mid前一個記錄開始向前順序檢索 ， 直到檢索成功或某個記錄的關鍵字值小于給定值 k時檢索失??； ?若 kR[mid].key， 則可由 mid后一個記錄開始向后順序檢索 ， 直到檢索成功或某個記錄的關鍵字值大于給定值 k時檢索失敗 。 精算點檢索算法描述 ?這種與順序檢索相結合的精算點檢索算法可描述如下： int precisesearch(sqlist R[],keytype k) {int low,mid,high。 low=1。 high=n。 mid=low+(kR[low].key)*(highlow)/ (R[high].keyR[low].key)+。 if(k==R[mid].key) return mid。 else if(kR[mid].key) {mid。 while(R[mid].keyk) mid。 精算點檢索算法描述（續(xù)） if(R[mid].key==k) return mid。 /*檢索成功返回位置 */ else return 0。 /*檢索失敗返回 0*/ } else {mid++。 /*若給定值大于 mid時在 mid后檢索 */ while(R[mid].keyk) /*向后順序檢索 */ mid++。 if(R[mid].key==k) return mid。 /*檢索成功返回位置 */ else return 0。 /*檢索失敗返回 0*/ } } 精算點檢索算法分析 ?該算法中的兩個當型循環(huán) ， 在關鍵字值分布較均勻的情況下 ， 檢索長度與檢索表的長度 n無關 ， 平均檢索長度趨近于某個常數(shù)； ?在關鍵字值分布不均勻的情況下 ， 檢索長度在最壞的情況下也不會超過二分法檢索和黃金分割點檢索； ?精算點檢索是平均性能最好的檢索方法 ， 對于檢索表較大和分布較均勻時 ， 使用精算點檢索特別合適 。 線性表的檢索 順序檢索 二分法檢索 黃金分割點檢索 精算點檢索 分塊檢索 精算點檢索算法分析 ? 分塊檢索 （ blocking search） ， 又稱作索引檢索 ，它是順序檢索的一種改進方法 ， 其效率介于順序檢索和二分法檢索之間 。 ? 分塊檢索不要求檢索表中所有記錄關鍵值有序排列 ， 但要求把檢索表分成若干塊之后各塊之間按關鍵字值大小有序 。 ?即分塊檢索要求檢索表的 特點 是：塊間有序 ， 塊內無序 。 ?所謂塊間有序是指塊間升序或塊間降序 。 ?在塊間升序時 ， 每一塊中所有記錄的關鍵字值均大于和該塊相鄰的前一塊中最大的關鍵字值； ?在塊間降序時 ， 每一塊中所有記錄的關鍵字值均小于和該塊相鄰的前一塊中最小的關鍵字值 。 精算點檢索算法分析（續(xù)） ? 在分塊檢索中 ， 除檢索表本身之外 ， 還需要建立一張索引表 。 如下圖給出了一張塊間升序的檢索表的索引表 ， 每個塊在索引表中有一個索引項 ， 每個索引項中包含有該塊中最大的關鍵字值和該塊第一個記錄在檢索表中的位置 。 ?本例中檢索表分為三塊 ， 各塊中最大關鍵字值依次為 248和 86， 各塊中第一個記錄在檢索表中的位置依次為 7和13；第二塊中的最小關鍵字值 24大于第一塊中的最大關鍵字值 22， 第三塊中的最小關鍵字值 49大于第二塊中的最大關鍵字值 48。 精算點檢索算法分析（續(xù)） ?下圖中給出了一張塊間降序的檢索表的索引表 ， 每個塊在索引表中也是一個索引項 ， 但索引項中包含的是塊中最小的關鍵字值和該塊第一個記錄在檢索表中的位置 。 ?該例中檢索表分為四塊 ， 各塊中最小關鍵字值依次為 43 22和 9， 各塊中第一個記錄在檢索表中的位置依次是 11和 16；第二塊中的最大關鍵字值 45小于第一塊中最小的關鍵字值 47， 第三塊中的最大關鍵字值 31小于第二塊中的最小關鍵字值 32， 第四塊中的最大關鍵字值 20小于第三塊中最小的關鍵字值 22。 精算點檢索的基本思想 ?分塊檢索的基本思想是： ?首先依據(jù)給定值在索引表中檢索 ， 以確定待查找記錄所屬的塊； ?由于索引表是有序表 ， 所以可以用二分法檢索 ，也可以用順序檢索或其它檢索方法進行 。 ?然后在確定的塊內檢索關鍵字值等于給定值的記錄 ， 由于塊內記錄無序排列 ， 所以只能用順序檢索方法進行 。 精算點檢索舉例 ?例如 ， 要在前例 “ 塊間升序的檢索表及其索引表示例 ” 中檢索 k=38的記錄： ?先將 k依次和索引表中各個最大關鍵字進行比較 ， 由于22k48， 所以 k=38的記錄若存在必在第二個塊中； ?然后從第二個塊的起始地址開始順序檢索 ， 直到R[10].key=k時檢索成功 。 ?再如檢索 k=76的記錄： ?將 k和索引表中各個最大關鍵字值比較 ， 由于 48k86，故 k=76的記錄若存在必在第三個塊中； ?從第三個塊的起始地址開始順序檢索 ， 直到和塊中最后一個記錄的關鍵字 R[18].key比較都不等于 k時檢索失敗 。 精算點檢索算法分析 ?由分塊檢索的思想可知 ， 分塊檢索算法是對索引表的二分法檢索或順序檢索和對塊中檢索的順序檢索這兩部分檢索算法的簡單合成 。 ?由于分塊檢索是由索引表檢索和塊內檢索兩部分合成 ， 所以分塊檢索的平均檢索長度為： ?其中： Lb是為確定所在塊對索引表的平均檢索長度 ，Lw是在塊內檢索記錄的平均檢索長度 。 精算點檢索算法分析（續(xù)） ? 一般情況下 ， 為了分塊檢索 ， 把長度為 n的檢索表均勻分成 b塊 ， 每塊含 s個記錄 ， 即 。 再假定對檢索表中各記錄的檢索是等概率的 ， 即塊檢索概率為 1/b， 塊中記錄的檢索概率為 1/s。 ?若順序檢索確定所在的塊 ， 則分塊檢索的平均檢索長度為： 精算點檢索算法分析（續(xù)） ?由上式可知 ， ASL不僅與檢索表的長度 n有關 ， 而且和每一塊中的記錄個數(shù) s有關 。 在給定 n的前提下 s是可以選擇的；當選取 時 ， ASL具有最小值 。 即 。 這個值比順序檢索有了很大的改進 ， 但遠不及二分法檢索 。 例如當 n＝ 1024時 ， ， 分塊檢索 、 順序檢索和二分法檢索的平均檢索長度分別如下： 精算點檢索算法分析（續(xù)） ?若用二分法檢索確定所在的塊 ， 則分塊檢索的平均檢索長度為： ?其平均檢索長度 ASL仍是介于二分法檢索和順序檢索之間 。 ?如當 n＝ 1024時 ， ?最后對分塊檢索需要說明的是 ， 為了提高檢索效率 ， 要盡可能把塊劃分均勻；在實際應用中 ， 要依據(jù)檢索表的具體情況來劃分塊的大小 ， 不一定要做到塊的大小相同 ， 只要滿足塊間有序即可 。 第 7章 檢索及基本算法 檢索的概念 線性表的檢索 樹表的檢索 哈希檢索 樹表的檢索 ?在上一節(jié)介紹的線性表的檢索 ， 主要討論了檢索表為順序表和有序表的幾種檢索方法；由于順序存儲結構的特點 ， 不適用于對檢索表中的記錄多做插入和刪除操作 ， 所以統(tǒng)稱作 靜態(tài)檢索 。 ?本節(jié)討論的樹表檢索屬于 動態(tài)檢索 ， 其 特點 是檢索表本身是在檢索過程中動態(tài)生成的；即若檢索表中存在關鍵字值等于給定值 k的記錄 ， 則檢索成功返回 ， 否則在檢索表中插入關鍵字值等于 k的記錄 。 樹表的檢索 二叉檢索樹 二叉檢索樹的平衡性調整 B樹和 B+樹 ?二叉檢索樹 （ binary search tree） ， 又稱作二叉排序樹 （ binary sort tree） ；它或者是一棵空樹 ， 或者是具有下列性質的二叉樹： ?若左子樹不空 ， 則左子樹上所有結點的值均小于根結點的值； ?若右子樹不空 ， 右子樹上所有結點的值均大于根結點的值； ?其左 、 右子樹也都是二叉檢索樹 。 二叉檢索樹舉例 ?如下圖給出的就是一棵二叉檢索樹 ， 它滿足二叉檢索樹的定義；對該二叉檢索樹中序遍歷得到結點序列 4 50、 5 70、 7 80，是一個結點的有序序列 。 二叉檢索樹的檢索過程 ? 如果把檢索表中各記錄按關鍵字值大小組織為上述的二叉檢索樹 ， 則檢索關鍵字值等于給定值 k的記錄的過程為： ⑴ 若二叉檢索樹為空 ， 檢索失敗 ， 返回特定值 NULL； ⑵ 若二叉檢索樹非空 ， 用給定值 k與根結點的關鍵字值比較： ① 相等時 ， 檢索成功 ， 返回指向當前根結點的指針； ② k小時 ， 繼續(xù)在根的左子樹中檢索 ， 即轉 ⑴ ； ③ k大時 ， 繼續(xù)在根的右子樹中檢索 ， 即轉 ⑴ 。 二叉檢索樹的檢索過程舉例 ?例如 ， 在右圖所示二叉檢索樹中檢索 k=80的記錄 ， 先用 80和根 50比較 ， 8050則在右子樹中繼續(xù)檢索；再用 80和右子樹的根 70比較 ， 8070則繼續(xù)在當前根結點 70的右子樹中檢索；當再次和新的當前根結點比較時二者相等檢索成功 ， 返回指向當前根結點的指針 。 ?又如檢索 k=15的記錄時 ， 由于 15小于根結點 50， 在其左子樹繼續(xù)檢索； 15又小于左子樹的根結點 40， 繼續(xù)在當前根結點 40的左子樹中檢索； 15也小于當前根結點 40的左子樹的根結點 20， 當在 20的左子樹中繼續(xù)檢索時發(fā)現(xiàn) 20的左子樹為空 ， 檢索失敗返回 NULL。 二叉檢索樹的二叉鏈表類型 ? 設二叉檢索樹以如下描述的二叉鏈表作為存儲結構： typedef struct node {keytype key。 /*關鍵字域 */ elemtype other。 /*其它數(shù)據(jù)域 */ struct node *lchild, *rchild。 /*左右孩子指針域 */ }bstnode。 /*定義結點類型 bstnode*/ typedef bstnode *bstlist。 /*定義二叉檢索樹表類型 bstlist*/ 二叉檢索樹的檢索算法描述 ? 二叉檢索樹的檢索算法可描述如下： bstlist bstsearch(bstlist t,keytype k) { bstlist p 。 p=t。 if((p==NULL)||(pkey==k)) return p。 else if(pkeyk) return bstsearch(prchild,k)。 else return bstsearch(plchild,k)。 } /*bstsearch end*/ ?對于一組關鍵字無序的記錄 ， 構造其相應的二叉檢索樹的方法是：從一棵空的二叉檢索樹開始 ， 每當讀入一個記錄就生成一個結點 ， 然后按關鍵字值的大小插入到當前的二叉檢索樹之中；當所有記錄的結點都已插入二叉檢索樹中時便構造完畢 。 ?雖然 ， 插入操作是構造二叉檢索樹的關鍵操作 。 要保證在一棵二叉檢索樹中插入一個結點之后 ， 仍然滿足二叉檢索樹的定義 。 其插入過程為： ?若二叉檢索樹為空 ， 則插入結點作為新的根結點； ?若二叉檢索樹非空 ， 則在非空的二叉檢索樹中檢索插入結點；如果檢索成功就不必插入 ， 否則插入結點作為新的葉結點 ， 并成為檢索路徑上最后一個結點的左孩子或右孩子 。 二叉檢索樹