數(shù)據(jù)結(jié)構(gòu)與算法分析第八章查找

數(shù)據(jù)結(jié)構(gòu)與算法分析第八章查找第1頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月所謂搜索(查找檢索)，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象

1.搜索成功即找到滿足條件的數(shù)據(jù)對(duì)象,作為結(jié)果,可報(bào)告該對(duì)象在結(jié)構(gòu)中的位置,還可給出該對(duì)象中的具體信息2.搜索不成功或搜索失敗。作為結(jié)果,應(yīng)報(bào)告一些信息,如失敗標(biāo)志、位置等第2頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象(或記錄)組成在每個(gè)對(duì)象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一第3頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月實(shí)施搜索時(shí)有兩種不同的環(huán)境靜態(tài)環(huán)境搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變

靜態(tài)搜索表

動(dòng)態(tài)環(huán)境為保持較高的搜索效率,搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化動(dòng)態(tài)搜索表第4頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月查找算法的評(píng)價(jià)指標(biāo)查找成功:最少比較次數(shù)最多比較次數(shù)平均比較次數(shù)查找失敗:最少比較次數(shù)最多比較次數(shù)平均比較次數(shù)第5頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

以順序表或線性鏈表表示靜態(tài)查找表順序查找第6頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月ST.elem順序查找過(guò)程假設(shè)給定值e=64,要求ST.elem[k]=e,問(wèn):k=?kk第7頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月ST.elemiST.elemi60ikey=64key=60i64第8頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月intSearch_Seq(TBST,TYPEkey){ST.elem[0].key=key;//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;--i);//從后往前找

returni;//找不到時(shí)，i為0}第9頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月分析順序查找的時(shí)間性能第10頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月查找算法的平均查找長(zhǎng)度(AverageSearchLength)

為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值第11頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月其中:n為表長(zhǎng)，Pi

為查找表中第i個(gè)記錄的概率，且，Ci為找到該記錄時(shí)，曾和給定值比較過(guò)的關(guān)鍵字的個(gè)數(shù)第12頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在等概率情形pi=1/n,i=1,2,,n

在搜索不成功情形，ASLunsucc=n+1

第13頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月查找成功:最少比較次數(shù)1

最多比較次數(shù)n

平均比較次數(shù)(n+1)/2

查找失敗:最少比較次數(shù)n+1

最多比較次數(shù)n+1

平均比較次數(shù)n+1第14頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

上述順序查找表的查找算法簡(jiǎn)單，但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表折半查找

若以有序表表示靜態(tài)查找表，則查找過(guò)程可以基于“折半”進(jìn)行第15頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月基于有序順序表的折半搜索設(shè)n個(gè)對(duì)象存放在一個(gè)有序順序表中，并按其關(guān)鍵碼從小到大排好了序折半搜索時(shí),先求位于搜索區(qū)間正中的對(duì)象的下標(biāo)mid，用其關(guān)鍵碼與給定值x比較第16頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月1.Element[mid].key==x搜索成功2.Element[mid].key>x把搜索區(qū)間縮小到表的前半部分，繼續(xù)折半搜索3.Element[mid].key<x把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索如果搜索區(qū)間已縮小到一個(gè)對(duì)象，仍未找到想要搜索的對(duì)象，則搜索失敗第17頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月ST.elemST.length例如:key=64

的查找過(guò)程如下mid=(low+high)/2Low

指示查找區(qū)間的下界high

指示查找區(qū)間的上界第18頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月搜索成功的例子-101346810126012345678搜索lowmidhigh6

6810125678lowmidhigh665lowmidhigh6第19頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月搜索失敗的例子-101346810125012345678搜索lowmidhigh5

6810125678lowmidhigh655lowmidhigh5第20頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月intSearch_Bin(TBST,TYPEkey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;if(key<ST.elem[mid].key)high=mid-1;

if(key>ST.elem[mid].key)low=mid+1;}return0;}第21頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月搜索成功時(shí)檢測(cè)指針停留在樹中某個(gè)結(jié)點(diǎn)搜索不成功時(shí)檢測(cè)指針停留在某個(gè)外結(jié)點(diǎn)（失敗結(jié)點(diǎn)）3515455025102030搜索22搜索45第22頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月有序順序表的折半搜索的判定樹

(10,20,30,40,50,60)1050======30<<<<<<>>>>>>204060第23頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月先看一個(gè)具體的情況，假設(shè)：n=11分析折半查找的平均查找長(zhǎng)度6391425781011判定樹12233334444第24頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月查找成功:最少比較次數(shù)?

最多比較次數(shù)?

平均比較次數(shù)?

查找失敗:最少比較次數(shù)?

最多比較次數(shù)?

平均比較次數(shù)?第25頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月假設(shè)n=2h-1并且查找概率相等則

在n>50時(shí)，可得近似結(jié)果

一般情況下，表長(zhǎng)為n的折半查找的判定樹的深度和含有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同第26頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月索引順序查找1）由索引確定記錄所在區(qū)間2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找注意：索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造可見:

索引順序查找的過(guò)程也是一個(gè)“縮小區(qū)間”的查找過(guò)程第27頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月分塊查找查找過(guò)程：將表分成幾塊，塊內(nèi)無(wú)序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實(shí)現(xiàn)用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針第28頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月12345678910111213141516171822121389203342443824486058745786532248861713索引表查38第29頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月分塊查找方法評(píng)價(jià)第30頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月索引順序查找的平均查找長(zhǎng)度=

查找“索引”的平均查找長(zhǎng)度

+查找“順序表”的平均查找長(zhǎng)度第31頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月ASL最大最小兩者之間表結(jié)構(gòu)有序表、無(wú)序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找分塊查找第32頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月二叉排序樹（二叉查找樹）第33頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹（3）它的左、右子樹也都分別是二叉排序樹（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值第34頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月503080209010854035252388是二叉排序樹66不第35頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月二叉排序樹的

查找算法第36頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功

2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找

3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找否則:若二叉排序樹為空，則查找不成功第37頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月50308020908540358832查找關(guān)鍵字50505030403550508090==50,35,90,95第38頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月n個(gè)結(jié)點(diǎn)的二叉搜索樹的數(shù)目3個(gè)結(jié)點(diǎn)的二叉搜索樹122133132123123{123}{132}{213}{231}{312}{321}第39頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來(lái)，所以也稱二叉搜索樹為二叉排序樹第40頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在查找過(guò)程中，生成了一條查找路徑

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)或者從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止

——查找成功

——查找不成功第41頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月351545504025102030搜索45搜索成功

搜索28搜索失敗第42頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月查找性能的分析

對(duì)于每一棵特定的二叉排序樹，均可按照平均查找長(zhǎng)度的定義來(lái)求它的ASL值，顯然，由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長(zhǎng)度的值不同，甚至可能差別很大第43頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2第44頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

輸入數(shù)據(jù)，建立二叉搜索樹的過(guò)程輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981第45頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來(lái)的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大

第46頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}123111132223323第47頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月二叉平衡樹（AVL樹）第48頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對(duì)值不超過(guò)1

不平衡平衡ABCABCDEDE第49頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

結(jié)點(diǎn)的平衡因子

(balancefactor)每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字,給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差,這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子AVL樹任一結(jié)點(diǎn)平衡因子只能取-1,0,1第50頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1,則這棵二叉搜索樹就失去了平衡,不再是AVL樹如果一棵二叉搜索樹是平衡的,

且有n個(gè)結(jié)點(diǎn)，其高度可保持在

O(log2n),平均搜索長(zhǎng)度也可保持在O(log2n)第51頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月548254821是平衡樹不是平衡樹第52頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月平衡化旋轉(zhuǎn)如果在一棵平衡的二叉搜索樹中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化平衡化旋轉(zhuǎn)有兩類：?jiǎn)涡D(zhuǎn)(左旋和右旋)

雙旋轉(zhuǎn)(左旋加右旋和右旋加左旋)第53頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月每插入一個(gè)新結(jié)點(diǎn)時(shí),AVL樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變。因此,在插入一個(gè)新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子第54頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)第55頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn),其中一個(gè)是另一個(gè)的鏡像,其方向與不平衡的形狀相關(guān)如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化雙旋轉(zhuǎn)分為先左后右和先右后左兩類第56頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月右單旋轉(zhuǎn)R型左單旋轉(zhuǎn)L型第57頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月左右雙旋轉(zhuǎn)LR型右左雙旋轉(zhuǎn)RL型第58頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月左單旋轉(zhuǎn)

(RotateLeft,L型)第59頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月hhhACEBDhhh+1BACEDhhh+1CEABD+1+20+100在子樹E中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，產(chǎn)生不平衡(L型)以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)第60頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月右單旋轉(zhuǎn)

(RotateRight,R型)第61頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在子樹D中插入新結(jié)點(diǎn),該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，產(chǎn)生不平衡(R型)以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)hhhACEBDhh+1BACEDhhh+1CEABDh000-1-1-2第62頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

先左后右雙旋轉(zhuǎn)

(RotationLeftRight,LR型)第63頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在子樹F或G中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，產(chǎn)生不平衡(LR型)首先以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時(shí)針旋轉(zhuǎn)，以E代替原來(lái)B的位置，做左單旋轉(zhuǎn)再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，做右單旋轉(zhuǎn)第64頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月插入00-1-2+1-1hhACED0h-1h-1hhAh-1hBCEDB左單旋轉(zhuǎn)FGFG第65頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月00-200+1hhACED-2h-1hhhAh-1hBCEDB右單旋轉(zhuǎn)FGFG第66頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月先右后左雙旋轉(zhuǎn)

(RotationRightLeft,RL型)第67頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在子樹F或G中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成2，產(chǎn)生不平衡(RL型)首先以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，以D代替原來(lái)C的位置,做右單旋轉(zhuǎn)再以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)，做左單旋轉(zhuǎn)第68頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月插入右單旋轉(zhuǎn)+1000-1+10hhACEDh-1BFGh-1+2000hhACEhBFGh-1D第69頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月00+20-10hhACE+2h-1hhhAh-1hBCEDB左單旋轉(zhuǎn)FGFGD第70頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月構(gòu)造二叉平衡（查找）樹的方法在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)第71頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9第72頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}插入和調(diào)整過(guò)程如下161603163-10701-2左右雙旋731600073110-111612273161190-1-2右單旋37169000371126916110112第73頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月右左雙旋左單18183-116000732611-1971614002691110316027390182611-11691711261第74頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月1518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過(guò)程第75頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月B樹大型文件訪問(wèn)方法第76頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月B樹是一種平衡的多路

查找樹第77頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

在

m

階的B樹上，每個(gè)非終端結(jié)點(diǎn)可能含有：

n

個(gè)關(guān)鍵字Ki（1≤i≤n）n<m

n

個(gè)指向記錄的指針Di（1≤i≤n）

n+1

個(gè)指向子樹的指針Ai（0≤i≤n）多叉樹的特性第78頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大有序排列，即：K1<K2<…<KnAi-1所指子樹上所有關(guān)鍵字均小于KiAi所指子樹上所有關(guān)鍵字均大于Ki查找樹的特性第79頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月平衡樹的特性樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹其余所有非葉結(jié)點(diǎn)均至少含有m/2棵子樹，至多含有m

棵子樹第80頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找兩個(gè)過(guò)程交叉進(jìn)行查找過(guò)程第81頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置若查找不成功，則返回插入位置第82頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在查找不成功之后，需進(jìn)行插入顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)，有下列幾種情況插入第83頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n<m，不修改指針第84頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n=m，則需進(jìn)行“結(jié)點(diǎn)分裂”，令s=m/2，在原結(jié)點(diǎn)中保留（A0，K1，……，Ks-1，As-1）；建新結(jié)點(diǎn)（As，Ks+1，……，Kn，An）；將（Ks，p）插入雙親結(jié)點(diǎn)第85頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月若雙親為空，則建新的根結(jié)點(diǎn)第86頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月下列為3階B樹502040

80插入關(guān)鍵字=60

6080,9060809090

508060,30

4020305080305080第87頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點(diǎn)“借調(diào)”關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無(wú)關(guān)鍵字可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字)，則必須進(jìn)行結(jié)點(diǎn)的“合并”刪除第88頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在含N

個(gè)關(guān)鍵字的B樹上進(jìn)行一次查找，需訪問(wèn)的結(jié)點(diǎn)個(gè)數(shù)不超過(guò)

logm/2((N+1)/2)+1查找性能第89頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月是B樹的一種變型B+樹第90頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

每個(gè)葉子結(jié)點(diǎn)中含有n

個(gè)關(guān)鍵字和n

個(gè)指向記錄的指針；并且，所有葉子結(jié)點(diǎn)彼此相鏈接構(gòu)成一個(gè)有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)第91頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵字Ki即為其相應(yīng)指針Ai所指子樹中關(guān)鍵字的最大值所有葉子結(jié)點(diǎn)都處在同一層次上，每個(gè)葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于m/2和m之間第92頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月查找過(guò)程

在B+樹上，既可以進(jìn)行縮小范圍的查找，也可以進(jìn)行順序查找

在進(jìn)行縮小范圍的查找時(shí)，不管成功與否，都必須查到葉子結(jié)點(diǎn)才能結(jié)束

若在結(jié)點(diǎn)內(nèi)查找時(shí)，給定值≤Ki，則應(yīng)繼續(xù)在Ai所指子樹中進(jìn)行查找第93頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月插入和刪除類似于B樹進(jìn)行，即必要時(shí)，也需要進(jìn)行結(jié)點(diǎn)的“分裂”或“歸并”第94頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

5096

155062

78

96

717884

89

96

566220264350

3815sqroot第95頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月第96頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月第97頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

B+樹的刪除僅在葉結(jié)點(diǎn)上進(jìn)行。當(dāng)在葉結(jié)點(diǎn)上刪除一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后，結(jié)點(diǎn)中的子樹棵數(shù)仍然不少于m/2，這屬于簡(jiǎn)單刪除，其上層索引可以不改變。如果刪除的關(guān)鍵碼是該結(jié)點(diǎn)的最小關(guān)鍵碼，但因在其上層的副本只是起了一個(gè)引導(dǎo)搜索的“分界關(guān)鍵碼”的作用，所以上層的副本仍然可以保留。如果在葉結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后，該結(jié)點(diǎn)中的子樹棵數(shù)n小于結(jié)點(diǎn)子樹棵數(shù)的下限m/2，必須做結(jié)點(diǎn)的調(diào)整或合并工作。第98頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月刪除18刪除12第99頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月如果右兄弟結(jié)點(diǎn)的子樹棵數(shù)已達(dá)到下限m/2，沒有多余的關(guān)鍵碼可以移入被刪關(guān)鍵碼所在的結(jié)點(diǎn)，這時(shí)必須進(jìn)行兩個(gè)結(jié)點(diǎn)的合并。將右兄弟結(jié)點(diǎn)中的所有關(guān)鍵碼-指針?biāo)饕?xiàng)移入被刪關(guān)鍵碼所在結(jié)點(diǎn)，再將右兄弟結(jié)點(diǎn)刪去。第100頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月刪除33進(jìn)行結(jié)點(diǎn)合并第101頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月結(jié)點(diǎn)的合并將導(dǎo)致雙親結(jié)點(diǎn)中“分界關(guān)鍵碼”的減少，有可能減到非葉結(jié)點(diǎn)中子樹棵數(shù)的下限m/2

以下。這樣將引起非葉結(jié)點(diǎn)的調(diào)整或合并。如果根結(jié)點(diǎn)的最后兩個(gè)子女結(jié)點(diǎn)合并，樹的層數(shù)就會(huì)減少一層。第102頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

TheB*-Treesplitstwopagesforthree,andcombinesthreepagesintotwo.Inthisway,nodesarealways2/3full.第103頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

Trie樹是一棵度m

2的樹，它的每一層分支不是靠整個(gè)關(guān)鍵碼的值來(lái)確定，而是由關(guān)鍵碼的一個(gè)分量來(lái)確定。如下圖所示Trie樹，關(guān)鍵碼由英文字母組成。它包括兩類結(jié)點(diǎn)：元素結(jié)點(diǎn)和分支結(jié)點(diǎn)。元素結(jié)點(diǎn)包含整個(gè)key數(shù)據(jù)；分支結(jié)點(diǎn)有27個(gè)指針，其中有一個(gè)空白字符‘b’，用來(lái)終結(jié)關(guān)鍵碼；其它用來(lái)標(biāo)識(shí)‘a(chǎn)’,‘b’,...,‘z’等26個(gè)英文字母。Trie樹Trie樹的定義當(dāng)關(guān)鍵碼是可變長(zhǎng)時(shí)，Trie樹是一種特別有用的索引結(jié)構(gòu)。第104頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月第105頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

在第0層，所有的關(guān)鍵碼根據(jù)它們第0位字符,被劃分到互不相交的27個(gè)類中。因此，root→brch.link[i]指向一棵子Trie樹，該子Trie樹上所包含的所有關(guān)鍵碼都是以第i個(gè)英文字母開頭。若某一關(guān)鍵碼第j

位字母在英文字母表中順序?yàn)閕(i=0,1,,26),則它在Trie樹的第

j層分支結(jié)點(diǎn)中從第i

個(gè)指針向下找第

j+1位字母所在結(jié)點(diǎn)。當(dāng)一棵子Trie樹上只有一個(gè)關(guān)鍵碼時(shí)，就由一個(gè)元素結(jié)點(diǎn)來(lái)代替。在這個(gè)結(jié)點(diǎn)中包含有關(guān)鍵碼，以及其它相關(guān)的信息，如對(duì)應(yīng)數(shù)據(jù)對(duì)象的存放地址等。第106頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

Trie樹的搜索為了在Trie樹上進(jìn)行搜索，要求把關(guān)鍵碼分解成一些字符元素,并根據(jù)這些字符向下進(jìn)行分支。第107頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在Trie樹上插入bobwhite和bluejay后的結(jié)果第108頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月哈希查找(Hash)第109頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

以上討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系第110頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

查找的過(guò)程為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較

查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)第111頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

用這類方法表示的查找表，其平均查找長(zhǎng)度都不為零

不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進(jìn)行比較的順序不同第112頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置對(duì)于頻繁使用的查找表，希望ASL=0

即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系第113頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月在一般情況下，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以H(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個(gè)函數(shù)H(key)為哈希函數(shù)第114頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

哈希函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可第115頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而

H(key1)=H(key2)第116頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生第117頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

因此，在構(gòu)造這種特殊的“查找表”時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法第118頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月哈希表的定義

根據(jù)設(shè)定的哈希函數(shù)H(key)和所選處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“映象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的查找表稱為“哈希表”第119頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月構(gòu)造哈希函數(shù)的方法對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法

若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理

直接定址法平方取中法

除留余數(shù)法

折疊法

數(shù)字分析法第120頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月數(shù)字分析法

第121頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月此方法適合于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度

假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址第122頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月平方取中法第123頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響

此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象第124頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月折疊法第125頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加

此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多第126頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月直接定址法第127頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key或者

H(key)=akey+b此法適合于：地址集合的大小==關(guān)鍵字集合的大小第128頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月除留余數(shù)法第129頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

設(shè)定哈希函數(shù)為:H(key)=keyMODp

其中，p≤m(表長(zhǎng))并且

p

應(yīng)為不大于m的素?cái)?shù)或是不含20以下的質(zhì)因子第130頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小第131頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月處理沖突的方法“處理沖突”的實(shí)際含義是為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址1.開放定址法2.鏈地址法第132頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di

)MODm

i=1,2,…,s開放定址法(閉域法)第133頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月增量di

的三種取法第134頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月

1)線性探測(cè)再散列

di=ci

最簡(jiǎn)單的情況c=12)平方探測(cè)再散列

di=12,-12,22,-22,…,3)隨機(jī)探測(cè)再散列

di

是一組偽隨機(jī)數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測(cè))第135頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月即：產(chǎn)生的Hi

均不相同，且所產(chǎn)生的

s(m-1)個(gè)Hi值能覆蓋哈希表中所有地址。且要求：

增量di

應(yīng)具有“完備性”

隨機(jī)探測(cè)時(shí)的m

和di沒有公因子

平方探測(cè)時(shí)的表長(zhǎng)m必為形如4j+3

的素?cái)?shù)（如:7,11,19,23,…等）第136頁(yè)，課件共151頁(yè)，創(chuàng)作于2023年2月{19,01,23,14,55,68,11,82,36}H(key)=keyMOD1119012314