《算法與數(shù)據(jù)結(jié)構(gòu)》第7章 檢索及基本算法ppt課件

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

2、檢索表search table；n檢索表是由同一類型的數(shù)據(jù)元素或記錄組成的集合。n由于集合是一種松散型數(shù)據(jù)構(gòu)造，數(shù)據(jù)元素除了同屬于一個(gè)集合外再無別的關(guān)系，所以檢索表是一種非常靈敏的數(shù)據(jù)構(gòu)造。 檢索的概念(續(xù)) n對(duì)檢索表常做的運(yùn)算和操作有：n 查找某個(gè)特定的數(shù)據(jù)元素能否在檢索表中；n 檢索某個(gè)特定的數(shù)據(jù)元素的各種屬性；n 在檢索表中插入一個(gè)數(shù)據(jù)元素；n 從檢索表中刪去某個(gè)數(shù)據(jù)元素。n假設(shè)對(duì)查找表只作前兩種統(tǒng)稱為“檢索的操作，稱此類檢索表為靜態(tài)檢索表static search table；n假設(shè)在檢索的過程中同時(shí)插入表中不存在的數(shù)據(jù)元素，或者從檢索表中刪除已存在的某個(gè)數(shù)據(jù)元素，稱此類檢索表為動(dòng)態(tài)

3、檢索表dynamic search table。 檢索的概念(續(xù)) n 所謂特定的信息，是指關(guān)鍵字值等于給定值的信息，信息的單位是數(shù)據(jù)元素或記錄。n 關(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)鍵字。如人事檔案記錄構(gòu)造為：n 它含有五個(gè)關(guān)鍵字，其中性別這個(gè)關(guān)鍵字標(biāo)識(shí)了一個(gè)職工的性別情況。檢索的概念(續(xù)) n主關(guān)鍵字primary key是指能獨(dú)一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素或記錄的關(guān)鍵字。如上述記錄中身份證號(hào)碼是主關(guān)鍵字，可以獨(dú)一標(biāo)識(shí)一條記錄；而姓名、性別、年齡、工資級(jí)別不能獨(dú)一標(biāo)識(shí)一條記錄，它們都不是主關(guān)鍵字。n輔關(guān)

4、鍵字secondary key是用以標(biāo)識(shí)假設(shè)干數(shù)據(jù)元素或記錄的關(guān)鍵字，也稱作次關(guān)鍵字或從關(guān)鍵字。如上述記錄中的姓名、性別、年齡、工資級(jí)別都是輔關(guān)鍵字。檢索的概念(續(xù)) n檢索，就是根據(jù)給定的某個(gè)值，在檢索表中查找一個(gè)關(guān)鍵字等于給定值的記錄的運(yùn)算或操作。n假設(shè)在檢索表中存在這樣的記錄，那么稱檢索勝利，檢索的結(jié)果是找到記錄的全部信息或找到記錄在檢索表中的位置；n假設(shè)檢索表中不存在關(guān)鍵字值等于給定值的記錄，那么稱檢索失敗，給出在檢索表中無要查找的記錄的信息提示，并在動(dòng)態(tài)檢索時(shí)插入關(guān)鍵字等于給定值的記錄于檢索表中。檢索的概念(續(xù)) n 在檢索表中查找某個(gè)數(shù)據(jù)元表或記錄的過程，依賴于這個(gè)數(shù)據(jù)元表或記錄在

5、查找表中所處的位置；對(duì)檢索表的檢索方法取決于檢索表中數(shù)據(jù)元表或記錄的組織戰(zhàn)略。n如在字典中查找一個(gè)英文單詞，由于字典是按字母順序編排的，所以不需從第一個(gè)單詞順序查找，而只是按待查單詞中每個(gè)字母在字母表中的位置快速找到該單詞；n而在數(shù)據(jù)元素或記錄之間無任何關(guān)系組織起來的集合中查找，那么需求從第一個(gè)元素或記錄開場(chǎng)依次順序查找。檢索的概念(續(xù)) n 在計(jì)算機(jī)中進(jìn)展檢索是對(duì)已存入計(jì)算機(jī)中的數(shù)據(jù)進(jìn)展檢索，取決于采用何種數(shù)據(jù)構(gòu)造來組織檢索表；往往需求在數(shù)據(jù)元素或記錄之間人為地加上一些關(guān)系，即用非集合構(gòu)造如數(shù)組、文件、二叉樹、散列表等構(gòu)造來組織檢索表，以便按某種規(guī)律來進(jìn)展檢索。n依數(shù)據(jù)組織方式不同，檢索分為

6、線性表檢索、樹表檢索和散列表檢索等。n 衡量一個(gè)檢索算法的優(yōu)劣，主要根據(jù)在檢索過程中給定值和關(guān)鍵字的比較操作次數(shù)。為此，我們引入平均檢索長(zhǎng)度的概念。平均檢索長(zhǎng)度n檢索算法的平均檢索長(zhǎng)度average search length，即在檢索過程中用給定值和關(guān)鍵字進(jìn)展比較的平均比較次數(shù)，n或者說是為找到具有給定值關(guān)鍵字的記錄所需求的比較次數(shù)的平均值。n它是為確定記錄在檢索表中的位置，需求和給定值進(jìn)展比較的關(guān)鍵字個(gè)數(shù)的期望值。平均檢索長(zhǎng)度續(xù)n 對(duì)于含有n個(gè)記錄的檢索表，檢索勝利時(shí)的平均檢索長(zhǎng)度為 n其中，Pi為檢索第i個(gè)記錄的概率，且 ；普通在不特殊闡明的情況下均以為是等概率，即檢索每個(gè)記錄的概率相等

7、， 。nCi為找到第i個(gè)記錄需求和給定值比較的關(guān)鍵字的個(gè)數(shù)，它隨檢索方法的不同而不同。 第7章 檢索及根本算法 7.1 檢索的概念7.2 線性表的檢索7.3 樹表的檢索7.4 哈希檢索線性表的檢索n 在檢索表的數(shù)據(jù)組織方式中，線性表是最根本的，也是最常用的一種組織方式。本節(jié)主要討論在順序存儲(chǔ)構(gòu)造實(shí)現(xiàn)的線性表上的檢索算法，其類型定義描畫為n typedef structn keytype key; /*關(guān)鍵字類型*/n elemtype other; /*其它域*/n sqlist;n sqlist Rn+1; /*順序表*/n本節(jié)引見的線性表檢索方法有順序檢索、二分法檢索、黃金點(diǎn)檢索、精算點(diǎn)檢

8、索和分塊檢索等。7.2 線性表的檢索7.2.1 順序檢索7.2.2 二分法檢索7.2.3 黃金分割點(diǎn)檢索7.2.4 精算點(diǎn)檢索7.2.5 分塊檢索順序檢索n 順序檢索sequential search是一種最簡(jiǎn)單的根本檢索方法。n其根本思緒為：n從表的一端開場(chǎng)，用給定值逐個(gè)與表中各記錄的關(guān)鍵字值比較。n假設(shè)找到某個(gè)關(guān)鍵字值等于給定值的記錄，那么檢索勝利，并給出該記錄在表中的位置；n假設(shè)檢索完好個(gè)表仍未找到關(guān)鍵字值等于給定值的記錄，那么檢索失敗，并給出失敗信息。n 順序檢索方法既適用于線性表的順序存儲(chǔ)構(gòu)造，也適用于線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。順序檢索舉例n以順序存儲(chǔ)構(gòu)造為例，設(shè)數(shù)據(jù)元素存放在數(shù)組中下標(biāo)

9、從1到n的記錄中，0號(hào)記錄位置留作監(jiān)視哨，從下標(biāo)為n的一端開場(chǎng)向另一端檢索，順序檢索算法可描畫如下：nint seqsearch(sqlist R,keytype k) n int i=n;n R0.key=k; /*設(shè)置R0為監(jiān)視哨*/n while(Ri.key != k)n i-;n return i; /*前往檢索結(jié)果i*/n 順序檢索舉例續(xù)n 算法中設(shè)置監(jiān)視哨R0，可以使得在檢索勝利和檢索失敗時(shí)的處置一致，在檢索失敗時(shí)也能在監(jiān)視哨位置找到關(guān)鍵字值為k的記錄，可省去在while循環(huán)中的位置越界檢查i=1。n假設(shè)從R0處向后順序檢索，監(jiān)視哨可設(shè)置在Rn處。n算法執(zhí)行之后，非0的函數(shù)值表示

10、待查找記錄在數(shù)組中的位置下標(biāo)；假設(shè)函數(shù)值為0闡明檢索表中沒有要查找的記錄。順序檢索續(xù)n對(duì)于具有n個(gè)記錄的檢索表，假設(shè)待查找記錄在Rn處，需求和給定值k比較一次，即Cn=1；n假設(shè)待查找記錄在Rn-1處，需求和給定值k比較兩次，即Cn-1=2；n普通地，假設(shè)待查找記錄在Ri處，需和給定值k比較n-i+1次，即Ci=n-i+1。n因此，在等概率的情況下順序檢索的平均檢索長(zhǎng)度為順序檢索續(xù)n在檢索勝利時(shí)順序檢索的平均比較次數(shù)約為表長(zhǎng)的一半。n在檢索失敗時(shí)，順序檢索需求進(jìn)展n+1次的比較。n當(dāng)n很大時(shí)，平均檢索長(zhǎng)度也很大，檢索效率較低，這是順序檢索的主要缺陷。n但由于順序檢索對(duì)表的存儲(chǔ)構(gòu)造和元素存放次序

11、沒有要求，且算法簡(jiǎn)單，在許多實(shí)踐運(yùn)用中常被采用。 7.2 線性表的檢索7.2.1 順序檢索7.2.2 二分法檢索7.2.3 黃金分割點(diǎn)檢索7.2.4 精算點(diǎn)檢索7.2.5 分塊檢索二分法檢索n二分法檢索binary search，也稱作折半檢索，它是一種效率較高的檢索方法。它要求檢索表是用順序存儲(chǔ)構(gòu)造表示，且數(shù)據(jù)元素的存放要按關(guān)鍵字值有序陳列。n二分法檢索的根本思想是：n在有序表中先取中間位置作為比較對(duì)象，假設(shè)給定值與中間記錄的關(guān)鍵字值相等，那么檢索勝利；n假設(shè)給定值小于中間記錄的關(guān)鍵值那么在表的左半?yún)^(qū)查找，n假設(shè)給定值大于中間記錄的關(guān)鍵字值那么在表的右半?yún)^(qū)查找。n就這樣經(jīng)過一次的比較減少一半

12、的檢索區(qū)間，在每一個(gè)檢索區(qū)間都是選取中間位置作為比較對(duì)象，不斷地反復(fù)這樣的檢索過程直到檢索勝利，或者檢索區(qū)間已無記錄時(shí)檢索失敗。二分法檢索舉例n例如：知一個(gè)含15個(gè)記錄的有序表，其關(guān)鍵字序列如下：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n如今要檢索給定值k為19、46和11的記錄，其檢索過程如下：n用low和high分別表示檢索區(qū)間的下界和上界；n用mid指示中間位置，即mid=(low +high)/2；n檢索開場(chǎng)時(shí)low=1，high=n；即檢索區(qū)間為1，n。二分法檢索舉例檢索k=18n檢索k=18的過程：n 07 10 14 18 21

13、23 25 29 31 35 38 42 46 49 52n nlow=1 mid=8 high=15n檢索開場(chǎng)時(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，即：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=9 mid=12 high=15n由于k=4642=R14.key，所以應(yīng)在當(dāng)前區(qū)間的右半?yún)^(qū)繼續(xù)檢索； 二分法檢索舉例檢索k=46(續(xù))n此時(shí)low=12+1 =13，mid=(13+15)

14、/2=14，即：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=13mid=14high=15n由于k=4649=R14.key，所以應(yīng)在當(dāng)前區(qū)間的左半?yún)^(qū)繼續(xù)檢索；此時(shí)high=mid-1= 14-1=13，mid=(13+13)/2=13，即：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=13n mid=13n high=13 n由于k=46=R13.key，此時(shí)檢索46勝利。二分法檢索舉例檢索k=11n檢索k=11的過程：n 07 10 14 18 21 23 25 29

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

16、igh=3n由于k=1114=R3.key，應(yīng)在當(dāng)前區(qū)間的左半?yún)^(qū)繼續(xù)檢索；此時(shí)high=mid-1= 3-1=23=low，左半?yún)^(qū)已沒有元素不存在區(qū)間了，檢索k11失敗。 二分法檢索過程可用C言語描畫 n二分法檢索過程可用C言語描畫為如下算法：n int binarysearch (sglist R,keytype k)n int low,mid,high;n low=1; high=n;n while(low=high)n mid=(low+high)/2;n if(k=Rmid.key)n return mid;n else n if(k100，那么可有如下近似結(jié)果： 二分法檢索過程分析續(xù)

17、 n由此可見，二分法檢索的效率比順序檢索高得多，如n=127時(shí)，順序檢索ASL64而二分法那么為ASL6。n二分法檢索只適用于檢索表為順序存儲(chǔ)構(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)檢索n黃金分割點(diǎn)檢索gold-partition search，簡(jiǎn)稱黃金點(diǎn)檢索。它是利用我國(guó)著名數(shù)學(xué)家華羅庚院士當(dāng)年推行優(yōu)選法時(shí)引見的黃金分割點(diǎn)的概念，即利用黃金分割數(shù)0.

18、618把檢索區(qū)間分為兩個(gè)不等的區(qū)間。n每次用給定值與黃金點(diǎn)上的記錄的關(guān)鍵字比較，假設(shè)相等檢索勝利，假設(shè)給定值小于黃金點(diǎn)關(guān)鍵字值，繼續(xù)在黃金點(diǎn)之前的區(qū)間檢索；假設(shè)給定值大于黃金點(diǎn)關(guān)鍵字值，繼續(xù)在黃金點(diǎn)之后的區(qū)間檢索。n經(jīng)過黃金點(diǎn)逐次減少檢索區(qū)間，直到檢索勝利，或區(qū)間已無記錄檢索失敗時(shí)止。 黃金分割點(diǎn)檢索舉例n 例如，仍以前面的15個(gè)記錄為例，檢索k46的黃金分割點(diǎn)檢索過程為：n 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=1 mid=9 high=15n開場(chǎng)時(shí)low=1，high=15，mid=low+0.618*(high-low+1

19、)-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。即：n 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=10 mid=13 high=15n 由于k=46=R13.key 檢索勝利。一個(gè)用二分法檢索需4次比較的任務(wù)，黃金分割點(diǎn)檢索只需兩次比較就完成了。黃金分割點(diǎn)檢索算法描畫 int goldpartsearch(sqlist R,keytype k) int low,mid,

20、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ù)n 該算法的時(shí)間性能與二分法相比，在平均性能上優(yōu)于二分法，但依然是；在最壞情況下，每次比較之后都在較大的區(qū)間內(nèi)繼續(xù)檢索，比二分法差；在最好情況下，每次比較之后都在小區(qū)間內(nèi)繼續(xù)檢索，比二分法好。n 所謂黃金分

21、割點(diǎn)，就是利用Fibonacci數(shù)列對(duì)檢索表分割得到的一系列位置。Fibonacci數(shù)列的定義為： 黃金分割點(diǎn)檢索續(xù)n留意察看“Fibonacci數(shù)列及其相鄰項(xiàng)的比值表中給出的F(n)/F(n+1)的值，從n=6之后根本上穩(wěn)定在0.618處。n因此，我們可以對(duì)長(zhǎng)度為F(n)的檢索表，第一次用F(n-1)處記錄的關(guān)鍵字同給定值比較；由F(n-1)分割的兩個(gè)區(qū)間的長(zhǎng)度分別為F(n-2)-1和F(n-3)，又都可以利用Fibonacci數(shù)列找出新的分割點(diǎn)；如此不斷進(jìn)展下去，就可獲得檢索勝利或失敗的結(jié)果。n然而，檢索表的長(zhǎng)度很難是某個(gè)Fibonacci數(shù)列或接近Fibonacci數(shù)的值；其次即就是Fi

22、bonacci數(shù)，也還得為Fibonacci檢索預(yù)備一張F(tuán)ibonacci數(shù)表或經(jīng)過循環(huán)遞推求出每次要用的Fibonacci數(shù)，所以說利用Fibonacci數(shù)列設(shè)計(jì)檢索算法不如直接運(yùn)用黃金分割數(shù)0.618設(shè)計(jì)檢索算法方便。 7.2 線性表的檢索7.2.1 順序檢索7.2.2 二分法檢索7.2.3 黃金分割點(diǎn)檢索7.2.4 精算點(diǎn)檢索7.2.5 分塊檢索精算點(diǎn)檢索n對(duì)于有序的檢索表，假設(shè)記錄的關(guān)鍵字值不僅有序，而且分布均勻或比較均勻，我們能不能很快地完成關(guān)鍵字值等于給定值記錄的檢索義務(wù)呢？回答是一定的，下面將要引見的精算點(diǎn)檢索就可以處理這個(gè)問題。n所謂精算點(diǎn)檢索precise computing

23、 search，也稱作插值檢索。它是利用檢索區(qū)間有序關(guān)鍵字值范圍和給定值的大小比例關(guān)系估算檢索位置的一種檢索方法。 精算點(diǎn)檢索續(xù)n當(dāng)關(guān)鍵字值分布均勻時(shí)應(yīng)滿足下式：n其中k為給定值，mid為估算位置，low和high分別為檢索區(qū)間下界和上界位置，經(jīng)整理可得估算公式為： n當(dāng)給定值k等于Rmid.key那么檢索勝利；否那么假設(shè)kRmid.key那么在mid之后檢索。 精算點(diǎn)檢索續(xù)n在關(guān)鍵字值均勻分布時(shí)，如呈等差數(shù)列時(shí)一次比較便可檢索勝利；在關(guān)鍵字值分布比較均勻時(shí)，假設(shè)一次比較不能找到也會(huì)在mid位置附近，這兩種情況的檢索長(zhǎng)度與檢索表的大小n無關(guān)，所以稱之為精算點(diǎn)檢索。n假設(shè)關(guān)鍵字值分布不均勻，可減

24、少檢索區(qū)間繼續(xù)用前面的估算公式確定檢索點(diǎn)檢索，其檢索性能也優(yōu)于黃金分割點(diǎn)檢索和二分法檢索。精算點(diǎn)檢索舉例n例如，對(duì)于前述的15個(gè)記錄的檢索表，檢索k=14的記錄，low=1，high=15， ，R3.key=14等于給定值，一次比較檢索勝利；又如檢索k=29時(shí)， ，一次比較Rn.key=29等于給定值檢索勝利；再如檢索k=46時(shí) ， ， 一 次 比 較R13.key=46等于給定值檢索勝利；等等。 精算點(diǎn)檢索舉例續(xù)n既然在關(guān)鍵字值分布較均勻時(shí)，即使一次比較不能檢索勝利也會(huì)在mid位置附近，在算法設(shè)計(jì)時(shí)就只需一次計(jì)算mid的值。n假設(shè)k=Rmid.key，那么一次比較檢索勝利；n假設(shè)kRmid.

25、key，那么可由mid后一個(gè)記錄開場(chǎng)向后順序檢索，直到檢索勝利或某個(gè)記錄的關(guān)鍵字值大于給定值k時(shí)檢索失敗。 精算點(diǎn)檢索算法描畫 n這種與順序檢索相結(jié)合的精算點(diǎn)檢索算法可描畫如下：n int precisesearch(sqlist R,keytype k)n int low,mid,high;n low=1; high=n;n mid=low+(k-Rlow.key)*(high-low)/n (Rhigh.key-Rlow.key)+0.5;n if(k=Rmid.key)n return mid; n elsen if(kk)n mid-; 精算點(diǎn)檢索算法描畫續(xù) if(Rmid.key=k

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

27、；n精算點(diǎn)檢索是平均性能最好的檢索方法，對(duì)于檢索表較大和分布較均勻時(shí)，運(yùn)用精算點(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)檢索算法分析n 分塊檢索blocking search，又稱作索引檢索，它是順序檢索的一種改良方法，其效率介于順序檢索和二分法檢索之間。n 分塊檢索不要求檢索表中一切記錄關(guān)鍵值有序陳列，但要求把檢索表分成假設(shè)干塊之后各塊之間按關(guān)鍵字值大小有序。n即分塊檢索要求檢索表的特點(diǎn)是：塊間有序，塊內(nèi)無序。n所謂塊間有序是指塊間升序或塊間降序。n在塊間升序時(shí)，每一塊中一切記錄的關(guān)

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

29、算法分析續(xù)n以下圖中給出了一張塊間降序的檢索表的索引表，每個(gè)塊在索引表中也是一個(gè)索引項(xiàng)，但索引項(xiàng)中包含的是塊中最小的關(guān)鍵字值和該塊第一個(gè)記錄在檢索表中的位置。n該例中檢索表分為四塊，各塊中最小關(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)鍵字值22。 精算點(diǎn)檢索的根本思想n分塊檢索的根本思想是：n首先根據(jù)給定值在索引表中檢索，以確定待查找記錄所屬的塊；n由于索引表是有序表，所以可以用二分

30、法檢索，也可以用順序檢索或其它檢索方法進(jìn)展。n然后在確定的塊內(nèi)檢索關(guān)鍵字值等于給定值的記錄，由于塊內(nèi)記錄無序陳列，所以只能用順序檢索方法進(jìn)展。精算點(diǎn)檢索舉例n例如，要在前例“塊間升序的檢索表及其索引表例如中檢索k=38的記錄：n先將k依次和索引表中各個(gè)最大關(guān)鍵字進(jìn)展比較，由于22k48，所以k=38的記錄假設(shè)存在必在第二個(gè)塊中；n然后從第二個(gè)塊的起始地址開場(chǎng)順序檢索，直到R10.key=k時(shí)檢索勝利。n再如檢索k=76的記錄：n將k和索引表中各個(gè)最大關(guān)鍵字值比較，由于48k50那么在右子樹中繼續(xù)檢索；再用80和右子樹的根70比較，8070那么繼續(xù)在當(dāng)前根結(jié)點(diǎn)70的右子樹中檢索；當(dāng)再次和新的當(dāng)前

31、根結(jié)點(diǎn)比較時(shí)二者相等檢索勝利，前往指向當(dāng)前根結(jié)點(diǎn)的指針。n又如檢索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。 二叉檢索樹的二叉鏈表類型n 設(shè)二叉檢索樹以如下描畫的二叉鏈表作為存儲(chǔ)構(gòu)造：n typedef struct noden keytype key; /*關(guān)鍵字域*/n elemtype other; /*其它數(shù)據(jù)域*/n struct node *lchild, *rchild;n /*

32、左右孩子指針域*/n bstnode; /*定義結(jié)點(diǎn)類型bstnode*/n typedef bstnode *bstlist; n /*定義二叉檢索樹表類型bstlist*/二叉檢索樹的檢索算法描畫 n 二叉檢索樹的檢索算法可描畫如下：n bstlist bstsearch(bstlist t,keytype k)n bstlist p ; n p=t; n if(p=NULL)|(p-key=k)n return p; n elsen if(p-keyrchild,k);n elsen return bstsearch(p-lchild,k);n /*bstsearch end*/2.二叉

33、檢索樹的構(gòu)造過程和插入操作 n對(duì)于一組關(guān)鍵字無序的記錄，構(gòu)造其相應(yīng)的二叉檢索樹的方法是：從一棵空的二叉檢索樹開場(chǎng)，每當(dāng)讀入一個(gè)記錄就生成一個(gè)結(jié)點(diǎn)，然后按關(guān)鍵字值的大小插入到當(dāng)前的二叉檢索樹之中；當(dāng)一切記錄的結(jié)點(diǎn)都已插入二叉檢索樹中時(shí)便構(gòu)造終了。n雖然，插入操作是構(gòu)造二叉檢索樹的關(guān)鍵操作。要保證在一棵二叉檢索樹中插入一個(gè)結(jié)點(diǎn)之后，依然滿足二叉檢索樹的定義。其插入過程為：n假設(shè)二叉檢索樹為空，那么插入結(jié)點(diǎn)作為新的根結(jié)點(diǎn)；n假設(shè)二叉檢索樹非空，那么在非空的二叉檢索樹中檢索插入結(jié)點(diǎn)；假設(shè)檢索勝利就不用插入，否那么插入結(jié)點(diǎn)作為新的葉結(jié)點(diǎn)，并成為檢索途徑上最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子。 二叉檢索樹的構(gòu)造過

34、程和插入操作(續(xù))n為了實(shí)現(xiàn)這一插入過程，在二叉檢索樹非空時(shí)需求知道檢索途徑上的最后一個(gè)結(jié)點(diǎn)位置，才可以準(zhǔn)確地把插入結(jié)點(diǎn)作為左孩子或右孩子插入二叉檢索樹中；為此；需求在檢索過程中設(shè)一指針變量記下當(dāng)前結(jié)點(diǎn)的前趨即雙親結(jié)點(diǎn)位置。n插入算法的方式化描畫如下：n bstlist insertbst(bstlist t,keytype k)n bstlist s,p,q; n if(t=NULLl)n p=(bstlist)malloc(sigeof(bstnode);n p-key=k; p-lchild=NULL; p-rchild=NULL;n p-other=data; n return p;

35、二叉檢索樹的構(gòu)造過程和插入操作(續(xù)) p=t; while(p!=NULL) q=p; if(p-key=k) /*檢索勝利不用插入*/ return t; /*前往原二叉檢索樹*/ else if(p-keyrchild; else p=p-lchild; p=(bstlist)malloc(sizeof(bstnode); 二叉檢索樹的構(gòu)造過程和插入操作(續(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; 二叉檢索(排序)樹構(gòu)造過程

36、舉例 n從空樹出發(fā)經(jīng)過一系列的檢索插入操作之后，就可生成一棵二叉檢索樹。一個(gè)無序序列可以經(jīng)過構(gòu)造一棵二叉檢索樹而變成一個(gè)有序序列即中序遍歷次序序列，構(gòu)造的過程就是對(duì)無序序列進(jìn)展排序的過程，所以又稱作二叉排序樹。n設(shè)關(guān)鍵字序列為45，22，57，18，29，92，生成二叉檢索樹即二叉排序樹的過程如以下圖所示。 3.二叉樹檢索樹的刪除操作 n在二叉檢索樹中刪除一個(gè)結(jié)點(diǎn)，相當(dāng)于在檢索表中刪除一個(gè)記錄，不能把以待刪除結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹全部刪去，并且要保證刪除某個(gè)結(jié)點(diǎn)后的二叉樹依然是一棵二叉檢索樹。下面，我們分三種情況討論如何在二叉檢索樹中刪除一個(gè)結(jié)點(diǎn)。n 待刪除結(jié)點(diǎn)是度為0的葉子結(jié)點(diǎn)n 刪除一個(gè)葉子結(jié)

37、點(diǎn)*p，不破壞整棵樹的構(gòu)造，只需將其雙親結(jié)點(diǎn)*f與*p之間相鏈接的指針域置為空即可：n f-lchild=NULL; 或 f-rchild=NULL;二叉樹檢索樹的刪除操作續(xù) 待刪除結(jié)點(diǎn)是度為1的單枝結(jié)點(diǎn) 即待刪除結(jié)點(diǎn)只需左子樹或只需右子樹的情況，如以下圖所示。此時(shí)只需將待刪除結(jié)點(diǎn)*p的獨(dú)一后繼結(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;二叉樹檢索樹的刪除操作續(xù) 待刪除

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

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

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

41、child!=NULL)n q=q-rchild;n而方法二和方法四中*p的中序后繼*q即右子樹中的最左下結(jié)點(diǎn)確實(shí)定方法為：n q=p-rchild;n while(q-lchild!=NULL)n q=q-lchild;二叉檢索樹的刪除算法描畫 n下面我們給出采用方法四刪除雙枝結(jié)點(diǎn)時(shí)的二叉檢索樹的刪除算法描畫如下：n bstlist deletebst(bstlist t,keytype k)n bstlist p,q,r,f;n p=t; n f=NULL;n while(p!=NULL)&(k!=p-key) n f=p;n if(kkey)n p=p-lchild;n else

42、n p=p-rchild;n 二叉檢索樹的刪除算法描畫續(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;二叉檢索樹的刪除算法描畫續(xù) if(p!=q) q-lchild= p-lchild; if(f-lchild=p) f-lchild=r; else f

43、-rchild=r; return t; /*前往刪除操作后的二叉檢索樹*/ /*deletebst end*/4.二叉檢索樹的檢索性能分析n在二叉檢索樹上檢索關(guān)鍵字值等于給定值k的記錄，正好是走了一條從根結(jié)點(diǎn)到關(guān)鍵字值為k的結(jié)點(diǎn)的途徑，和給定值k的比較次數(shù)為途徑長(zhǎng)度加1或結(jié)點(diǎn)所在層次數(shù)，和二分法檢索類似，其比較次數(shù)不超越樹的深度。n然而，用二分法檢索一個(gè)長(zhǎng)度為n的檢索表其檢索過程的二叉樹表示是獨(dú)一的，而含有n個(gè)結(jié)點(diǎn)的二叉檢索樹卻不獨(dú)一。 二叉檢索樹的檢索性能分析舉例n例如，如以下圖給出了結(jié)點(diǎn)值都一樣的兩棵二叉檢索樹，由于構(gòu)造時(shí)的關(guān)鍵字序列不同，前者深度為3，而后者深度為7；在等概率的情況下，

44、前者的平均檢索長(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。 二叉檢索樹的檢索性能分析續(xù)n 因此，含有n個(gè)結(jié)點(diǎn)的二叉檢索樹的平均檢索長(zhǎng)度和二叉檢索樹的形狀有關(guān)，領(lǐng)先后插入的關(guān)鍵字按值有序時(shí)，構(gòu)造的二叉檢索樹蛻變?yōu)閱沃?；n升序時(shí)為單右枝二叉樹，降序時(shí)為單左枝二叉樹；n樹的深度為n，平均檢索長(zhǎng)度為(n+1)/2和順序檢索一樣，這是最差的情況。最好的情況是二叉檢索樹的形狀和二分法檢索過程得到的樹一樣，樹的高度和 完 全 二 叉 樹 的 高 度 一 樣 ， 其 平 均 檢 索 長(zhǎng) 度為 。二叉檢索樹的檢索性

45、能分析續(xù)n如今我們思索在普通情況下二叉檢索樹的平均檢索長(zhǎng)度，假設(shè)在含有n個(gè)結(jié)點(diǎn)的二叉樹中，有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)鍵字值。n在等概率檢索的情況下平均檢索長(zhǎng)度為：n其中，p(i)為含有i個(gè)結(jié)點(diǎn)的二叉檢索樹的平均檢索長(zhǎng)度；p(i)+1為檢索左子樹中每個(gè)結(jié)點(diǎn)所用比較次數(shù)的平均值，p(n-i-1)+1為檢索右子樹中每個(gè)結(jié)點(diǎn)所用比較次數(shù)的平均值。 二叉檢索樹的檢索性能分析續(xù)n由于根結(jié)點(diǎn)的左子樹中有0個(gè)，1個(gè)，n-1個(gè)結(jié)點(diǎn)的情況是等概率的，對(duì)上式取平均值得：n用數(shù)學(xué)歸納法可以證明， ，即二叉檢索樹的平均長(zhǎng)度為 。7.3 樹表的檢索7.3.1 二叉檢索樹

46、7.3.2 二叉檢索樹的平衡性調(diào)整7.3.3 B樹和B+樹平衡因子n平衡因子balance factorn二叉樹上任一結(jié)點(diǎn)的平衡因子，定義為該結(jié)點(diǎn)的左子樹深度減去右子樹深度的差。n如以下圖中給出了一些二叉樹，其結(jié)點(diǎn)上所示數(shù)值為該結(jié)點(diǎn)的平衡因子值。平衡二叉樹n平衡二叉樹balance binary treen假設(shè)一棵二叉樹中一切結(jié)點(diǎn)的平衡因子的絕對(duì)值不超越1，那么稱該二叉樹為平衡二叉樹；平衡二叉樹也稱作AVL樹。n顯然，AVL樹要么是一棵空樹，要么其左右子樹深度不超越1且都是AVL樹；只需二叉樹上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，該二叉樹就是不平衡的。如前例圖中，(a)和(b)都是平衡二叉樹即

47、AVL樹，而(c)和(d)都不是平衡二叉樹即非AVL樹。 平衡二叉樹續(xù)n由于AVL樹具有良好的形狀，其左右子樹的深度差不超越1；對(duì)于給定的結(jié)點(diǎn)數(shù)目n，AVL樹的平均深度接近于完全二叉樹的深度 ；n所以我們希望由任何初始序列構(gòu)成的二叉檢索樹都是AVL樹，使得其平均檢索長(zhǎng)度接近于 。 n如何使構(gòu)造的二叉樹成為AVL樹呢？Adelson-Velskii和Landis提供了一個(gè)動(dòng)態(tài)地堅(jiān)持二叉檢索樹平衡性的方法；n其根本思想是在構(gòu)造二叉檢索樹的過程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)后都去檢查能否由于該結(jié)點(diǎn)的插入而破壞了二叉檢索樹的平衡性；假設(shè)出現(xiàn)絕對(duì)值超越1的平衡因子，那么需求在堅(jiān)持二叉檢索樹特性的前提下經(jīng)過調(diào)整使之

48、到達(dá)新的平衡。 平衡二叉樹續(xù)n在普通情況下，設(shè)在插入結(jié)點(diǎn)的過程中使二叉檢索樹失去平衡的最小子樹的根結(jié)點(diǎn)為a，即a為離插入結(jié)點(diǎn)最近且平衡因子絕對(duì)值超越1的祖先結(jié)點(diǎn)；n因插入結(jié)點(diǎn)的位置不同而失去平衡需求調(diào)整的規(guī)律可歸納為如下四種情況：nLL型平衡旋轉(zhuǎn)右單旋型 nRR型平衡旋轉(zhuǎn)左單旋型 nLR型平衡旋轉(zhuǎn)先左后右雙旋型 nRL型平衡旋轉(zhuǎn)先右后左雙旋型 1.LL型平衡旋轉(zhuǎn)右單旋型n這種失衡是由于在結(jié)點(diǎn)a的左孩子b的左子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)a的平衡因子由1增至2而呵斥的。n其調(diào)整戰(zhàn)略是以a的左孩子b為軸心順時(shí)針旋轉(zhuǎn)即向右旋轉(zhuǎn)一次；使結(jié)點(diǎn)a成為其左孩子b的右孩子，而b的右子樹成為a的左子樹，如以下圖所示。這

49、種調(diào)整戰(zhàn)略既使結(jié)點(diǎn)的平衡因子滿足AVL樹的要求，又堅(jiān)持了二叉檢索樹的特性即中序遍歷次序?yàn)樯仙蛄小?2.RR型平衡旋轉(zhuǎn)左單旋型n這種失衡是由于在結(jié)點(diǎn)a的右孩子b的左子樹上插入結(jié)點(diǎn)，使a的平衡因子由-1變成-2而呵斥的；n其調(diào)整戰(zhàn)略是以a的右孩子b 為軸心逆時(shí)針旋轉(zhuǎn)即向左旋轉(zhuǎn)一次；使a成為b的左孩子，而b的左子樹成為a的右子樹，如以下圖所示。 3. LR型平衡旋轉(zhuǎn)先左后右雙旋型 n這種失衡是由于在結(jié)點(diǎn)a的左孩子b的右子樹上插入結(jié)點(diǎn)，使a的平衡因子由1增至2呵斥的。n設(shè)c是b的右孩子，插入結(jié)點(diǎn)的位置有三種能夠性：nc就是插入結(jié)點(diǎn)，這是由于插入前b為葉子結(jié)點(diǎn)且a無右孩子而產(chǎn)生的一種能夠；n插入結(jié)點(diǎn)在

50、c的左子樹上；n插入結(jié)點(diǎn)在c的右子樹上。 LR型平衡旋轉(zhuǎn)續(xù) n對(duì)這三種導(dǎo)致LR型失衡的情況，其調(diào)整戰(zhàn)略是一致的：n即以a的左孩子b的右孩子c為軸心，先逆時(shí)針即向左旋轉(zhuǎn)一次，再順時(shí)針即向右旋轉(zhuǎn)一次；使c的左子樹成為b的右子樹，c的右子樹成a的左子樹，b成為c的左孩子而a成為c的右孩子，以“插入在c的左子樹上為例，兩次旋轉(zhuǎn)的調(diào)整過程如以下圖所示。 4. RL型平衡旋轉(zhuǎn)先右后左雙旋型 n這種失衡是由于在結(jié)點(diǎn)a的右孩子b的左子樹上插入結(jié)點(diǎn)，使a的平衡因子由-1變成-2呵斥的，設(shè)c是b的左孩子，插入結(jié)點(diǎn)位置的三種能夠性如以下圖所示：RL型平衡旋轉(zhuǎn)續(xù) n對(duì)這三種導(dǎo)致RL型失衡的情況，其調(diào)整戰(zhàn)略為：n以a的

51、右孩子b的左孩子c為軸心，先順時(shí)針即向右旋轉(zhuǎn)一次，再逆時(shí)針即向左旋轉(zhuǎn)一次；使c的左子樹成為a的右子樹，c的右子樹成為b的左子樹，a成為c的左孩子而b成為c的右孩子。以“插入在c的左子樹上為例，兩次旋轉(zhuǎn)的調(diào)整過程如以下圖所示：構(gòu)造平衡二叉檢索樹舉例 n例如，對(duì)于一組記錄其關(guān)鍵字序列為18，5，10，15，12，11，20，要建立一棵平衡的二叉檢索樹，其構(gòu)造過程如以下圖所示： 構(gòu)外型平二叉檢索樹的算法n 在設(shè)計(jì)構(gòu)造平衡的二叉檢索樹的算法時(shí)，需求先為每個(gè)結(jié)點(diǎn)添加一個(gè)平衡因子域，然后在二叉檢索樹構(gòu)造算法的根底上做幾點(diǎn)修正：n 插入一個(gè)結(jié)點(diǎn)后，要修正樹中各結(jié)點(diǎn)平衡因子的值；n 判別能否因插入結(jié)點(diǎn)產(chǎn)生失衡

52、，在失衡時(shí)找到失衡的最小子樹；n 判別失衡類型并做相應(yīng)的調(diào)整處置。n在平衡的二叉檢索樹上進(jìn)展檢索的過程，和在二叉檢索樹上的檢索過程一致，在檢索過程中和給定值比較的次數(shù)不會(huì)超越樹的深度，而含有n個(gè)結(jié)點(diǎn)的平衡二叉檢索樹的最大深度為 ，n 其中 。7.3 樹表的檢索7.3.1 二叉檢索樹7.3.2 二叉檢索樹的平衡性調(diào)整7.3.3 B樹和B+樹B樹n B樹是一種平衡的多路檢索樹，是文件系統(tǒng)包括大型數(shù)據(jù)庫(kù)文件系統(tǒng)中的一種重要的數(shù)據(jù)組織構(gòu)造。n 一棵m階B樹，或者為空樹，或者為滿足以下特性的m叉樹：n 樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹即至多有m-1個(gè)關(guān)鍵字；n 除非根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，否那么至少有兩棵子樹即至少

53、有一個(gè)關(guān)鍵字；n 除根結(jié)點(diǎn)之外的一切非終端結(jié)點(diǎn)至少有棵子樹；B樹續(xù) 一切的非終端結(jié)點(diǎn)中包含以下信息： n，A0，k1，A1，k2，kn，An 其中： nnm-1為關(guān)鍵字的個(gè)數(shù)，即子樹個(gè)數(shù)為n+1； ki1in為關(guān)鍵字，且kiki+11in； Ai0in為指向其子樹的根結(jié)點(diǎn)的指針，且Ai0in所指子樹中一切結(jié)點(diǎn)的關(guān)鍵字值都小于ki+1，An所指子樹中一切結(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樹示全例n以下圖給出了一棵4階 B樹的例如： B樹的插入操作n在B樹上插入一個(gè)關(guān)鍵字

54、，不是象在二叉檢索樹中那樣添加一個(gè)葉子結(jié)點(diǎn)，而是在B樹的最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字。n假設(shè)該結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)小于m-1個(gè)那么插入完成；否那么添加后關(guān)鍵字個(gè)數(shù)由m-1個(gè)變?yōu)閙個(gè)與B樹定義不符，需求進(jìn)展結(jié)點(diǎn)的“分裂以滿足B樹定義。n結(jié)點(diǎn)的分裂方法為，把中間一個(gè)關(guān)鍵字拿出來插入到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)上，前后兩部分各自構(gòu)成一個(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)。n由這種分裂過程可見，B樹是由底向上生長(zhǎng)的。 B樹的插入操作舉例nB樹的插入過程如以下圖所示，圖中只畫出了非終端結(jié)點(diǎn)，省去了最底層的葉子結(jié)點(diǎn)。 B樹的刪除操作n 在B樹

55、上刪除一個(gè)關(guān)鍵字和插入關(guān)鍵字類似也是由底向上的調(diào)整過程，n先找到該關(guān)鍵字所在的結(jié)點(diǎn)并刪除這個(gè)關(guān)鍵字。n假設(shè)找到的結(jié)點(diǎn)是最底層的非終端結(jié)點(diǎn)，當(dāng)關(guān)鍵字個(gè)數(shù)大于那么刪除完成，否那么刪除后關(guān)鍵字個(gè)數(shù)由個(gè)變?yōu)閭€(gè)與B樹定義不符，需求進(jìn)展結(jié)點(diǎn)的“合并以滿足B樹定義。n合并的方法是把刪除了關(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í)繼續(xù)向上調(diào)整直到根結(jié)點(diǎn)。n假設(shè)找到的待刪除關(guān)鍵字所在結(jié)點(diǎn)不是底層非終端結(jié)點(diǎn)，那么是將該關(guān)鍵字用其B樹中的后繼替代，而刪除其后繼的信息。B樹的刪除操作舉例nB樹的刪除過程如以下圖所示： B樹的檢索操作n在

56、B樹中進(jìn)展檢索的過程是：n首先在根結(jié)點(diǎn)中所包含的關(guān)鍵字中檢索給定的關(guān)鍵字，假設(shè)找到那么檢索勝利，否那么確定待檢索關(guān)鍵字所在的子樹，并在該子樹中繼續(xù)檢索，直到檢索勝利或指針為空時(shí)檢索失敗。n例如，在前例中的一棵4階B樹中檢索關(guān)鍵字值為61的記錄，因根結(jié)點(diǎn)中不存在此關(guān)鍵字，那么到大于39的子樹中檢索；又由于子樹的根結(jié)點(diǎn)中沒有此關(guān)鍵字，而506180，故再到s所指子樹中檢索，在這個(gè)結(jié)點(diǎn)中含有61的關(guān)鍵字值那么檢索勝利。n又如在此4階B樹中檢索關(guān)鍵字值為75的記錄，也是沿前面的這一條道路檢索，由于s所指結(jié)點(diǎn)中沒有值為75的關(guān)鍵字而檢索失敗。 B樹的檢索操作續(xù)n B樹的檢索是在B 樹上找結(jié)點(diǎn)和在結(jié)點(diǎn)中找

57、關(guān)鍵字兩個(gè)根本操作的交叉進(jìn)展過程，待查關(guān)鍵字所在結(jié)點(diǎn)在B樹中的層次是決議B樹檢索效率的首要要素，最壞的情況下是含n個(gè)關(guān)鍵字的m階B樹的最大深度。n由B樹定義，第一層至少有1個(gè)結(jié)點(diǎn)，第二層至少有2個(gè)結(jié)點(diǎn)；由于除根結(jié)點(diǎn)外的每個(gè)非終端結(jié)點(diǎn)至少有n 棵子樹，那么第三層至少有2 個(gè)結(jié)點(diǎn)；依此類推，第h+1層至少有 個(gè)結(jié)點(diǎn)；而h+1層為葉子結(jié)點(diǎn)。假設(shè)m階B樹有n個(gè)關(guān)鍵字，那么葉子結(jié)點(diǎn)即查找不勝利的結(jié)點(diǎn)數(shù)為n+1，由此有 B+樹 nB+樹是運(yùn)用于文件系統(tǒng)中的B樹的一種變形樹，它與B樹的差別主要在于：n 有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字；n 一切葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息及指向相應(yīng)記錄的指針，且葉子結(jié)點(diǎn)

58、以關(guān)鍵字遞增順序鏈接；n 一切的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹中的最大或最小關(guān)鍵字。B+樹舉例 n如以下圖給出了一棵3階B+樹。n通常B+樹上有兩個(gè)指針，一個(gè)指向根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵字值最小的葉子結(jié)點(diǎn)。n因此，對(duì)于B+樹既可從根結(jié)點(diǎn)開場(chǎng)多級(jí)索引順序檢索，又可以從最小關(guān)鍵字開場(chǎng)順序檢索。 B+樹的操作 n在B+樹上進(jìn)展插入、刪除和檢索的過程與B樹根本類似。n在檢索過程中在非終端結(jié)點(diǎn)上找到給定值后并不終止，而是繼續(xù)向下直到葉子結(jié)點(diǎn)；因此無論是檢索勝利還是檢索失敗，每次檢索都是走了一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的途徑。nB+樹的插入僅在葉子結(jié)點(diǎn)上進(jìn)展，當(dāng)葉子結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于m時(shí)也要分裂

59、成兩個(gè)結(jié)點(diǎn)，并且其雙親結(jié)點(diǎn)中同時(shí)也包含這兩個(gè)結(jié)點(diǎn)的關(guān)鍵字最大值。nB+樹的刪除也在葉子結(jié)點(diǎn)中進(jìn)展，其在非終端結(jié)點(diǎn)中的值可以作為分界關(guān)鍵字存在；當(dāng)然在刪除后假設(shè)使結(jié)點(diǎn)中關(guān)鍵個(gè)數(shù)小于 時(shí)也要進(jìn)展結(jié)點(diǎn)的合并操作。 第7章 檢索及根本算法 7.1 檢索的概念7.2 線性表的檢索7.3 樹表的檢索7.4 哈希檢索哈希檢索 n在前兩節(jié)引見的線性表檢索和樹表檢索方法后，由于記錄在檢索表中的位置是隨機(jī)的或按關(guān)鍵字值大小次序陳列的，記錄的存儲(chǔ)位置和其關(guān)鍵字值之間不存在某種確定的關(guān)系，存儲(chǔ)位置依賴于關(guān)鍵字的初始隨機(jī)序列或在檢索表中其它關(guān)鍵字值的大小。n所以在檢索時(shí)需求進(jìn)展一系列的關(guān)鍵字值與給定值之間的比較，其檢索

60、效率和檢索過程中進(jìn)展的比較次數(shù)有關(guān)。n本節(jié)引見一種直接利用關(guān)鍵字值計(jì)算記錄在檢索表中的存儲(chǔ)位置來進(jìn)展檢索的方法哈希Hash檢索技術(shù)。 7.4 哈希檢索7.4.1 哈希檢索與哈希表 7.4.2 哈希函數(shù)的構(gòu)造方法7.4.3 地址沖突的消解戰(zhàn)略7.4.4 哈希表的檢索算法及性能分析哈希檢索與哈希表 n哈希檢索技術(shù)的初衷是組織理想形狀的檢索表。n檢索表的理想形狀是：把記錄的關(guān)鍵字值與記錄在檢索表中的存儲(chǔ)位置建立起某種一對(duì)一的關(guān)系，這種一對(duì)一的關(guān)系可以用關(guān)于關(guān)鍵字的一個(gè)函數(shù)h(key)來表示，這樣就可以不用進(jìn)展關(guān)鍵字與給定值的比較，而是直接根據(jù)給定的關(guān)鍵字值來直接計(jì)算得到記錄在檢索表中的存儲(chǔ)地址。 哈希檢索與