《算法與數據結構》第7章檢索及基本算法ppt.ppt

《《算法與數據結構》第7章檢索及基本算法ppt.ppt》由會員分享，可在線閱讀，更多相關《《算法與數據結構》第7章檢索及基本算法ppt.ppt（160頁珍藏版）》請在裝配圖網上搜索。

1、算法與數據結構 第 7章 檢索及基本算法 第 7章 檢索及基本算法 7.1 檢索的概念 7.2 線性表的檢索 7.3 樹表的檢索 7.4 哈希檢索 檢索的概念 檢索 （ searching） 也稱作查找 ， 是一種常用的基本 運算 。 人們幾乎每天都要做檢索的工作 ， 如在電話號碼薄 中查找某單位或某個人的電話號碼 ， 在字典中查找 某個詞的含義或讀法 ， 在圖書館查找某本書刊的編 號 ， 上網在各種數據庫中查找某些需要的文獻資料 等等 。 在語言翻譯的編譯程序中要對符號表查找 ， 在數據 庫系統(tǒng)中要用 SQL語言為各種應用設計查找程序 ， 如此等等 。 檢索的概念 (續(xù) ) 簡言之 ， 檢索

2、 就是在 “ 大量信息 ” 中查找一個 “ 特定的 ” 信息 。 這里的大量信息是檢索所依賴的數據結構 ， 稱之 為 檢索表 （ search table） ； 檢索表是由同一類型的數據元素 （ 或記錄 ） 組成 的集合 。 由于集合是一種松散型數據結構 ， 數據元素除了 同屬于一個集合外再無別的關系 ， 所以檢索表是 一種非常靈活的數據結構 。 檢索的概念 (續(xù) ) 對檢索表常做的運算和操作有： 查找某個特定的數據元素是否在檢索表中； 檢索某個特定的數據元素的各種屬性； 在檢索表中插入一個數據元素； 從檢索表中刪去某個數據元素 。 若對查找表只作前兩種統(tǒng)稱為 “ 檢索 ” 的操作 ， 稱 此

3、類檢索表為 靜態(tài)檢索表 （ static search table） ； 若在檢索的過程中同時插入表中不存在的數據元素 ， 或者從檢索表中刪除已存在的某個數據元素 ， 稱此 類檢索表為 動態(tài)檢索表 （ dynamic search table） 。 檢索的概念 (續(xù) ) 所謂 特定的信息 ， 是指關鍵字值等于給定值的信 息 ， 信息的單位是數據元素或記錄 。 關鍵字 （ key） 是數據元素 （ 或記錄 ） 中某個數據 項的值 ， 用它可以標識一個數據元素 （ 或記錄 ） 。 顯然 ， 在一個記錄中的每個數據項都可以作為標識 該記錄的關鍵字 。 如人事檔案記錄結構為： 它含有五個關鍵字 ， 其

4、中性別這個關鍵字標識了 一個職工的性別情況 。 檢索的概念 (續(xù) ) 主關鍵字 （ primary key） 是指能惟一標識一個 數據元素 （ 或記錄 ） 的關鍵字 。 如上述記錄中身 份證號碼是主關鍵字 ， 可以惟一標識一條記錄； 而姓名 、 性別 、 年齡 、 工資級別不能惟一標識一 條記錄 ， 它們都不是主關鍵字 。 輔關鍵字 （ secondary key） 是用以標識若干數 據元素 （ 或記錄 ） 的關鍵字 ， 也稱作次關鍵字或 從關鍵字 。 如上述記錄中的姓名 、 性別 、 年齡 、 工資級別都是輔關鍵字 。 檢索的概念 (續(xù) ) 檢索 ， 就是根據給定的某個值 ， 在檢索表中查找

5、 一個關鍵字等于給定值的記錄的運算或操作 。 若在檢索表中存在這樣的記錄 ， 則稱 檢索成功 ， 檢索的結果是找到記錄的全部信息 （ 或找到記錄 在檢索表中的位置 ） ； 若檢索表中不存在關鍵字值等于給定值的記錄 ， 則稱 檢索失敗 ， 給出在檢索表中無要查找的記錄 的信息提示 ， 并在動態(tài)檢索時插入關鍵字等于給 定值的記錄于檢索表中 。 檢索的概念 (續(xù) ) 在檢索表中查找某個數據元表 （ 或記錄 ） 的過程 ， 依賴于這個數據元表 （ 或記錄 ） 在查找表中所處 的位置；對檢索表的檢索方法取決于檢索表中數 據元表 （ 或記錄 ） 的組織策略 。 如在字典中查找一個英文單詞 ， 由于字典是按

6、字母順 序編排的 ， 所以不需從第一個單詞順序查找 ， 而只是 按待查單詞中每個字母在字母表中的位置快速找到該 單詞； 而在數據元素 （ 或記錄 ） 之間無任何關系組織起 來的集合中查找 ， 則需要從第一個元素 （ 或記錄 ） 開始依次順序查找 。 檢索的概念 (續(xù) ) 在計算機中進行檢索是對已存入計算機中的數據 進行檢索 ， 取決于采用何種數據結構來組織檢索 表；往往需要在數據元素 （ 或記錄 ） 之間人為地 加上一些關系 ， 即用非集合結構如數組 、 文件 、 二叉樹 、 散列表等結構來組織檢索表 ， 以便按某 種規(guī)律來進行檢索 。 依數據組織方式不同 ， 檢索分為 線性表檢索 、 樹 表

7、檢索 和 散列表檢索 等 。 衡量一個檢索算法的優(yōu)劣 ， 主要依據在檢索過程 中給定值和關鍵字的比較操作次數 。 為此 ， 我們 引入 平均檢索長度 的概念 。 平均檢索長度 檢索算法的 平均檢索長度 （ average search length） ， 即在檢索過程中用給定值和關鍵字進 行比較的平均比較次數 ， 或者說是為找到具有給定值關鍵字的記錄所需 要的比較次數的平均值 。 它是為確定記錄在檢索表中的位置 ， 需要和給 定值進行比較的關鍵字個數的期望值 。 平均檢索長度（續(xù)） 對于含有 n個記錄的檢索表 ， 檢索成功時的平均 檢索長度為 其中 ， Pi為檢索第 i個記錄的概率 ， 且 ；

8、 一般在不特殊說明的情況下均認為是等概率 ， 即 檢索每個記錄的概率相等 ， 。 Ci為找到第 i個記錄需要和給定值比較的關鍵字的 個數 ， 它隨檢索方法的不同而不同 。 第 7章 檢索及基本算法 7.1 檢索的概念 7.2 線性表的檢索 7.3 樹表的檢索 7.4 哈希檢索 線性表的檢索 在檢索表的數據組織方式中 ， 線性表是最基本的 ， 也是最常用的一種組織方式 。 本節(jié)主要討論在順序 存儲結構實現的線性表上的檢索算法 ， 其類型定義 描述為 typedef struct keytype key; /*關鍵字類型 */ elemtype other; /*其它域 */ sqlist; sq

9、list Rn+1; /*順序表 */ 本節(jié)介紹的線性表檢索方法有 順序檢索 、 二分法檢 索 、 黃金點檢索 、 精算點檢索 和 分塊檢索 等 。 7.2 線性表的檢索 7.2.1 順序檢索 7.2.2 二分法檢索 7.2.3 黃金分割點檢索 7.2.4 精算點檢索 7.2.5 分塊檢索 順序檢索 順序檢索 （ sequential search） 是一種最簡單的基 本檢索方法 。 其基本思路為： 從表的一端開始 ， 用給定值逐個與表中各記錄的關鍵字 值比較 。 若找到某個關鍵字值等于給定值的記錄 ， 則檢索成功 ， 并給出該記錄在表中的位置； 若檢索完整個表仍未找到關鍵字值等于給定值的記錄

10、 ， 則檢索失敗 ， 并給出失敗信息 。 順序檢索方法既適用于線性表的 順序存儲結構 ， 也適用于線性表的 鏈式存儲結構 。 順序檢索舉例 以順序存儲結構為例 ， 設數據元素存放在數組中 下標從 1到 n的記錄中 ， 0號記錄位置留作監(jiān)視哨 ， 從下標為 n的一端開始向另一端檢索 ， 順序檢索算 法可描述如下： int seqsearch(sqlist R,keytype k) int i=n; R0.key=k; /*設置 R0為監(jiān)視哨 */ while(Ri.key != k) i-; return i; /*返回檢索結果 i*/ 順序檢索舉例（續(xù)） 算法中設置 監(jiān)視哨 R0， 可以使得在

11、檢索成功和 檢索失敗時的處理一致 ， 在檢索失敗時也能在監(jiān)視 哨位置找到關鍵字值為 k的記錄 ， 可省去在 while循 環(huán)中的位置越界檢查 （ i=1） 。 若從 R0處向后順序檢索 ， 監(jiān)視哨可設置在 Rn處 。 算法執(zhí)行之后 ， 非 0的函數值表示待查找記錄在數 組中的位置 （ 下標 ） ；若函數值為 0說明檢索表中 沒有要查找的記錄 。 順序檢索（續(xù)） 對于具有 n個記錄的檢索表 ， 若待查找記錄在 Rn 處 ， 需要和給定值 k比較一次 ， 即 Cn=1； 若待查找記錄在 Rn-1處 ， 需要和給定值 k比較兩 次 ， 即 Cn-1=2； 一般地 ， 若待查找記錄在 Ri處 ， 需和

12、給定值 k比 較 n-i+1次 ， 即 Ci=n-i+1。 因此 ， 在等概率的情況下順序檢索的平均檢索長 度為 順序檢索（續(xù)） 在檢索成功時順序檢索的平均比較次數約為 表長 的一半 。 在檢索失敗時 ， 順序檢索需要進行 n+1次的比較 。 當 n很大時 ， 平均檢索長度也很大 ， 檢索效率較低 ， 這是順序檢索的主要缺點 。 但由于順序檢索對表的存儲結構和元素存放次序 沒有要求 ， 且算法簡單 ， 在許多實際應用中常被 采用 。 7.2 線性表的檢索 7.2.1 順序檢索 7.2.2 二分法檢索 7.2.3 黃金分割點檢索 7.2.4 精算點檢索 7.2.5 分塊檢索 二分法檢索 二分法檢

13、索 （ binary search） ， 也稱作折半檢索 ， 它是一種效率較高的檢索方法 。 它要求檢索表是用 順序存儲結構表示 ， 且數據元素的存放要按關鍵字 值有序排列 。 二分法檢索的基本思想是： 在有序表中先取中間位置作為比較對象 ， 若給定值與中 間記錄的關鍵字值相等 ， 則檢索成功； 若給定值小于中間記錄的關鍵值則在表的左半區(qū)查找 ， 若給定值大于中間記錄的關鍵字值則在表的右半區(qū)查找 。 就這樣經過一次的比較縮小一半的檢索區(qū)間 ， 在每一個 檢索區(qū)間都是選取中間位置作為比較對象 ， 不斷地重復這 樣的檢索過程直到檢索成功 ， 或者檢索區(qū)間已無記錄時檢 索失敗 。 二分法檢索舉例 例

14、如 ：已知一個含 15個記錄的有序表 ， 其關鍵字序 列如下： （ 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52） 現在要檢索給定值 k為 19、 46和 11的記錄 ， 其檢索 過程如下： 用 low和 high分別表示檢索區(qū)間的下界和上界； 用 mid指示中間位置 ， 即 mid=(low +high)/2； 檢索開始時 low=1， high=n；即檢索區(qū)間為 1， n。 二分法檢索舉例 檢索 k=18 檢索 k=18的過程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=8 hi

15、gh=15 檢索開始時 ， low=1， high=15， mid=(1+15)/2=8。 由于 k=1829=R8.key， 所以應在右半區(qū)繼續(xù)檢索； 此時 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=R14.key， 所以應在當前區(qū)間的右 半區(qū)繼續(xù)檢索； 二分法檢索舉例 檢索 k=46(續(xù) ) 此時 low=12+1 =13， mid=(13+15)/2=14， 即： 07 10 14 18 21 23 25

16、 29 31 35 38 42 46 49 52 low=13mid=14high=15 由于 k=4649=R14.key， 所以應在當前區(qū)間的左半 區(qū) 繼 續(xù) 檢 索 ； 此 時 high=mid-1= 14-1=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 high=13 由于 k=46=R13.key， 此時檢索 46成功 。 二分法檢索舉例 檢索 k=11 檢索 k=11的過程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49

17、 52 low=1 mid=8 high=15 由于 k=1129=R8.key， 應在左半區(qū)繼續(xù)檢索；此 時 high= mid-1=8-1=7， mid= (1+7)/2=4， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=4 high=7 由于 k=1110=R2.key， 應在當前區(qū)間的右半區(qū)繼 續(xù)檢索；此時 low=2+1=3， mid= (3+3)/2=3， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=3 mid=3 high=3 由于 k=1114=R

18、3.key， 應在當前區(qū)間的左半區(qū)繼 續(xù)檢索；此時 high=mid-1= 3-1=23=low， 左半區(qū)已 沒有元素 （ 不存在區(qū)間了 ） ， 檢索 k 11失敗 。 二分法檢索過程可用 C語言描述 二分法檢索過程可用 C語言描述為如下算法： int binarysearch (sglist R,keytype k) int low,mid,high; low=1; high=n; while(low=high) mid=(low+high)/2; if(k=Rmid.key) return mid; else if(k100， 則可有如下近似結果： 二分法檢索過程分析（續(xù)） 由此可見 ，

19、二分法檢索的效率比順序檢索高得多 ， 如 n=127時 ， 順序檢索 ASL 64而二分法則為 ASL 6。 二分法檢索只適用于檢索表為順序存儲結構之下 的有序表 ， 即這種較高的檢索效率是以對檢索表預 先按關鍵字值大小排序為代價的 ， 所以二分法檢索 適合于一旦建立很少變動而又需要經常檢索的檢索 表 。 7.2 線性表的檢索 7.2.1 順序檢索 7.2.2 二分法檢索 7.2.3 黃金分割點檢索 7.2.4 精算點檢索 7.2.5 分塊檢索 黃金分割點檢索 黃金分割點檢索 （ gold-partition search） ， 簡稱黃 金點檢索 。 它是利用我國著名數學家華羅庚院士當 年推廣

20、優(yōu)選法時介紹的黃金分割點的概念 ， 即利用 黃金分割數 0.618把檢索區(qū)間分為兩個不等的區(qū)間 。 每次用給定值與黃金點上的記錄的關鍵字比較 ， 若相等檢索成功 ， 若給定值小于黃金點關鍵字值 ， 繼續(xù)在黃金點之前的區(qū)間檢索；若給定值大于黃金 點關鍵字值 ， 繼續(xù)在黃金點之后的區(qū)間檢索 。 通過黃金點逐次縮小檢索區(qū)間 ， 直到檢索成功 ， 或區(qū)間已無記錄檢索失敗時止 。 黃金分割點檢索舉例 例如 ， 仍以前面的 15個記錄為例 ， 檢索 k 46的黃金分割點 檢索過程為： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=9 high

21、=15 開始時 low=1 ， high=15 ， mid=low+0.618*(high-low+1)- 1=1+0.618*(15-1+1)-1=9.329。 給定值 k=4631=R9.key， 在 黃 金 點 之 后 的 區(qū) 間 繼 續(xù) 檢 索 。 此時 low=9+1=10 ， mid=10+0.618*(15-10+1)-1=12.70813。 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=10 mid=13 high=15 由于 k=46=R13.key 檢索成功 。 一個用二分法檢索需 4次比 較的工作 ， 黃金分割點檢

22、索只需兩次比較就完成了 。 黃金分割點檢索算法描述 int goldpartsearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; while(low=high) /*逐次縮小區(qū)間檢索 */ mid=low+0.618*(high-low+1)-1+0.5; if(k=Rmid.key) return mid; else if(kRmid.key) high=mid-1; /*修改區(qū)間上界 */ else low=mid+1; /*修改區(qū)間下界 */ return 0; 黃金分割點檢索（續(xù)） 該算法的時間性能與二分法相比 ， 在平

23、均性能上優(yōu)于二分法 ， 但仍然是；在最壞情況下 ， 每次比較之后都在較大的區(qū)間內 繼續(xù)檢索 ， 比二分法差；在最好情況下 ， 每次比較之后都在 小區(qū)間內繼續(xù)檢索 ， 比二分法好 。 所謂 黃金分割點 ， 就是利用 Fibonacci數列對檢索表分割 得到的一系列位置 。 Fibonacci數列的定義為： 黃金分割點檢索（續(xù)） 注意觀察 “ Fibonacci數列及其相鄰項的比值 ” 表中給出的 F(n)/F(n+1)的值 ， 從 n=6之后基本上穩(wěn)定在 0.618處 。 因此 ， 我們可以對長度為 F(n)的檢索表 ， 第一次用 F(n-1) 處記錄的關鍵字同給定值比較；由 F(n-1)分割的

24、兩個區(qū)間的 長度分別為 F(n-2)-1和 F(n-3)， 又都可以利用 Fibonacci 數列找出新的分割點；如此一直進行下去 ， 就可獲得檢索成 功或失敗的結果 。 然而 ， 檢索表的長度很難是某個 Fibonacci數列或接近 Fibonacci數的值；其次即就是 Fibonacci數 ， 也還得為 Fibonacci檢索準備一張 Fibonacci數表或通過循環(huán)遞推求 出每次要用的 Fibonacci數 ， 所以說利用 Fibonacci數列設 計檢索算法不如直接使用黃金分割數 0.618設計檢索算法方 便 。 7.2 線性表的檢索 7.2.1 順序檢索 7.2.2 二分法檢索 7.

25、2.3 黃金分割點檢索 7.2.4 精算點檢索 7.2.5 分塊檢索 精算點檢索 對于有序的檢索表 ， 如果記錄的關鍵字值不僅有 序 ， 而且分布均勻或比較均勻 ， 我們能不能很快 地完成關鍵字值等于給定值記錄的檢索任務呢 ？ 回答是肯定的 ， 下面將要介紹的精算點檢索就可 以解決這個問題 。 所謂 精算點檢索 （ precise computing search） ， 也稱作插值檢索 。 它是利用檢索區(qū)間有序關鍵字 值范圍和給定值的大小比例關系估算檢索位置的 一種檢索方法 。 精算點檢索（續(xù)） 當關鍵字值分布均勻時應滿足下式： 其中 k為給定值 ， mid為估算位置 ， low和 high分

26、別 為檢索區(qū)間下界和上界位置 ， 經整理可得估算公式 為： 當給定值 k等于 Rmid.key則檢索成功；否則若 kRmid.key則 在 mid之后檢索 。 精算點檢索（續(xù)） 在關鍵字值均勻分布時 ， 如呈等差數列時一次比 較便可檢索成功；在關鍵字值分布比較均勻時 ， 若一次比較不能找到也會在 mid位置附近 ， 這兩種 情況的檢索長度與檢索表的大小 n無關 ， 所以稱之 為 精算點檢索 。 如果關鍵字值 分布不均勻 ， 可縮小檢索區(qū)間繼續(xù) 用前面的估算公式確定檢索點檢索 ， 其檢索性能 也優(yōu)于黃金分割點檢索和二分法檢索 。 精算點檢索舉例 例如 ， 對于前述的 15個記錄的檢索表 ， 檢索

27、 k=14 的記錄 ， low=1， high=15， ， R3.key=14等于給定值 ， 一次比較檢索成功；又如 檢索 k=29 時 ， ， 一次比較 Rn.key=29等于給定值檢索成功；再如檢索 k=46 時 ， ， 一次比較 R13.key=46 等于給定值檢索成功；等等 。 精算點檢索舉例（續(xù)） 既然在關鍵字值分布較均勻時 ， 即使一次比較不能 檢索成功也會在 mid位置附近 ， 在算法設計時就只需 一次計算 mid的值 。 若 k=Rmid.key， 則一次比較檢索成功； 若 kRmid.key， 則可由 mid后一個記錄開始向后 順序檢索 ， 直到檢索成功或某個記錄的關鍵字值大

28、 于給定值 k時檢索失敗 。 精算點檢索算法描述 這種與順序檢索相結合的精算點檢索算法可描述如下： int precisesearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; mid=low+(k-Rlow.key)*(high-low)/ (Rhigh.key-Rlow.key)+0.5; if(k=Rmid.key) return mid; else if(kk) mid-; 精算點檢索算法描述（續(xù)） if(Rmid.key=k) return mid; /*檢索成功返回位置 */ else return 0; /*檢索失敗

29、返回 0*/ else mid+; /*若給定值大于 mid時在 mid后檢索 */ while(Rmid.keyk) /*向后順序檢索 */ mid+; if(Rmid.key=k) return mid; /*檢索成功返回位置 */ else return 0; /*檢索失敗返回 0*/ 精算點檢索算法分析 該算法中的兩個當型循環(huán) ， 在關鍵字值分布較均 勻的情況下 ， 檢索長度與檢索表的長度 n無關 ， 平 均檢索長度趨近于某個常數； 在關鍵字值分布不均勻的情況下 ， 檢索長度在最 壞的情況下也不會超過二分法檢索和黃金分割點 檢索； 精算點檢索是平均性能最好的檢索方法 ， 對于檢 索表較

30、大和分布較均勻時 ， 使用精算點檢索特別 合適 。 7.2 線性表的檢索 7.2.1 順序檢索 7.2.2 二分法檢索 7.2.3 黃金分割點檢索 7.2.4 精算點檢索 7.2.5 分塊檢索 精算點檢索算法分析 分塊檢索 （ blocking search） ， 又稱作索引檢索 ， 它是順序檢索的一種改進方法 ， 其效率介于順序檢 索和二分法檢索之間 。 分塊檢索不要求檢索表中所有記錄關鍵值有序排 列 ， 但要求把檢索表分成若干塊之后各塊之間按關 鍵字值大小有序 。 即分塊檢索要求檢索表的 特點 是：塊間有序 ， 塊內無序 。 所謂塊間有序是指塊間升序或塊間降序 。 在塊間升序時 ， 每一塊

31、中所有記錄的關鍵字值均大于和 該塊相鄰的前一塊中最大的關鍵字值； 在塊間降序時 ， 每一塊中所有記錄的關鍵字值均小于和 該塊相鄰的前一塊中最小的關鍵字值 。 精算點檢索算法分析（續(xù)） 在分塊檢索中 ， 除檢索表本身之外 ， 還需要建立一張索引 表 。 如下圖給出了一張塊間升序的檢索表的索引表 ， 每個塊 在索引表中有一個索引項 ， 每個索引項中包含有該塊中最大 的關鍵字值和該塊第一個記錄在檢索表中的位置 。 本例中檢索表分為三塊 ， 各塊中最大關鍵字值依次為 22、 48和 86， 各塊中第一個記錄在檢索表中的位置依次為 1、 7和 13；第二塊中的最小關鍵字值 24大于第一塊中的最大關鍵字

32、值 22， 第三塊中的最小關鍵字值 49大于第二塊中的最大關鍵 字值 48。 精算點檢索算法分析（續(xù)） 下圖中給出了一張塊間降序的檢索表的索引表 ， 每個塊在 索引表中也是一個索引項 ， 但索引項中包含的是塊中最小的 關鍵字值和該塊第一個記錄在檢索表中的位置 。 該例中檢索表分為四塊 ， 各塊中最小關鍵字值依次為 47、 32、 22和 9， 各塊中第一個記錄在檢索表中的位置依次是 1、 6、 11和 16；第二塊中的最大關鍵字值 45小于第一塊中最小 的關鍵字值 47， 第三塊中的最大關鍵字值 31小于第二塊中的 最小關鍵字值 32， 第四塊中的最大關鍵字值 20小于第三塊中 最小的關鍵字值

33、 22。 精算點檢索的基本思想 分塊檢索的基本思想是： 首先依據給定值在索引表中檢索 ， 以確定待查找 記錄所屬的塊； 由于索引表是有序表 ， 所以可以用二分法檢索 ， 也可以用順序檢索或其它檢索方法進行 。 然后在確定的塊內檢索關鍵字值等于給定值的記 錄 ， 由于塊內記錄無序排列 ， 所以只能用順序檢 索方法進行 。 精算點檢索舉例 例如 ， 要在前例 “ 塊間升序的檢索表及其索引表示 例 ” 中檢索 k=38的記錄： 先將 k依次和索引表中各個最大關鍵字進行比較 ， 由于 22k48， 所以 k=38的記錄若存在必在第二個塊中； 然后從第二個塊的起始地址開始順序檢索 ， 直到 R10.ke

34、y=k時檢索成功 。 再如檢索 k=76的記錄： 將 k和索引表中各個最大關鍵字值比較 ， 由于 48k50則在右 子樹中繼續(xù)檢索；再用 80和右子樹的根 70比 較 ， 8070則繼續(xù)在當前根結點 70的右子樹 中檢索；當再次和新的當前根結點比較時二 者相等檢索成功 ， 返回指向當前根結點的指 針 。 又如檢索 k=15的記錄時 ， 由于 15小于根結 點 50， 在其左子樹繼續(xù)檢索； 15又小于左子 樹的根結點 40， 繼續(xù)在當前根結點 40的左子 樹中檢索； 15也小于當前根結點 40的左子樹 的根結點 20， 當在 20的左子樹中繼續(xù)檢索時 發(fā)現 20的左子樹為空 ， 檢索失敗返回 N

35、ULL。 二叉檢索樹的二叉鏈表類型 設二叉檢索樹以如下描述的二叉鏈表作為存儲結 構： typedef struct node keytype key; /*關鍵字域 */ elemtype other; /*其它數據域 */ struct node *lchild, *rchild; /*左右孩子指針域 */ bstnode; /*定義結點類型 bstnode*/ typedef bstnode *bstlist; /*定義二叉檢索樹表類型 bstlist*/ 二叉檢索樹的檢索算法描述 二叉檢索樹的檢索算法可描述如下： bstlist bstsearch(bstlist t,keytype k

36、) bstlist p ; p=t; if(p=NULL)|(p-key=k) return p; else if(p-keyrchild,k); else return bstsearch(p-lchild,k); /*bstsearch end*/ 2.二叉檢索樹的構造過程和插入操作 對于一組關鍵字無序的記錄 ， 構造其相應的二叉檢索 樹的方法是：從一棵空的二叉檢索樹開始 ， 每當讀入 一個記錄就生成一個結點 ， 然后按關鍵字值的大小插 入到當前的二叉檢索樹之中；當所有記錄的結點都已 插入二叉檢索樹中時便構造完畢 。 雖然 ， 插入操作是構造二叉檢索樹的關鍵操作 。 要保 證在一棵二叉檢索

37、樹中插入一個結點之后 ， 仍然滿足 二叉檢索樹的定義 。 其插入過程為： 若二叉檢索樹為空 ， 則插入結點作為新的根結點； 若二叉檢索樹非空 ， 則在非空的二叉檢索樹中檢索插入結 點；如果檢索成功就不必插入 ， 否則插入結點作為新的葉結 點 ， 并成為檢索路徑上最后一個結點的左孩子或右孩子 。 二叉檢索樹的構造過程和插入操作 (續(xù) ) 為了實現這一插入過程 ， 在二叉檢索樹非空時需要知 道檢索路徑上的最后一個結點位置 ， 才能夠準確地把 插入結點作為左孩子或右孩子插入二叉檢索樹中；為 此；需要在檢索過程中設一指針變量記下當前結點的 前趨 （ 即雙親 ） 結點位置 。 插入算法的形式化描述如下：

38、 bstlist insertbst(bstlist t,keytype k) bstlist s,p,q; if(t=NULLl) p=(bstlist)malloc(sigeof(bstnode); p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; return p; 二叉檢索樹的構造過程和插入操作 (續(xù) ) p=t; while(p!=NULL) q=p; if(p-key=k) /*檢索成功不必插入 */ return t; /*返回原二叉檢索樹 */ else if(p-keyrchild; else p=p-lchild; p

39、=(bstlist)malloc(sizeof(bstnode); 二叉檢索樹的構造過程和插入操作 (續(xù) ) p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; if(kq-key) q-rchild=p; else q-lchild=p; return t; 二叉檢索 (排序 )樹構造過程舉例 從空樹出發(fā)經過一系列的檢索插入操作之后 ， 就可生成一 棵 二叉檢索樹 。 一個無序序列可以通過構造一棵二叉檢索樹 而變成一個有序序列 （ 即中序遍歷次序序列 ） ， 構造的過程 就是對無序序列進行排序的過程 ， 所以又稱作 二叉排序樹 。 設關鍵

40、字序列為 （ 45， 22， 57， 18， 29， 92） ， 生成二叉 檢索樹 （ 即二叉排序樹 ） 的過程如下圖所示 。 3.二叉樹檢索樹的刪除操作 在二叉檢索樹中刪除一個結點 ， 相當于在檢索表中 刪除一個記錄 ， 不能把以待刪除結點為根結點的子樹 全部刪去 ， 并且要保證刪除某個結點后的二叉樹仍然 是一棵二叉檢索樹 。 下面 ， 我們分三種情況討論如何 在二叉檢索樹中刪除一個結點 。 待刪除結點是度為 0的葉子結點 刪除一個葉子結點 *p， 不破壞整棵樹的結構 ， 只 需將其雙親結點 *f與 *p之間相鏈接的指針域置為空即 可： f-lchild=NULL; 或 f-rchild=N

41、ULL; 二叉樹檢索樹的刪除操作（續(xù)） 待刪除結點是度為 1的單枝結點 即待刪除結點只有左子樹或只有右子樹的情況 ， 如下圖所 示 。 此時只需將待刪除結點 *p的惟一后繼結點 （ 左孩子或右 孩子 ） 直接鏈接到其雙親結點 *f的相應位置 （ 即左鏈域或右 鏈域 ） 上即可： (a) f-lchild=p-lchild; 或 (b) f-lchild=p-rchild; 或 (c) f-rchild=p-lchild; 或 (d) f-rchild=p-rchild; 二叉樹檢索樹的刪除操作（續(xù)） 待刪除結點是度為 2的雙枝結點 即待刪除結點既有左子樹又有右子樹的情況 ， 如下圖所 示 ，

42、為了保持二叉檢索樹的特性 ， 通常有如下四種做法 。 二叉樹檢索樹的刪除操作 方法一 方法一：找出待刪除結點 *p的中序前趨結點 *q， 把 *q的關鍵 字域和數據域的值賦給 *p的相應域 ， 即： p-key=q-key; p-other=q-other; 然后刪除其中序前趨結點 *q， 由于 *p的中序前趨 *q是 *p左子 樹上的最右下結點 ， 所以 *q必是葉子結點或單左枝結點 ， 如 下圖所示；其刪除方法見 和 。 二叉樹檢索樹的刪除操作 方法二 方法二：找出待刪除結點 *p的中序后繼結點 *q， 把 *q的關鍵 字域和數據域的值賦給 *p的相應域 ， 即： p-key=q-key;

43、 p-other=q-other; 然后刪除其中序后繼結點 *q。 由于 *p的中序后繼 *q是 *p右子 樹上的最左下結點 ， 所以 *q必是葉子結點或單右枝結點 ， 如 下圖所示；其刪除方法見 和 。 二叉樹檢索樹的刪除操作 方法三 方法三：將待刪除結點 *p的右子樹鏈接到它的中 序前趨結點 （ 即左子樹上的最右下結點 ） *q的右孩 子域上 ， 然后把它的左子樹直接鏈接到其雙親結點 *f的左 （ 或右 ） 孩子域上 。 即： q-rchild=p-rchild; f-lchild（ 或 f-rchild） =p-lchild; 二叉樹檢索樹的刪除操作 方法四 方法四：將刪除結點 *p的左

44、子樹鏈接到它的中序 后繼 （ 即右子樹上的最左下結點 ） *q的左孩子域上 ， 然后把它的右子樹直接鏈接到其雙親結點 *f的左 （ 或右 ） 孩子域上 。 即： q-lchild=p-lchild; f-lchild（ 或 f-rchild） =p-rchild; 二叉樹檢索樹的刪除操作（續(xù)） 前兩種方法是以刪除待刪除結點 *p的中序前趨或 中序后繼 *q來實現刪除結點 *p之目的 ， 不需要知道 待刪除結點的雙親結點位置； 后兩種方法是直接刪除待刪除結點 *p， 不僅需要 知道其中序前趨或中序后繼 *q的位置 ， 還需要在檢 索待刪除結點 *p的同時記住其雙親結點的位置 。 二叉樹檢索樹的刪

45、除操作（續(xù)） 方法一和方法三中 *p的中序前趨 *q（ 即左子樹中的 最右下結點 ） 可以如下確定： q=p-lchild; while(q-rchild!=NULL) q=q-rchild; 而方法二和方法四中 *p的中序后繼 *q（ 即右子樹中 的最左下結點 ） 的確定方法為： q=p-rchild; while(q-lchild!=NULL) q=q-lchild; 二叉檢索樹的刪除算法描述 下面我們給出采用方法四刪除雙枝結點時的二叉檢 索樹的刪除算法描述如下： bstlist deletebst(bstlist t,keytype k) bstlist p,q,r,f; p=t; f=

46、NULL; while(p!=NULL) if(kkey) p=p-lchild; else p=p-rchild; 二叉檢索樹的刪除算法描述（續(xù)） if(p=NULL) break; /*檢索失敗時不用刪除中斷執(zhí)行 */ if(p-lchild=NULL)|(p-rchild=NULL) q=p; /*待刪除的 *p為葉子結點或單枝結點時 */ else q=p-rchild; while(q-lchild!=NULL) q=q-lchild; if(q-lchild!=NULL) r=q-lchild; else r=q-rchild; 二叉檢索樹的刪除算法描述（續(xù)） if(p!=q) q

47、-lchild= p-lchild; if(f-lchild=p) f-lchild=r; else f-rchild=r; return t; /*返回刪除操作后的二叉檢索樹 */ /*deletebst end*/ 4.二叉檢索樹的檢索性能分析 在二叉檢索樹上檢索關鍵字值等于給定值 k的記錄 ， 正好是走了一條從根結點到關鍵字值為 k的結點的路 徑 ， 和給定值 k的比較次數為路徑長度加 1（ 或結點所 在層次數 ） ， 和二分法檢索類似 ， 其比較次數不超過 樹的深度 。 然而 ， 用 二分法檢索 一個長度為 n的檢索表其檢索過 程的二叉樹表示是 惟一 的 ， 而含有 n個結點的 二叉檢

48、 索樹 卻 不惟一 。 二叉檢索樹的檢索性能分析舉例 例如 ， 如下圖給出了結點值都相同的兩棵二叉檢索 樹 ， 由于構造時的關鍵字序列不同 ， 前者深度為 3， 而后者深度為 7；在等概率的情況下 ， 前者的平均檢 索長度為 ASL=(1+2+2+3+3+3+3)/7=17/7， 后者的平均 檢索長度為 ASL=(1+2+3+4+5+6+7)/7= 28/7=4。 二叉檢索樹的檢索性能分析（續(xù)） 因此 ， 含有 n個結點的二叉檢索樹的平均檢索長度 和二叉檢索樹的形態(tài)有關 ， 當先后插入的關鍵字按值 有序時 ， 構造的二叉檢索樹蛻變?yōu)閱沃洌?升序時為 單右枝二叉樹 ， 降序時為 單左枝二叉樹

49、； 樹的深度為 n， 平均檢索長度為 (n+1)/2（ 和順序檢 索相同 ） ， 這是最差的情況 。 最好的情況是二叉檢索 樹的形態(tài)和二分法檢索過程得到的樹相同 ， 樹的高度 和完全二叉樹的高度相同 ， 其平均檢索長度為 。 二叉檢索樹的檢索性能分析（續(xù)） 現在我們考慮在一般情況下二叉檢索樹的平均檢索 長度 ， 假設在含有 n個結點的二叉樹中 ， 有 i個結點關 鍵字值小于根結點的關鍵字值 ， n-i-1個結點關鍵字值 大于根結點的關鍵字值 。 在等概率檢索的情況下平均檢索長度為： 其中 ， p(i)為含有 i個結點的二叉檢索樹的平均檢索長度； p(i)+1為檢索左子樹中每個結點所用比較次數的

50、平均值 ， p(n-i-1)+1為檢索右子樹中每個結點所用比較次數的平均值 。 二叉檢索樹的檢索性能分析（續(xù)） 由于根結點的左子樹中有 0個 ， 1個 ， ， n-1個結點 的情況是等概率的 ， 對上式取平均值得： 用數學歸納法可以證明 ， ， 即二叉檢 索樹的平均長度為 。 7.3 樹表的檢索 7.3.1 二叉檢索樹 7.3.2 二叉檢索樹的平衡性調整 7.3.3 B樹和 B+樹 平衡因子 平衡因子 （ balance factor） 二叉樹上任一結點的平衡因子 ， 定義為該結點的左子樹深 度減去右子樹深度的差 。 如下圖中給出了一些二叉樹 ， 其結點上所示數值為 該結點的平衡因子值 。 平

51、衡二叉樹 平衡二叉樹 （ balance binary tree） 如果一棵二叉樹中所有結點的平衡因子的絕對值不超過 1， 則稱該二叉樹為 平衡二叉樹 ；平衡二叉樹也稱作 AVL樹 。 顯然 ， AVL樹要么是一棵空樹 ， 要么其左右子樹深 度不超過 1且都是 AVL樹；只要二叉樹上有一個結點 的平衡因子的絕對值大于 1， 該二叉樹就是不平衡的 。 如前例圖中 ， (a)和 (b)都是平衡二叉樹 （ 即 AVL樹 ） ， 而 (c)和 (d)都不是平衡二叉樹 （ 即非 AVL樹 ） 。 平衡二叉樹（續(xù)） 由于 AVL樹具有良好的形態(tài) ， 其左右子樹的深度差不 超過 1；對于給定的結點數目 n，

52、 AVL樹的平均深度接 近于完全二叉樹的深度 ； 所以我們希望由任何初始序列構成的二叉檢索樹都 是 AVL樹 ， 使得其平均檢索長度接近于 。 如何使構造的二叉樹成為 AVL樹呢 ？ Adelson- Velskii和 Landis提供了一個動態(tài)地保持二叉檢索樹 平衡性的方法； 其基本思想是在構造二叉檢索樹的過程中 ， 每當插入一個 結點后都去檢查是否由于該結點的插入而破壞了二叉檢索 樹的平衡性；若出現絕對值超過 1的平衡因子 ， 則需要在保 持二叉檢索樹特性的前提下通過調整使之達到新的平衡 。 平衡二叉樹（續(xù)） 在一般情況下 ， 設在插入結點的過程中使二叉檢索 樹失去平衡的最小子樹的根結點為

53、 a， 即 a為離插入 結點最近且平衡因子絕對值超過 1的祖先結點； 因插入結點的位置不同而失去平衡需要調整的規(guī)律 可歸納為如下四種情況： LL型平衡旋轉 （ 右單旋型 ） RR型平衡旋轉 （ 左單旋型 ） LR型平衡旋轉 （ 先左后右雙旋型 ） RL型平衡旋轉 （ 先右后左雙旋型 ） 1.LL型平衡旋轉（右單旋型） 這種失衡是由于在結點 a的左孩子 b的左子樹上插入結點 ， 使結點 a的平衡因子由 1增至 2而造成的 。 其 調整策略 是以 a的左孩子 b為軸心順時針旋轉 （ 即向右旋 轉 ） 一次；使結點 a成為其左孩子 b的右孩子 ， 而 b的右子樹 成為 a的左子樹 ， 如下圖所示 。

54、 這種調整策略既使結點的平 衡因子滿足 AVL樹的要求 ， 又保持了二叉檢索樹的特性 （ 即 中序遍歷次序為上升序列 ） 。 2.RR型平衡旋轉（左單旋型） 這種失衡是由于在結點 a的右孩子 b的左子樹上插入結點 ， 使 a的平衡因子由 -1變成 -2而造成的； 其 調整策略 是以 a的右孩子 b 為軸心逆時針旋轉 （ 即向左旋 轉 ） 一次；使 a成為 b的左孩子 ， 而 b的左子樹成為 a的右子樹 ， 如下圖所示 。 3. LR型平衡旋轉（先左后右雙旋型） 這種失衡是由于在結點 a的左孩子 b的右子樹上插入結點 ， 使 a的平衡因子由 1增至 2造成的 。 設 c是 b的右孩子 ， 插入結

55、點的位置有三種可能性： c就是插入結點 ， 這是由于插入前 b為葉子結點且 a無右孩子而產生的 一種可能； 插入結點在 c的左子樹上； 插入結點在 c的右子樹上 。 LR型平衡旋轉（續(xù)） 對這三種導致 LR型失衡的情況 ， 其 調整策略 是一致的： 即以 a的左孩子 b的右孩子 c為軸心 ， 先逆時針 （ 即向左 ） 旋轉一次 ， 再順時針 （ 即向右 ） 旋轉一次；使 c的左子樹 成為 b的右子樹 ， c的右子樹成 a的左子樹 ， b成為 c的左孩子 而 a成為 c的右孩子 ， 以 “ 插入在 c的左子樹上 ” 為例 ， 兩次 旋轉的調整過程如下圖所示 。 4. RL型平衡旋轉（先右后左雙旋

56、型） 這種失衡是由于在結點 a的右孩子 b的左子樹上插入 結點 ， 使 a的平衡因子由 -1變成 -2造成的 ， 設 c是 b的 左孩子 ， 插入結點位置的三種可能性如下圖所示 ： RL型平衡旋轉（續(xù)） 對這三種導致 RL型失衡的情況 ， 其 調整策略 為： 以 a的右孩子 b的左孩子 c為軸心 ， 先順時針 （ 即向右 ） 旋 轉一次 ， 再逆時針 （ 即向左 ） 旋轉一次；使 c的左子樹成 為 a的右子樹 ， c的右子樹成為 b的左子樹 ， a成為 c的左孩 子而 b成為 c的右孩子 。 以 “ 插入在 c的左子樹上 ” 為例 ， 兩次旋轉的調整過程如下圖所示： 構造平衡二叉檢索樹舉例 例

57、如 ， 對于一組記錄其關鍵字序列為 （ 18， 5， 10， 15， 12， 11， 20） ， 要建立一棵平衡的二叉檢索樹 ， 其構造過程如下 圖所示： 構造型平二叉檢索樹的算法 在設計構造平衡的二叉檢索樹的算法時 ， 需要先為 每個結點增加一個平衡因子域 ， 然后在二叉檢索樹構 造算法的基礎上做幾點修改： 插入一個結點后 ， 要修改樹中各結點平衡因子的值； 判別是否因插入結點產生失衡 ， 在失衡時找到失衡的最 小子樹； 判別失衡類型并做相應的調整處理 。 在平衡的二叉檢索樹上進行檢索的過程 ， 和在二叉 檢索樹上的檢索過程一致 ， 在檢索過程中和給定值比 較的次數不會超過樹的深度 ， 而含

58、有 n個結點的平衡 二叉檢索樹的最大深度為 ， 其中 。 7.3 樹表的檢索 7.3.1 二叉檢索樹 7.3.2 二叉檢索樹的平衡性調整 7.3.3 B樹和 B+樹 B樹 B樹 是一種平衡的多路檢索樹 ， 是文件系統(tǒng) （ 包 括大型數據庫文件系統(tǒng) ） 中的一種重要的數據組織 結構 。 一棵 m階 B樹 ， 或者為空樹 ， 或者為滿足下列特性 的 m叉樹： 樹中每個結點至多有 m棵子樹 （ 即至多有 m-1 個關鍵字 ） ； 除非根結點為葉子結點 ， 否則至少有兩棵子 樹 （ 即至少有一個關鍵字 ） ； 除根結點之外的所有非終端結點至少有棵子 樹； B樹（續(xù)） 所有的非終端結點中包含以下信息：

59、（ n， A0， k1， A1， k2， ， kn， An ） 其中： n（ nm-1） 為關鍵字的個數 ， 即子樹個數為 n+1； ki（ 1in） 為關鍵字 ， 且 kiki+1（ 1in） ； Ai（ 0in） 為指向其子樹的根結點的指針 ， 且 Ai （ 0in） 所指子樹中所有結點的關鍵字值都小于 ki+1， An 所指子樹中所有結點的關鍵字值都大于 kn； 所有葉子結點在同一個層次上 ， 且不含有任何 信息 （ 可以看作是外部結點或檢索失敗的結點；實 際上這些結點不存在 ， 指向這些結點的指針為 NULL） 。 B樹示全例 下圖給出了一棵 4階 B樹的示例： B樹的插入操作 在 B

60、樹上插入一個關鍵字 ， 不是象在二叉檢索樹中 那樣添加一個葉子結點 ， 而是在 B樹的最底層的某個 非終端結點中添加一個關鍵字 。 若該結點中關鍵字的個數小于 m-1個則插入完成； 否則添加后關鍵字個數由 m-1個變?yōu)?m個與 B樹定義不 符 ， 需要進行結點的 “ 分裂 ” 以滿足 B樹定義 。 結點的分裂方法為 ， 把中間一個關鍵字拿出來插入到該 結點的雙親結點上 ， 前后兩部分各自形成一個結點；雙 親結點中也可能有 m個關鍵字 ， 就需要繼續(xù)分裂結點 ， 直 到插入到某個關鍵字個數小于 m-1的祖先結點 。 由這種分裂過程可見 ， B樹是由底向上生長的 。 B樹的插入操作舉例 B樹的插入

61、過程如下圖所示 ， 圖中只畫出了非終端 結點 ， 省去了最底層的葉子結點 。 B樹的刪除操作 在 B樹上刪除一個關鍵字和插入關鍵字類似也是由 底向上的調整過程 ， 先找到該關鍵字所在的結點并刪除這個關鍵字 。 若找到的結點是最底層的非終端結點 ， 當關鍵字個數大 于則刪除完成 ， 否則刪除后關鍵字個數由個變?yōu)閭€與 B樹 定義不符 ， 需要進行結點的 “ 合并 ” 以滿足 B樹定義 。 合并的方法是把刪除了關鍵字的結點同其左兄弟結點 （ 或右兄弟結點 ） 合并 ， 連同它們的雙親結點中的相關 關鍵字項一塊合并重新分配 ， 在其雙親結點不滿足 B樹定 義時繼續(xù)向上調整直到根結點 。 若找到的待刪除

62、關鍵字所在結點不是底層非終端結點 ， 則是將該關鍵字用其 B樹中的后繼替代 ， 而刪除其后繼的 信息 。 B樹的刪除操作舉例 B樹的刪除過程如下圖所示： B樹的檢索操作 在 B樹中進行檢索的過程是： 首先在根結點中所包含的關鍵字中檢索給定的關鍵字 ， 若找到則檢索成功 ， 否則確定待檢索關鍵字所在的子樹 ， 并在該子樹中繼續(xù)檢索 ， 直到檢索成功或指針為空時檢 索失敗 。 例如 ， 在前例中的一棵 4階 B樹中檢索關鍵字值為 61的記錄 ， 因根結點中不存在此關鍵字 ， 則到大于 39的子樹中檢索；又 因為子樹的根結點中沒有此關鍵字 ， 而 506180， 故再到 s 所指子樹中檢索 ， 在這

63、個結點中含有 61的關鍵字值則檢索成 功 。 又如在此 4階 B樹中檢索關鍵字值為 75的記錄 ， 也是沿前面 的這一條路線檢索 ， 由于 s所指結點中沒有值為 75的關鍵字而 檢索失敗 。 B樹的檢索操作（續(xù)） B樹的檢索是在 B 樹上找結點和在結點中找關鍵字 兩個基本操作的交叉進行過程 ， 待查關鍵字所在結 點在 B樹中的層次是決定 B樹檢索效率的首要因素 ， 最壞的情況下是含 n個關鍵字的 m階 B樹的最大深度 。 由 B樹定義 ， 第一層至少有 1個結點 ， 第二層至少有 2個結點；由于除根結點外的每個非終端結點至少有 棵子樹 ， 則第三層至少有 2（ ） 個結 點； ；依此類推 ，

64、第 h+1層至少有 個結 點；而 h+1層為葉子結點 。 若 m階 B樹有 n個關鍵字 ， 則葉子結點即查找不成功的結點數為 n+1， 由此有 B+樹 B+樹是應用于文件系統(tǒng)中的 B樹的一種變形樹 ， 它 與 B樹的差異主要在于： 有 n棵子樹的結點中含有 n個關鍵字； 所有葉子結點中包含了全部關鍵字的信息 及指向相應記錄的指針 ， 且葉子結點以關鍵字遞增 順序鏈接； 所有的非終端結點可以看成是索引部分 ， 結點中僅含有其子樹中的最大 （ 或最小 ） 關鍵字 。 B+樹舉例 如下圖給出了一棵 3階 B+樹 。 通常 B+樹上有兩個指針 ， 一個指向根結點 ， 一個指 向關鍵字值最小的葉子結點

65、。 因此 ， 對于 B+樹既可從根結點開始多級索引順序檢 索 ， 又可以從最小關鍵字開始順序檢索 。 B+樹的操作 在 B+樹上進行插入 、 刪除和檢索的過程與 B樹基本相 似 。 在檢索過程中在非終端結點上找到給定值后并不終止 ， 而是繼續(xù)向下直到葉子結點；因而無論是檢索成功還是檢 索失敗 ， 每次檢索都是走了一條從根結點到葉子結點的路 徑 。 B+樹的插入僅在葉子結點上進行 ， 當葉子結點中關鍵字 個數大于 m時也要分裂成兩個結點 ， 并且其雙親結點中同 時也包含這兩個結點的關鍵字最大值 。 B+樹的刪除也在葉子結點中進行 ， 其在非終端結點中的 值可以作為分界關鍵字存在；當然在刪除后若使

66、結點中關 鍵個數小于 時也要進行結點的合并操作 。 第 7章 檢索及基本算法 7.1 檢索的概念 7.2 線性表的檢索 7.3 樹表的檢索 7.4 哈希檢索 哈希檢索 在前兩節(jié)介紹的線性表檢索和樹表檢索方法后 ， 由 于記錄在檢索表中的位置是隨機的或按關鍵字值大 小次序排列的 ， 記錄的存儲位置和其關鍵字值之間 不存在某種確定的關系 ， 存儲位置依賴于關鍵字的 初始隨機序列或在檢索表中其它關鍵字值的大小 。 所以在檢索時需要進行一系列的關鍵字值與給定值 之間的比較 ， 其檢索效率和檢索過程中進行的比較 次數有關 。 本節(jié)介紹一種直接利用關鍵字值計算記錄在檢索表 中的存儲位置來進行檢索的方法 哈希 （ Hash） 檢索技術 。 7.4 哈希檢索 7.4.1 哈希檢索與哈希表 7.4.2 哈希函數的構造方法 7.4.3 地址沖突的消解策略 7.4.4 哈希表的檢索算法及性能分析 哈希檢索與哈希表 哈希檢索技術的初衷是組織理想狀態(tài)的檢索表 。 檢索表的理想狀態(tài)是：把記錄的關鍵字值與記錄在 檢索表中的存儲位置建立起某種一對一的關系 ， 這 種一對一的關系可以用關于關鍵字的一個 函數 h(key