《《算法與數(shù)據(jù)結(jié)構(gòu)》第7章檢索及基本算法ppt.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第7章檢索及基本算法ppt.ppt（160頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、gh=15 檢索開(kāi)始時(shí) ， low=1， high=15， mid=(1+15)/2=8。 由于 k=1829=R8.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=R14.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

16、 29 31 35 38 42 46 49 52 low=13mid=14high=15 由于 k=4649=R14.key， 所以應(yīng)在當(dāng)前區(qū)間的左半 區(qū) 繼 續(xù) 檢 索 ； 此 時(shí) 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， 此時(shí)檢索 46成功 。 二分法檢索舉例 檢索 k=11 檢索 k=11的過(guò)程： 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， 應(yīng)在左半?yún)^(qū)繼續(xù)檢索；此 時(shí) 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， 應(yīng)在當(dāng)前區(qū)間的右半?yún)^(qū)繼 續(xù)檢索；此時(shí) 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， 應(yīng)在當(dāng)前區(qū)間的左半?yún)^(qū)繼 續(xù)檢索；此時(shí) high=mid-1= 3-1=23=low， 左半?yún)^(qū)已 沒(méi)有元素 （ 不存在區(qū)間了 ） ， 檢索 k 11失敗 。 二分法檢索過(guò)程可用 C語(yǔ)言描述 二分法檢索過(guò)程可用 C語(yǔ)言描述為如下算法： 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， 則可有如下近似結(jié)果： 二分法檢索過(guò)程分析（續(xù)） 由此可見(jiàn) ，

19、二分法檢索的效率比順序檢索高得多 ， 如 n=127時(shí) ， 順序檢索 ASL 64而二分法則為 ASL 6。 二分法檢索只適用于檢索表為順序存儲(chǔ)結(jié)構(gòu)之下 的有序表 ， 即這種較高的檢索效率是以對(duì)檢索表預(yù) 先按關(guān)鍵字值大小排序?yàn)榇鷥r(jià)的 ， 所以二分法檢索 適合于一旦建立很少變動(dòng)而又需要經(jīng)常檢索的檢索 表 。 7.2 線性表的檢索 7.2.1 順序檢索 7.2.2 二分法檢索 7.2.3 黃金分割點(diǎn)檢索 7.2.4 精算點(diǎn)檢索 7.2.5 分塊檢索 黃金分割點(diǎn)檢索 黃金分割點(diǎn)檢索 （ gold-partition search） ， 簡(jiǎn)稱黃 金點(diǎn)檢索 。 它是利用我國(guó)著名數(shù)學(xué)家華羅庚院士當(dāng) 年推廣

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

21、=15 開(kāi)始時(shí) 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， 在 黃 金 點(diǎn) 之 后 的 區(qū) 間 繼 續(xù) 檢 索 。 此時(shí) 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 檢索成功 。 一個(gè)用二分法檢索需 4次比 較的工作 ， 黃金分割點(diǎn)檢

22、索只需兩次比較就完成了 。 黃金分割點(diǎn)檢索算法描述 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; 黃金分割點(diǎn)檢索（續(xù)） 該算法的時(shí)間性能與二分法相比 ， 在平

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

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

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

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

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

28、 于給定值 k時(shí)檢索失敗 。 精算點(diǎn)檢索算法描述 這種與順序檢索相結(jié)合的精算點(diǎn)檢索算法可描述如下： 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-; 精算點(diǎn)檢索算法描述（續(xù)） if(Rmid.key=k) return mid; /*檢索成功返回位置 */ else return 0; /*檢索失敗

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

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

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

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

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

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

35、ULL。 二叉檢索樹(shù)的二叉鏈表類型 設(shè)二叉檢索樹(shù)以如下描述的二叉鏈表作為存儲(chǔ)結(jié) 構(gòu)： typedef struct node keytype key; /*關(guān)鍵字域 */ elemtype other; /*其它數(shù)據(jù)域 */ struct node *lchild, *rchild; /*左右孩子指針域 */ bstnode; /*定義結(jié)點(diǎn)類型 bstnode*/ typedef bstnode *bstlist; /*定義二叉檢索樹(shù)表類型 bstlist*/ 二叉檢索樹(shù)的檢索算法描述 二叉檢索樹(shù)的檢索算法可描述如下： 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.二叉檢索樹(shù)的構(gòu)造過(guò)程和插入操作 對(duì)于一組關(guān)鍵字無(wú)序的記錄 ， 構(gòu)造其相應(yīng)的二叉檢索 樹(shù)的方法是：從一棵空的二叉檢索樹(shù)開(kāi)始 ， 每當(dāng)讀入 一個(gè)記錄就生成一個(gè)結(jié)點(diǎn) ， 然后按關(guān)鍵字值的大小插 入到當(dāng)前的二叉檢索樹(shù)之中；當(dāng)所有記錄的結(jié)點(diǎn)都已 插入二叉檢索樹(shù)中時(shí)便構(gòu)造完畢 。 雖然 ， 插入操作是構(gòu)造二叉檢索樹(shù)的關(guān)鍵操作 。 要保 證在一棵二叉檢索

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

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; 二叉檢索樹(shù)的構(gòu)造過(guò)程和插入操作 (續(xù) ) p=t; while(p!=NULL) q=p; if(p-key=k) /*檢索成功不必插入 */ return t; /*返回原二叉檢索樹(shù) */ else if(p-keyrchild; else p=p-lchild; p

39、=(bstlist)malloc(sizeof(bstnode); 二叉檢索樹(shù)的構(gòu)造過(guò)程和插入操作 (續(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; 二叉檢索 (排序 )樹(shù)構(gòu)造過(guò)程舉例 從空樹(shù)出發(fā)經(jīng)過(guò)一系列的檢索插入操作之后 ， 就可生成一 棵 二叉檢索樹(shù) 。 一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉檢索樹(shù) 而變成一個(gè)有序序列 （ 即中序遍歷次序序列 ） ， 構(gòu)造的過(guò)程 就是對(duì)無(wú)序序列進(jìn)行排序的過(guò)程 ， 所以又稱作 二叉排序樹(shù) 。 設(shè)關(guān)鍵

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

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

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

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

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

45、除操作（續(xù)） 方法一和方法三中 *p的中序前趨 *q（ 即左子樹(shù)中的 最右下結(jié)點(diǎn) ） 可以如下確定： q=p-lchild; while(q-rchild!=NULL) q=q-rchild; 而方法二和方法四中 *p的中序后繼 *q（ 即右子樹(shù)中 的最左下結(jié)點(diǎn) ） 的確定方法為： q=p-rchild; while(q-lchild!=NULL) q=q-lchild; 二叉檢索樹(shù)的刪除算法描述 下面我們給出采用方法四刪除雙枝結(jié)點(diǎn)時(shí)的二叉檢 索樹(shù)的刪除算法描述如下： 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; 二叉檢索樹(shù)的刪除算法描述（續(xù)） if(p=NULL) break; /*檢索失敗時(shí)不用刪除中斷執(zhí)行 */ if(p-lchild=NULL)|(p-rchild=NULL) q=p; /*待刪除的 *p為葉子結(jié)點(diǎn)或單枝結(jié)點(diǎn)時(shí) */ else q=p-rchild; while(q-lchild!=NULL) q=q-lchild; if(q-lchild!=NULL) r=q-lchild; else r=q-rchild; 二叉檢索樹(shù)的刪除算法描述（續(xù)） if(p!=q) q

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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