算法與數(shù)據(jù)結(jié)構(gòu)查找

關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)查找BUPTSCSTBUPT8.1基本概念與術(shù)語(yǔ)查找表同一類型的記錄(數(shù)據(jù)元素)的集合。查找指定某個(gè)值，在查找表中確定是否存在一個(gè)記錄，該記錄的關(guān)鍵字等于給定值。關(guān)鍵字記錄(數(shù)據(jù)元素)中的某個(gè)數(shù)據(jù)項(xiàng)的值。

主關(guān)鍵字該關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)記錄。

次關(guān)鍵字該關(guān)鍵字不能唯一標(biāo)識(shí)一個(gè)記錄。靜態(tài)查找表對(duì)查找表的查找僅是以查詢?yōu)槟康?，不改?dòng)查找表中的數(shù)據(jù)。動(dòng)態(tài)查找表在查找的過(guò)程中同時(shí)插入不存在的記錄，或刪除某個(gè)已存在的記錄。查找成功查找表中存在滿足查找條件的記錄。查找不成功查找表中不存在滿足查找條件的記錄。第2頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT內(nèi)查找整個(gè)查找過(guò)程都在內(nèi)存中進(jìn)行。外查找在查找過(guò)程中需要訪問(wèn)外存。平均查找長(zhǎng)度ASL——查找方法時(shí)效的度量為確定記錄在查找表中的位置，需將關(guān)鍵字和給定值比較次數(shù)的期望值。查找成功時(shí)的ASL計(jì)算方法：

n：記錄的個(gè)數(shù)

pi：查找第i個(gè)記錄的概率，

(不特別聲明時(shí)認(rèn)為等概率pi=1/n)ci：找到第i個(gè)記錄所需的比較次數(shù)約定：無(wú)特殊說(shuō)明，一般默認(rèn)關(guān)鍵字的類型為整型第3頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.2順序表的查找01n-1nr[0..n]a0a1an-1r[n].key=K[算法描述]intseqsearch(int*a,constintn,constintK)

{inti=0;a[n]=K;while(a[i]!=K)i++;returni;}第4頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[程序設(shè)計(jì)技巧]

設(shè)置監(jiān)視哨，提高算法效率。[性能分析]空間：一個(gè)輔助空間。時(shí)間：

1)查找成功時(shí)的平均查找長(zhǎng)度設(shè)表中各記錄查找概率相等

ASLs(n)=(1+2+...+n)/n=(n+1)/22)查找不成功時(shí)的平均查找長(zhǎng)度ASLf=n+1[算法特點(diǎn)]算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無(wú)任何要求n很大=>查找效率較低改進(jìn)措施：非等概率查找時(shí)，可將查找概率高的記錄盡量排在表前部。第5頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.3二分查找滿足r[i].keyr[i+1].key,0i<n-1

仍可用順序查找，但在找不到時(shí)不需比較到表尾，只需比較到比給定值大的記錄就可終止。[折半(二分)查找法]

1234567891011

0513192137566475808892lowmidhigh=(low+high)/2

K=21lhmK=85

lhm111611161537119454101110109第6頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[算法描述]intbinsearch(intK,intv[],intn){intlow,high,mid;low=1;high=n;while(low<=high){

mid=(low+high)/2;if(K<v[mid])

high=mid-1;elseif(K>v[mid])

low=mid+1;else/*找到了匹配的值*/returnmid;}return-1;/*沒(méi)有查到*/}第7頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[性能分析]

h=log2n+1{同完全二叉樹(shù)，二叉樹(shù)性質(zhì)4}成功查找時(shí)的平均查找長(zhǎng)度（等概率）：

ASLs=

例：ASLS=(1*1+2*2+3*4+4*4)/11=3不成功查找時(shí)的查找長(zhǎng)度：h-1或h次-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h判定樹(shù)（描述查找過(guò)程的二叉樹(shù)）外結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)><=第8頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT1.具有12個(gè)關(guān)鍵字的有序表，在等概率情況下，折半查找的平均查找長(zhǎng)度（）

A.3.1B.4C.2.5D.5

2.折半查找的時(shí)間復(fù)雜度為（）A.O（n2）B.O（n）C.O（nlogn）D.O（logn）3.用二分（對(duì)半）查找表的元素的速度比用順序法()A.必然快B.必然慢C.相等D.不能確定4.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵字比較次數(shù)為_(kāi)___.

在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標(biāo)依次為_(kāi)_________。ADD46,9,11,12第9頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.4靜態(tài)樹(shù)表的查找[問(wèn)題出發(fā)點(diǎn)]

討論有序表中各記錄查找概率不等時(shí)，查找成功時(shí)的ASLs。

12345

關(guān)鍵字1519364267

查找概率0.10.20.10.40.2

折半查找高概率為根

+折半

ASLs=2.3ASLs=1.8363151192424675424192675151363第10頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[靜態(tài)最優(yōu)查找樹(shù)]定義：查找性能最佳的判定樹(shù)。性質(zhì)：帶權(quán)內(nèi)路徑長(zhǎng)度之和PH為最小值。

PH=與ASLs成正比

其中n：二叉樹(shù)上結(jié)點(diǎn)的個(gè)數(shù)(有序表長(zhǎng)度)hi：第i個(gè)結(jié)點(diǎn)在二叉樹(shù)上的層次數(shù)

wi=cpi：c為某個(gè)常量；

pi：第i個(gè)結(jié)點(diǎn)的查找概率最優(yōu)查找體現(xiàn)的原則：

1）最先訪問(wèn)的結(jié)點(diǎn)應(yīng)是訪問(wèn)概率最大的結(jié)點(diǎn)；

2）每次訪問(wèn)應(yīng)使結(jié)點(diǎn)兩邊尚未訪問(wèn)的結(jié)點(diǎn)的被訪概率之和盡可能相等。第11頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[次優(yōu)查找樹(shù)的構(gòu)造方法]PH值近似為最小比靜態(tài)最優(yōu)查找樹(shù)易于構(gòu)造，時(shí)間開(kāi)銷少已知按關(guān)鍵字有(升)序的記錄序列：

(rl,rl+1,...,ri-1,ri,ri+1,...,rh-1,rh)1)選取記錄ri作為根結(jié)點(diǎn)：計(jì)算所有

pi(lih)

找出最小

pi的對(duì)應(yīng)的i；若相鄰關(guān)鍵字的權(quán)值大，則確定為權(quán)值大的關(guān)鍵字對(duì)應(yīng)的i第12頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT簡(jiǎn)化計(jì)算

pi的方法：設(shè)定累計(jì)權(quán)值和swi=

則

pi=|(swh-swi)-(swi-1-swl-1)|=|(swh+swl-1)-swi-swi-1|

設(shè)sw-1=02)ri的左子樹(shù)：(rl,rl+1,...,ri-1)構(gòu)造的次優(yōu)查找樹(shù)3)ri的右子樹(shù)：(ri+1,...,rh-1,rh)構(gòu)造的次優(yōu)查找樹(shù)第13頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT設(shè)有一組數(shù)據(jù)black,blue,green,purple,red,white,yellow，它們的查找概率分別為0.10,0.08,0.12,0.05,0.20,0.25,0.20。試以它們的查找概率為權(quán)值，構(gòu)造一棵次優(yōu)查找樹(shù)，并計(jì)算其查找成功的平均查找長(zhǎng)度。關(guān)鍵字blackbluegreenpurpleredwhiteyellow

權(quán)值0.100.080.120.050.200.250.20j1234567SWj0.10.180.300.350.550.801.00△Pj0.90.720.520.350.100.350.80

（根）↑i△Pj0.250.070.130.300.200.25

↑i

↑i△Pj0.050.12

↑i

第14頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.5分塊查找[索引表的構(gòu)造]

索引表index[0..b-1]

最大關(guān)鍵字值224286

起始地址048

主表r[0..n-1]（分塊有序/有序）

key12221382833384286765063

其它項(xiàng)

01234567891011[分塊查找步驟]1)折半或者順序查找索引表，確定所在塊2)在已確定的塊中順序查找/折半查找第15頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT設(shè)b為索引表長(zhǎng)度，s為塊中記錄個(gè)數(shù)順序查找索引表+順序查找被確定的塊

ASLbs=

當(dāng)s取時(shí)，ASLbs取最小值折半查找索引表+順序查找被確定的塊

ASLbs=[log2(b+1)-1]+(s+1)/2log2(n/s+1)+s/2實(shí)用中，各塊大小不一定相等分塊查找效率介于順序查找和折半查找之間第16頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT1.有一個(gè)2000項(xiàng)的表，欲采用等分區(qū)間順序查找方法進(jìn)行查找，則每塊的理想長(zhǎng)度是__(1)___，分成__(2)___塊最為理想，平均查找長(zhǎng)度是__(3)___。(1)45(2)45(3)46

第17頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.6二叉排序樹(shù)BST(二叉查找/搜索樹(shù))[定義]

二叉排序樹(shù)或者是空樹(shù)，或者是滿足如下性質(zhì)的二叉樹(shù)：

1)若其左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

2)若其右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值；

3)其左右子樹(shù)本身又各是一棵二叉排序樹(shù)[性質(zhì)]

中序遍歷一棵二叉排序樹(shù)，將得到一個(gè)以關(guān)鍵字遞增排列的有序序列452453122890判別給定二叉樹(shù)是否為二叉排序樹(shù)的算法如何實(shí)現(xiàn)？？（用二叉鏈表存儲(chǔ)）第18頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT方法1：根據(jù)二叉排序樹(shù)中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論。void

JudgeBST(BTreet,intflag){//全局指針pre，初值為NULL；調(diào)用時(shí)變量flag=TRUE

if(t!=NULL&&flag){JudgeBST(t->lc,flag)；//中序遍歷左子樹(shù)

if(pre==NULL)pre=t；//中序的第一個(gè)結(jié)點(diǎn)不判斷

else

if(pre->data<t->data)pre=t；//前驅(qū)指針指向當(dāng)前結(jié)點(diǎn)

elseflag=FLASE；//不是完全二叉樹(shù)

JudgeBST(t->rc,flag)；//中序遍歷右子樹(shù)

}}第19頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT方法2：照定義，二叉排序樹(shù)的左右子樹(shù)都是二叉排序樹(shù)，根結(jié)點(diǎn)的值大于左子樹(shù)中所有值而小于右子樹(shù)中所有值，即根結(jié)點(diǎn)大于左子樹(shù)的最大值而小于右子樹(shù)的最小值。boolJudgeBST(BTreet){

if(t==NULL)returnTRUE；

if(JudgeBST(t->lc)&&JudgeBST(t->rc)){m=max(t->llink)；

n=min(t->rlink)；//左子樹(shù)中最大值和右子樹(shù)中最小值

return(t->data>m&&t->data<n)；

}

else

returnFALSE；//不是}intmax(BTreep)//求左子樹(shù)的最大值

{if(p==NULL)return-maxint；

//返回機(jī)器最小整數(shù)

else{

while(p->rc！=null)p=p->rc；

returnp->data；}}intmin(BTreep)//求右子最小值

{if(p==NULL)returnmaxint；

else{while(p->lc!=NULL)p=p->lc；

returnp->data；}}第20頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[在二叉排序樹(shù)上的操作][1.查找][例]K=28K=32bst45241228bst455390241228325390

查找步驟：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。 否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，查其左子樹(shù)。 若大于根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹(shù)。在左右子樹(shù)上的操作類似。第21頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPTBitreeSearchBST(BiTreeT,KeyTypekey)//在二叉分類樹(shù)查找關(guān)鍵字之值為key的結(jié)點(diǎn)，找到返回該結(jié)//點(diǎn)的地址，否則返回空。T為根結(jié)點(diǎn)的指針。{

if((T==NULL)||(key==T->data))

return(T);

elseif(key<T->data.key)

return(SearchBST(T->lc,key));

elsereturn(SearchBST(T->rc,key));}[查找算法]第22頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[2.插入]首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。[3.生成][算法步驟]反復(fù)執(zhí)行以下操作a.讀入一個(gè)記錄，設(shè)其關(guān)鍵字為K；b.調(diào)用查找算法，確定插入位置；c.調(diào)用插入算法，實(shí)施插入結(jié)點(diǎn)的操作；第23頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT例：將序列122、99、250、110、300、280作為二叉排序樹(shù)的結(jié)點(diǎn)的關(guān)鍵字值，生成二叉排序樹(shù)。12212299122250991222501109912225030011099第24頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[4.刪除]依據(jù)被刪除結(jié)點(diǎn)p的不同情況分析：1.p是葉子結(jié)點(diǎn)：修改其雙親指針即可2.p只有左孩子：用p的左子樹(shù)代替以p為根的子樹(shù)p只有右孩子：用p的右子樹(shù)代替以p為根的子樹(shù)3.p有兩個(gè)孩子：找到p的中序后繼(或前趨)結(jié)點(diǎn)q，q的數(shù)據(jù)復(fù)制給p，刪除只有右子(或左子)/無(wú)孩子的q第25頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT例：(1)(2)(2)(3)5320901050869541241528891304539878992第26頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPTvoidDelete(BSTreeT,keytypeX)//在二叉排序樹(shù)T上，刪除為X的結(jié)點(diǎn)。

{BSTreef,p=T;while(p&&p->key!=X)//查找值為X的結(jié)點(diǎn)

if(p->key>X){f=p;p=p->lc;}//f為p的雙親

else{f=p;p=p->rc;}if(p==NULL){printf(“無(wú)關(guān)鍵字為X的結(jié)點(diǎn)\n”);exit(0);}if(p->lc==NULL)//被刪結(jié)點(diǎn)無(wú)左子樹(shù)

if(f->lc==p)f->lc=p->rc;//將被刪結(jié)點(diǎn)的右子樹(shù)接到其雙親上

elsef->rc=p->rc;else{//被刪結(jié)點(diǎn)有左子樹(shù)

q=p;s=p->lc;

while(s->rc!=NULL){//查左子樹(shù)中最右下的結(jié)點(diǎn)（中序最后結(jié)點(diǎn)）

q=s;s=s->rc;}p->key=s->key;//結(jié)點(diǎn)值用其左子樹(shù)最右下的結(jié)點(diǎn)的值代替

if(q==p)p->lc=s->lc;//被刪結(jié)點(diǎn)左子樹(shù)的根結(jié)點(diǎn)無(wú)右子女

elseq->rc=s->lc;//s是被刪結(jié)點(diǎn)左子樹(shù)中序序列最后一個(gè)結(jié)點(diǎn)

free(s);}}第27頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[4.性能分析]給定樹(shù)的形態(tài)，等概率查找成功時(shí)的ASL=ci/n最差(單支樹(shù))：(n+1)/2最好(類似折半查找的判定樹(shù))：log2(n+1)-1隨機(jī)：1+4log2n關(guān)鍵字有序出現(xiàn)時(shí)，構(gòu)造出“退化”的二叉排序樹(shù)，樹(shù)深為n，各種操作代價(jià)O(n)。避免方法：采用平衡二叉樹(shù)第28頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.7平衡二叉樹(shù)(AVL樹(shù))[1.定義]平衡二叉樹(shù)或者是空樹(shù)，或者是滿足如下性質(zhì)的二叉排序樹(shù)：

1)它的左、右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1；

2)其左右子樹(shù)本身又各是一棵平衡二叉樹(shù)。二叉樹(shù)上結(jié)點(diǎn)的平衡因子：該結(jié)點(diǎn)的左子樹(shù)高度減去右子樹(shù)的高度。平衡二叉樹(shù)非平衡二叉樹(shù)302010252235383020353233001-10-1100-12-2平衡二叉樹(shù)：每個(gè)結(jié)點(diǎn)的平衡因子都為＋1、－1、0的二叉排序樹(shù)。第29頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[2.結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)]lcbfkeyotherinforclc：左孩子指針

rc：右孩子指針

bf：平衡因子

key：記錄的關(guān)鍵字

otherinfo：記錄的其它數(shù)據(jù)成分第30頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[4.在平衡二叉樹(shù)上的操作][查找]查找方法同二叉排序樹(shù)。[插入]插入新結(jié)點(diǎn)之后仍應(yīng)保持平衡二叉樹(shù)的性質(zhì)不變。[例]平衡二叉樹(shù)的生成過(guò)程15001525-1-2-1000000-1-1001-2-20000-11525353525152515359015253590651525653590第31頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[調(diào)整范圍的確定]

插入結(jié)點(diǎn)后，找到離插入結(jié)點(diǎn)最近且平衡因子絕對(duì)值超過(guò)1的祖先結(jié)點(diǎn)（危機(jī)節(jié)點(diǎn)），則以該危機(jī)節(jié)點(diǎn)為根的子樹(shù)將是可能不平衡的最小子樹(shù)，可將重新平衡的范圍局限于這棵子樹(shù)。[調(diào)整的類型]LL型-表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子的左子樹(shù)上LR型-表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子的右子樹(shù)上RL型-表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子的左子樹(shù)上RR型-表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子的右子樹(shù)上第32頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[調(diào)整的方法]LL型平衡旋轉(zhuǎn)——一次順時(shí)針旋轉(zhuǎn)AB+1h-10+2+1hh-1h-1LL型調(diào)整BLBRARBA0h0h-1h-1BLBRAR危機(jī)結(jié)點(diǎn)調(diào)整前：高度為h+1

中序序列：ABBLBRAR調(diào)整后：高度為h+1

中序序列：ABBLBR注意：調(diào)整后平衡因子為0ABAR第33頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPTLR型平衡旋轉(zhuǎn)——一次逆時(shí)針旋轉(zhuǎn)+一次順時(shí)針旋轉(zhuǎn)AB+1h-10+2-1h-1LR型調(diào)整BLAR危機(jī)結(jié)點(diǎn)CBCCLCRh-2h-2h-10+1CB0h-1BLARACRh-2CLh-1-10ABBLARCCLCR調(diào)整后：高度為h+1

中序序列：ABBLARCCLCRA調(diào)整前：高度為h+1

中序序列：h-1情形A注意：調(diào)整后平衡因子為+1,0,0第34頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPTLR型平衡旋轉(zhuǎn)——一次逆時(shí)針旋轉(zhuǎn)+一次順時(shí)針旋轉(zhuǎn)AB+1h-10+2-1h-1LR型調(diào)整BLAR危機(jī)結(jié)點(diǎn)調(diào)整前：高度為h+1

中序序列：注意：改組后平衡度為+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1BLARACRh-1CLh-2+10ABBLARCCRCL調(diào)整后：高度為h+1

中序序列：AABBLARCCRCL情形B第35頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT注意：調(diào)整后平衡因子為0,0,0LR型平衡旋轉(zhuǎn)——一次逆時(shí)針旋轉(zhuǎn)+一次順時(shí)針旋轉(zhuǎn)AB+10+2-1LR型調(diào)整危機(jī)結(jié)點(diǎn)調(diào)整前：高度為2中序序列：CBC0ABCA新插入結(jié)點(diǎn)ABC調(diào)整后：高度為2中序序列：ca0b00情形C第36頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPTRR型平衡旋轉(zhuǎn)——一次逆時(shí)針旋轉(zhuǎn)AB-1h-10-2-1hh-1h-1RR型調(diào)整BLBRALBA0h0h-1h-1BLAL危機(jī)結(jié)點(diǎn)調(diào)整前：高度為h+1

中序序列：BAALBLBR調(diào)整后：高度為h+1

中序序列：注意：調(diào)整后平衡因子為0ABBRBAALBLBR第37頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPTRL型平衡旋轉(zhuǎn)——一次順時(shí)針旋轉(zhuǎn)+一次逆時(shí)針旋轉(zhuǎn)AALCRCLBRALCRCLBRALCLBRCRBCABCACB-100h-1h-2h-1h-211(-1)00(1)-1(0)危機(jī)結(jié)點(diǎn)第38頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[刪除]（思路同插入）將刪除結(jié)點(diǎn)q轉(zhuǎn)化為q最多有一個(gè)孩子的情形，即若q有兩個(gè)孩子，則以其中序前驅(qū)/后繼結(jié)點(diǎn)r取代它，刪除r；若樹(shù)的平衡性被破壞，利用單一/雙重旋轉(zhuǎn)恢復(fù)。[性能]定理：一個(gè)具有n個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)形，其高度h為

log2(n+1)h1.4404log2(n+2)-0.328

結(jié)論：最壞情況下，AVL樹(shù)的高度約為1.44log2n，而完全平衡的二叉樹(shù)高度約為log2n，因此AVL樹(shù)是接近最優(yōu)的，其平均查找長(zhǎng)度與log2n同數(shù)量級(jí)。第39頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.7B+樹(shù)與B-樹(shù)[采用B+與B-樹(shù)的意義]大量數(shù)據(jù)存放在外存中，由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次訪問(wèn)外存，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。內(nèi)存第40頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT用用二叉樹(shù)組織文件，需訪問(wèn)外存次數(shù)太多。如：當(dāng)文件的記錄個(gè)數(shù)為100，000時(shí)，要找到給定關(guān)鍵字的記錄，需訪問(wèn)外存17次（log100,000）,太長(zhǎng)了！502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭，可常駐內(nèi)存文件訪問(wèn)示意圖：索引文件存在內(nèi)存、數(shù)據(jù)文件存在盤(pán)上第41頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[B-樹(shù)]B-樹(shù)是一種平衡的多路查找樹(shù)。應(yīng)用于文件系統(tǒng)。1.定義一棵m階B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M足下列特性的m叉樹(shù)：

1、樹(shù)中每個(gè)結(jié)點(diǎn)最多有

m

棵子樹(shù)；

2、若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則最少有兩棵子樹(shù)；

3、除根之外的所有非終端結(jié)點(diǎn)最少有

m/2

棵子樹(shù)；

4、所有非終端結(jié)點(diǎn)包含（n,A0,K1,A1,K2,…,Kn,An）信息數(shù)據(jù)；其中n為結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，Ai為指向子樹(shù)的指針，Ki為關(guān)鍵字。

5、所有葉子結(jié)點(diǎn)在同一層上，且不帶信息。第42頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT例如：m=4階B_樹(shù)。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)至少為m/2=2個(gè)；結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為1。該B_樹(shù)的深度為4。葉子結(jié)點(diǎn)都在第4層上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第1層第2層第3層(L層)第4層(L＋1層)m/2~m棵子樹(shù)葉第43頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT2.B-樹(shù)結(jié)點(diǎn)結(jié)構(gòu)(n,A0,K1,A1,K2,A2,...,Kn,An)n:關(guān)鍵字的個(gè)數(shù)A0：<K1

的結(jié)點(diǎn)的地址（指在該B_樹(shù)中）K1：關(guān)鍵字A2：>K1

且<K2

的結(jié)點(diǎn)的地址（指在該B_樹(shù)中）其余類推………An：>Kn

的結(jié)點(diǎn)的地址（指在該B_樹(shù)中）K1<=K2<=…...<=Kn第44頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT127階B-樹(shù)中每個(gè)結(jié)點(diǎn)最多有____個(gè)關(guān)鍵字；除根結(jié)點(diǎn)外所有非終端結(jié)點(diǎn)至少有____棵子樹(shù)；65階B+樹(shù)中除根結(jié)點(diǎn)外所有結(jié)點(diǎn)至少有____個(gè)關(guān)鍵字；最多有____棵子樹(shù)。高度為5（除葉子層之外）的三階B-樹(shù)至少有____個(gè)結(jié)點(diǎn)。31126643365思考：高度為h的m階B-樹(shù)（除葉子層）至少有多少個(gè)結(jié)點(diǎn)？第45頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT3.B-樹(shù)查找過(guò)程類似于二叉樹(shù)的查找。如查找關(guān)鍵字為KEY的記錄。

從根開(kāi)始查找，如果Ki=KEY則查找成功。若Ki<KEY<Ki+1;查找Ai

指向的結(jié)點(diǎn)若KEY<K1;查找A0

指向的結(jié)點(diǎn)若KEY>Kn;查找An指向的結(jié)點(diǎn)若找到葉子，則查找失敗。第46頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT設(shè)關(guān)鍵字的總數(shù)為N，求m階B_樹(shù)的最大層次L。層次 結(jié)點(diǎn)數(shù) 關(guān)鍵字的個(gè)數(shù)（最少）

1 1 12 2 2(

m/2-1

)3 2(

m/2

) 2(

m/2

)(

m/2-1

) 4 2(

m/2

)2 2(

m/2

)2(

m/2-1

)………L 2(

m/2

)L-22(

m/2

)L-2(

m/2-1

)L+1 2(

m/2

)L-1

所以，N=2(

m/2

)L-1-1故：L＝log

m/2

((N+1)/2)+1設(shè)N＝1000，000且m＝256，則L<=3；最多3次訪問(wèn)外存可找到所有的記錄。第47頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT4.B-樹(shù)插入過(guò)程1、確定插入位置，將結(jié)點(diǎn)插入到第L層（注意：第L+1層為葉子結(jié)點(diǎn)）2、找到插入位置，將關(guān)鍵字和其它信息按序插入。3、若被插入結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)>m-1,則該結(jié)點(diǎn)滿。必須分裂成兩個(gè)結(jié)點(diǎn)。否則不滿結(jié)束。如結(jié)點(diǎn)原為：

(m-1,A0,K1,A1,K2,A2,…Km-1,Am-1)插入一個(gè)關(guān)鍵字之后變?yōu)椋?m,A0,K1,A1,K2,A2,…Km,Am)該結(jié)點(diǎn)以K

m/2

為界，進(jìn)行分裂：

………...(K

m/2

,p’)…………...(

m/2-1

,A0,(K1,A1)…(K

m/2-1,A

m/2-1)(m-

m/2

,A

m/2

,K

m/2+1…Km,Am)生成新結(jié)點(diǎn)p’,將原結(jié)點(diǎn)的后半部分復(fù)制過(guò)去。若分裂一直進(jìn)行到根結(jié)點(diǎn)，樹(shù)可能長(zhǎng)高一層。(Km/2,p’

)數(shù)據(jù)項(xiàng)插入上層結(jié)點(diǎn)之中PP’第48頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT例：3階B_樹(shù)的插入key=73，127243024，3045，7053902610039506185345，70539026100395061851230324457053902610039506185127303245390261003950618512745707插入第49頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT5.B-樹(shù)刪除過(guò)程1、查找具有給定鍵值的關(guān)鍵字Ki

2、如果在第L層，可直接刪除（注意：第L+1層為葉子結(jié)點(diǎn)），轉(zhuǎn)4。3、否則，則首先生成“替身”。用該關(guān)鍵字的右邊子樹(shù)中的最左面的結(jié)點(diǎn)的關(guān)鍵字取代。然后，刪除第L層上的該關(guān)鍵字。4、從第L層開(kāi)始進(jìn)行刪除。

A、不動(dòng)：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)仍處于

m/2

-1和m-1之間。則結(jié)束。

B、借：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)原為

m/2

-1。而它們左\右兄弟結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)>

m/2

-1;則借一關(guān)鍵字過(guò)來(lái)，結(jié)束。

C、并：若該結(jié)點(diǎn)的左\右兄弟結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)為

m/2

-1;則執(zhí)行合并結(jié)點(diǎn)的操作。如結(jié)點(diǎn)原為：（………….(Ki,Ai),(Ki+1,Ai+1),………….）

（A0’,(K1’,A1’)………）

（A0’’,(K1’’,A1’’)………）

……K1………第L層：找到了被刪結(jié)點(diǎn)的替身。第50頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT例如：3階B_樹(shù)的刪除操作。324455390371005061，70被刪關(guān)鍵字324456190371005370借：向被刪結(jié)點(diǎn)方向旋轉(zhuǎn)假定再刪除該關(guān)鍵字32445903710061，703，24459010061，703，24459010061，70并并并并：和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及兄弟合并。有可能進(jìn)行到根，使B_樹(shù)的深度降低一層！假定再刪除該關(guān)鍵字第51頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[B+樹(shù)]B+樹(shù)是一種B-樹(shù)的變形樹(shù)。應(yīng)用于索引順序文件系統(tǒng)。1.m階B+

樹(shù)與B-

樹(shù)的不同之處1)有n棵子樹(shù)的結(jié)點(diǎn)中有n個(gè)關(guān)鍵字；2)非葉結(jié)點(diǎn)可以看成是索引部分索引集Ai

：第i個(gè)子結(jié)點(diǎn)的指針Ki

：第i個(gè)子結(jié)點(diǎn)的最大（或最小）關(guān)鍵字3)所有葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息及指向這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)以關(guān)鍵字大小自小至大順序鏈接；數(shù)據(jù)集第52頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[結(jié)點(diǎn)結(jié)構(gòu)]非葉結(jié)點(diǎn)(A1,K1,...,Ai,Ki,...,An,Kn)索引集Ai

：第i個(gè)子結(jié)點(diǎn)的指針Ki

：第i個(gè)子結(jié)點(diǎn)的最大（或最小）關(guān)鍵字葉結(jié)點(diǎn)全部關(guān)鍵字及指向關(guān)鍵字記錄的指針數(shù)據(jù)集2153344047586727985390961052851323336785210513221141324階B+樹(shù)rootsqt第53頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT2.B+樹(shù)上的基本運(yùn)算1)查找方式1：從根結(jié)點(diǎn)開(kāi)始，利用索引集結(jié)構(gòu)，向下查找直到葉子結(jié)點(diǎn)方式2：從最小關(guān)鍵字開(kāi)始，沿葉結(jié)點(diǎn)數(shù)據(jù)集的鏈結(jié)構(gòu)順序查找2)插入

僅在葉子結(jié)點(diǎn)上進(jìn)行，關(guān)鍵字個(gè)數(shù)大于m則分裂3)刪除也僅在葉子結(jié)點(diǎn)上進(jìn)行，關(guān)鍵字個(gè)數(shù)小于

m/2時(shí)，需進(jìn)行合并第54頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT8.8哈希表[哈希表的基本思想]

在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，理想狀態(tài)不經(jīng)過(guò)比較，一次存取就能得到所查元素。[術(shù)語(yǔ)]

哈希表一個(gè)有限的連續(xù)的地址空間，用以容納按哈希地址存儲(chǔ)的記錄。

哈希函數(shù)記錄的存儲(chǔ)位置與它的關(guān)鍵字之間存在的一種對(duì)應(yīng)關(guān)系。Loc(ri)=H(keyi)

沖突對(duì)于keyikeyj，ij，出現(xiàn)的H(keyi)=H(keyj)的現(xiàn)象。第55頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT

同義詞在同一地址出現(xiàn)沖突的各關(guān)鍵字。

哈希(散列)地址根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法確定的記錄的存儲(chǔ)位置。

裝填因子表中填入的記錄數(shù)n和哈希表表長(zhǎng)m之比。

=n/m[設(shè)計(jì)哈希表的過(guò)程]1)明確哈希表的地址空間范圍。即確定哈希函數(shù)的值域。

2)選擇合理的哈希函數(shù)。該函數(shù)要保證所有可能的記錄的哈希地址均在指定的值域內(nèi)，并使沖突的可能性盡量小。

3)設(shè)定處理沖突的方法。哈希表bb+(m-1)L第56頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[哈希函數(shù)的基本構(gòu)造方法]構(gòu)造原則：算法簡(jiǎn)單，運(yùn)算量??；均勻分布，減少?zèng)_突。[1.直接定址法]H(key)=a*key+ba、b為常數(shù)e.g:令：a、b為1，有兩個(gè)關(guān)鍵字k1,k2值為10、1000；選10、1000作為存放地址。特點(diǎn)：計(jì)算簡(jiǎn)單，沖突最少。[2.數(shù)字分析法/基數(shù)轉(zhuǎn)換法]取關(guān)鍵字在某種進(jìn)制下的若干數(shù)位作為哈希地址。e.g:key=236076基數(shù)為10，看成是13進(jìn)制的。則：(236075)13=841547；選取4154作為散列地址(假設(shè)表長(zhǎng)m=10000)。第57頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[3.平方取中法]取關(guān)鍵字平方后的中間幾位作為哈希地址。e.g:(4731)2=22382361；選取82（假設(shè)m=100）。[4.隨機(jī)數(shù)法]

H(key)=random(key)特點(diǎn)：較適于關(guān)鍵字長(zhǎng)度不等時(shí)的情況。[5.折疊法]

將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進(jìn)位)作為哈希地址。e.g:key=381，412，975選取768或570作為散列地址（假設(shè)m=1000）。38141297517689752143811570＋＋第58頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[6.除留余數(shù)法]H(key)=keyMODp(pm)m:哈希表的表長(zhǎng)；p:最好為素?cái)?shù)最常用，余數(shù)總在0～p-1之間。通常p選<m的最大質(zhì)數(shù)如：m=1024,則p=1019。e.g:選取p為質(zhì)數(shù)的理由：設(shè)key值都為奇數(shù)，選p為偶數(shù)；則H(key)=keyMODp，結(jié)果為奇數(shù)， 一半單元被浪費(fèi)掉。設(shè)key值都為5的倍數(shù)，選p為95；則H(key)=keyMODp，結(jié)果為：0、5、10、15、……90奇數(shù)。4/5的單元被浪費(fèi)掉。第59頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[處理沖突的常用方法][1.開(kāi)放定址法(空缺編址法)]Hi=(H(key)+di)MODm

0H(key)m-1i=1,2,...,k(km-1)m:哈希表的表長(zhǎng)；di:增量序列1)線性探測(cè)再散列

di=1,2,...,m-1缺陷：有聚集(堆積)現(xiàn)象—非同義詞地址沖突。第60頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPTe.g:假定采用的hashing函數(shù)為：H(key)=keyMOD11假定的關(guān)鍵字序列為：17、60、29、38……；它們的散列過(guò)程為：H(17)=6H(60)=5H(29)=7H(38)=5012345678910Hashing表1760293838當(dāng)散列38時(shí)發(fā)生沖突，同60爭(zhēng)奪第5個(gè)單元解決辦法：探測(cè)下一個(gè) 空單元Hi=(H(key)+di)MOD11其中：di為1、2……10沖突：

初級(jí)沖突：不同關(guān)鍵字值的結(jié)點(diǎn)得到同一個(gè)散列地址。二次聚集：同不同散列地址的結(jié)點(diǎn)爭(zhēng)奪同一個(gè)單元。結(jié)果：沖突加劇，最壞時(shí)可能達(dá)到O(n)級(jí)代價(jià)。思考：假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測(cè)？k(k+1)/2第61頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT2)二次探測(cè)再散列

di=12,-12,22,-22,32,...,k2

km/2缺陷：不易探查到整個(gè)散列空間。3)偽隨機(jī)探測(cè)再散列di=偽隨機(jī)數(shù)序列4)雙重散列函數(shù)探查法

di=i*h1(key)0<im-1要求：h1(key)的值與m互素。m為素?cái)?shù)時(shí)，h1(key)可取1到m-1之間的任何數(shù)，建議：h1(key)=keymod(m-2)+1m為2的方冪時(shí)，h1(key)可取1到m-1之間的任何奇數(shù)注意：開(kāi)放定址法不宜執(zhí)行刪除操作第62頁(yè),共70頁(yè)，2024年2月25日，星期天BUPTSCSTBUPT[2.再哈希法]Hi

=RHi(key)