數(shù)據(jù)結構 第九章 查找

1第九章查找本章目標理解"查找表"的結構特點及各種表示方法的適用性；熟練掌握以順序表或有序表表示靜態(tài)查找表時的查找方法；熟練掌握二叉查找樹的構造和查找方法；理解二叉平衡樹的構造過程；熟練掌握哈希表的構造方法，深刻理解哈希表與其它結構的表的實質(zhì)性的差別；掌握描述查找過程的判定樹的構造方法，以及計算各種查找方法在等概率情況下查找成功時的平均查找長度。9.2

靜態(tài)查找表9.3

動態(tài)查找表9.4

哈希表9.1

基本概念和術語查找表：？關鍵字：？查找：？查找方法：？平均查找長度：？9.1基本概念和術語查找表：由同一類型的數(shù)據(jù)元素(或記錄)構成的集合。9.1基本概念和術語對查找表的操作1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。靜態(tài)查找表動態(tài)查找表關鍵字：是指數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。9.1基本概念和術語

學號姓名數(shù)學英語Java總分1214010301張國慶8090942641214010302

李光榮8570992541214010303

王宇田858087252………………1214010304

張國慶788873239主關鍵字：可以識別唯一的一個記錄；次關鍵字：能識別若干記錄。查找：根據(jù)某個給定值，在查找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素（或記錄）。9.1基本概念和術語當查找成功時給出整個記錄的信息，或指示該記錄在查找表中的位置；當查找不成功時給出“空記錄”或“空指針”。

學號姓名數(shù)學英語Java總分1214010301張國慶8090942641214010302

李光榮8570992541214010303

王宇田858087252………………1214010304

張國慶788873239如何進行查找？

查找的方法取決于查找表的結構。9.1基本概念和術語由于查找表中的數(shù)據(jù)元素之間存在著完全松散的關系，給查找?guī)聿槐?。為此，需要在元素之間人為地附加某種確定的關系，以方便按照某種規(guī)則進行查找，即需要用另外一種數(shù)據(jù)結構來表示查找表。

基于線性表的查找方法

基于樹的查找方法

基于哈希表的查找方法

適合于靜態(tài)查找表

適合于動態(tài)查找表

基于地址計算的查找方法統(tǒng)一約定如下：9.1基本概念和術語典型的關鍵字類型說明可以是：數(shù)據(jù)元素類型定義為：typedeffloatKeyType;

//實型typedefintKeyType;//整型typedefchar

*KeyType;//字符串型typedefstruct{KeyTypekey;

//關鍵字域…//其他域}ElemType;統(tǒng)一約定如下：9.1基本概念和術語//--對數(shù)值型關鍵字的比較約定為如下宏定義：//--對字符串型關鍵字：

#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)

<(b))#defineLQ(a,b)((a)<=(b))#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)平均查找長度(AverageSearchLength)：

為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數(shù)的期望值。9.1基本概念和術語?==niiiCPASL1其中:n

為表長；Pi

為查找表中查找第i個記錄的概率，且∑Pi=1；Ci為找到該記錄時，和給定值比較過的關鍵字個數(shù)。9.2

靜態(tài)查找表9.3

動態(tài)查找表9.4

哈希表9.1

基本概念和術語9.2

靜態(tài)查找表

9.2.2順序表的查找9.2.3

有序表的查找9.2.4

索引順序表的查找

9.2.1靜態(tài)查找表的定義使用線性表表示靜態(tài)查找表；可用順序或鏈式存儲結構實現(xiàn)查找操作。ADTStaticSearchTable{9.2.1靜態(tài)查找表的定義}ADTStaticSearchTable數(shù)據(jù)對象D:數(shù)據(jù)關系R:基本操作P:D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關鍵字，可唯一標識數(shù)據(jù)元素。數(shù)據(jù)元素同屬一個集合。Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());9.2.1靜態(tài)查找表的定義Create(&ST,n);Destroy(&ST);操作結果：構造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。初始條件：靜態(tài)查找表ST存在；操作結果：銷毀表ST。9.2.1靜態(tài)查找表的定義Search(ST,key);初始條件：靜態(tài)查找表ST存在，key為和查找表中元素的關鍵字類型相同的給定值；操作結果：若ST中存在其關鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。9.2.1靜態(tài)查找表的定義Traverse(ST,Visit());初始條件：靜態(tài)查找表ST存在，Visit是對元素操作的應用函數(shù)；操作結果：按某種次序對ST的每個元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()失敗，則操作失敗。9.2

靜態(tài)查找表

9.2.2順序表的查找9.2.3

有序表的查找9.2.4

索引順序表的查找

9.2.1靜態(tài)查找表的定義使用線性表表示靜態(tài)查找表；可用順序或鏈式存儲結構實現(xiàn)查找操作。9.2.2順序表的查找通常采用順序存儲結構:typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲空間基址，建表時

//按實際長度分配，0號單元留空intlength;

//表的長度}SSTable;假設給定值k=64,要求ST.elem[i].Key=k,問:i=?ST.elemiSSTableST；i9.2.2順序表的查找int

Search_Seq(SSTableST,KeyTypekey){//在順序表ST中順序查找其關鍵字等于key的數(shù)據(jù)元素，//若找到，則返回它在表中的位置，否則返回0。inti=1;

while(i<=ST.length&&

!EQ(ST.elem[i].key,key))++i;if(i<=ST.length)returni;

elsereturn0;}

//Search_Seq9.2.2順序表的查找ST.elemiST.elemi60key=6464key=60ii“哨兵”9.2.2順序表的查找int

Search_Seq(SSTableST,KeyTypekey){//改進算法。在順序表ST中順序查找其關鍵字等于key的數(shù)//據(jù)元素，若找到，則返回它在表中的位置，否則返回0。inti;ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);

//從后往前找returni;//返回找到元素在表中位置i（找不到時i為0）}

//Search_Seq9.2.2順序表的查找順序查找算法的時間性能分析：

?==niiiCPASL1平均查找長度對順序表而言，Ci=n-i+1

在等概率查找的情況下，

順序查找算法的平均查找長度為：ASL=nP1+(n-1)P2++2Pn-1+Pn若查找概率無法事先測定，則查找過程采取的改進辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss在Pn≥Pn-1≥···≥P2≥P1時取極小值。9.2.2順序表的查找9.2

靜態(tài)查找表

9.2.2順序表的查找9.2.3

有序表的查找9.2.4

索引順序表的查找

9.2.1靜態(tài)查找表的定義使用線性表表示靜態(tài)查找表；可用順序或鏈式存儲結構實現(xiàn)查找操作。9.2.3有序表的查找上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。9.2.3有序表的查找ST.elemST.length例如:key=64

的查找過程如下：lowhighmidlow

mid

midlow

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

指示查找區(qū)間的上界mid=(low+high)/2high9.2.3有序表的查找intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其關鍵字等于key的數(shù)據(jù)元素。//若找到，則函數(shù)值為該元素在表中的位置，否則為0。

low=1;high=ST.length;

//置區(qū)間初值

while(low<=high){mid=(low+high)/2;if（EQ(key,ST.elem[mid].key))returnmid;

//找到待查元素

elseif(LT(key,ST.elem[mid].key))high=mid-1;

//繼續(xù)在前半?yún)^(qū)間進行查找

elselow=mid+1;

//繼續(xù)在后半?yún)^(qū)間進行查找

}return0;

//順序表中不存在待查元素}//Search_Bin9.2.3有序表的查找假設：n=11分析折半查找的平均查找長度6391425781011判定樹12233334444Key:05131921375664758088929.2.3有序表的查找假設n=2h-1，并且查找概率相等則

在n>50時，可得近似結果

一般情況下，表長為n的折半查找的判定樹的深度和含有n個結點的完全二叉樹的深度相同,即小結：順序查找與折半查找的比較順序查找算法優(yōu)點：算法簡單，且適應面廣。缺點：平均查找長度較大。折半查找算法優(yōu)點：平均查找長度較小。缺點：適應面小,只能適用于有序表，且限于順序存儲結構，而不能用于線性鏈表。9.2

靜態(tài)查找表

9.2.2順序表的查找9.2.3

有序表的查找9.2.4

索引順序表的查找

9.2.1靜態(tài)查找表的定義使用線性表表示靜態(tài)查找表；可用順序或鏈式存儲結構實現(xiàn)查找操作。9.2.4索引順序表的查找

分塊查找又稱索引順序查找，是順序查找的一種改進方法。在此方法中，除表本身外，還需建立一個‘索引表’。如下圖所示：

若以索引順序表表示靜態(tài)查找表，則Search函數(shù)可用分塊查找來實現(xiàn)。22121389203342443824486058744986532248861713索引表

最大關鍵字起始地址表及其索引表9.2.4索引順序表的查找1）由索引確定記錄所在區(qū)間；2）在順序表的某個區(qū)間內(nèi)進行查找。注意：索引可以根據(jù)查找表的特點來構造?？梢?，索引順序查找的過程也是一個“縮小區(qū)間”的查找過程。查找過程：索引順序查找的平均查找長度=查找“索引”的平均查找長度+查找“順序表”的平均查找長度9.2

靜態(tài)查找表9.3

動態(tài)查找表9.4

哈希表9.1

基本概念和術語9.3

動態(tài)查找表

9.3.2二叉排序樹9.3.3

平衡二叉樹9.3.4

B-樹和B+樹

9.3.1動態(tài)查找表的定義使用樹結構表示動態(tài)查找表；使用鏈式存儲結構實現(xiàn)查找、插入和刪除操作。ADTDynamicSearchTable{9.3.1動態(tài)查找表的定義}ADTDynamicSearchTable數(shù)據(jù)對象D：數(shù)據(jù)關系R：基本操作P：D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關鍵字，可唯一標識數(shù)據(jù)元素。數(shù)據(jù)元素同屬一個集合。InitDSTable(&DT);DestroyDSTable(&DT);SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT,Visit());9.3.1動態(tài)查找表的定義InitDSTable(&DT);DestroyDSTable(&DT);操作結果：構造一個空的動態(tài)查找表DT。初始條件：動態(tài)查找表DT存在；操作結果：銷毀動態(tài)查找表DT。9.3.1動態(tài)查找表的定義SearchDSTable(DT,key);初始條件：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值；操作結果：若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。9.3.1動態(tài)查找表的定義InsertDSTable(&DT,e);初始條件：動態(tài)查找表DT存在，e

為待插入的數(shù)據(jù)元素；操作結果：若DT中不存在其關鍵字等于e.key的數(shù)據(jù)元素，則插入e到DT。9.3.1動態(tài)查找表的定義DeleteDSTable(&T,key);初始條件：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值；操作結果：若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則刪除之。9.3.1動態(tài)查找表的定義TraverseDSTable(DT,Visit());初始條件：動態(tài)查找表DT存在，Visit是對結點操作的應用函數(shù)；操作結果：按某種次序對DT的每個結點調(diào)用函數(shù)Visit()一次且至多一次。一旦Visit()失敗，則操作失敗。9.3

動態(tài)查找表

9.3.2二叉排序樹9.3.3

平衡二叉樹9.3.4

B-樹和B+樹

9.3.1動態(tài)查找表的定義使用樹結構表示動態(tài)查找表；使用鏈式存儲結構實現(xiàn)查找、插入和刪除操作。9.3.2二叉排序樹1．定義二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；（2）若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；（3）它的左、右子樹也都分別是二叉排序樹。503080209010854035252388例如:不是二叉排序樹。669.3.2二叉排序樹通常，取二叉鏈表作為二叉排序樹的存儲結構。typedefstructBiTNode{//結點結構

structBiTNode*lchild,*rchild;

//左右孩子指針

}BiTNode,*BiTree;TElemTypedata;9.3.2二叉排序樹2．二叉排序樹的查找算法若二叉排序樹為空，則查找不成功；否則，（1）若給定值等于根結點的關鍵字，則查找成功；（2）若給定值小于根結點的關鍵字，則繼續(xù)在左子樹上進行查找；（3）若給定值大于根結點的關鍵字，則繼續(xù)在右子樹上進行查找。9.3.2二叉排序樹例如:查找關鍵字==50,35,90,95,50308020908540358832二叉排序樹50505030403550508090查找失敗9.3.2二叉排序樹從上述查找過程可見，在查找過程中，生成了一條查找路徑：

從根結點出發(fā)，沿著左分支或右分支逐層向下直至關鍵字等于給定值的結點;或者

從根結點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功

——查找不成功9.3.2二叉排序樹算法描述如下：StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){

//在根指針T所指二叉排序樹中遞歸地查找其//關鍵字等于key的數(shù)據(jù)元素，若查找成功，//則返回指針p指向該數(shù)據(jù)元素的結點，并返回//函數(shù)值為TRUE;}//SearchBST…………

否則表明查找不成功，返回//指針p指向查找路徑上訪問的最后一個結點，//并返回函數(shù)值為FALSE,指針f指向當前訪問//的結點的雙親，其初始調(diào)用值為NULL算法9.59.3.2二叉排序樹if(!T)elseif(EQ(key,T->data.key))

elseif(LT(key,T->data.key))

else{p=f;returnFALSE;}//查找不成功{p=T;returnTRUE;}//查找成功SearchBST(T->lchild,key,T,p);

//在左子樹中繼續(xù)查找SearchBST(T->rchild,key,T,p);//在右子樹中繼續(xù)查找9.3.2二叉排序樹30201040352523fT設key=48fTfT22pfTfTTTTfffp9.3.2二叉排序樹3．二叉排序樹的插入算法

根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進行。插入規(guī)則：若二叉排序樹為空樹，則插入結點為新的根結點；否則，插入結點成為一個新的葉子結點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。例：若從空樹出發(fā)，經(jīng)過一系列的查找插入之后，可生成一棵二叉排序樹；設關鍵字序列為{45，24，53，12，24，90}，則生成的二叉排序樹如下：φ45452445245345245312452453124524531290ffffff9.3.2二叉排序樹StatusInsertBST(BiTree&T,ElemTypee){

//當二叉排序樹中不存在關鍵字等于e.key的//數(shù)據(jù)元素時，插入元素值為e的結點，并返//回TRUE;否則，不進行插入并返回FALSEif(!SearchBST(T,e.key,NULL,p)){}elsereturnFALSE;}//InsertBST……算法9.69.3.2二叉排序樹s=(BiTree)malloc(sizeof(BiTNode));

//為新結點分配空間s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//插入s為新的根結點elseif(LT(e.key,p->data.key))p->lchild=s;//插入*s為*p的左孩子elsep->rchild=s;//插入*s為*p的右孩子returnTRUE;//插入成功二叉排序樹的一些特性：（1）中序遍歷二叉排序樹可得到一個關鍵字的有序序列。例：關鍵字序列為{45，24，53，12，24，90}構造的二叉排序樹為：4524531290中序遍歷12，24，45，53，90（2）在構造二叉排序樹中，在進行插入新結點操作時，不必移動其它結點，僅需改動某個結點的指針，由空變?yōu)榉强占纯?。?）二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作為存儲結構,是動態(tài)查找表的一種適宜表示。9.3.2二叉排序樹4．二叉排序樹的刪除算法（1）被刪除的結點是葉子；（2）被刪除的結點只有左子樹或者只有右子樹；（3）被刪除的結點既有左子樹，也有右子樹?？煞秩N情況討論：和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結點之后，仍然保持二叉排序樹的特性。假設在二叉樹上被刪結點為*p,其雙親結點為*f,且*p是*f的左孩子,如圖:f→p→PlPr(1)結點*p為葉子結點.f→p→刪除f->lchild=NULL;50308020908540358832例如:被刪關鍵字=2088其雙親結點中相應指針域的值改為“空”(2)結點*p只有左子樹Pl或只有右子樹Pr.f→p→Pl或f→p→Prf->lchild=p->lchild;f->lchild=p->rchild;50308020908540358832其雙親結點的相應指針域的值改為“指向被刪除結點的左子樹或右子樹”。被刪關鍵字=4080例如：(3)結點*p的左子樹和右子樹均不空.f→p→PlPr第一種方法:令*p的左子樹為*f的左子樹,*p的右子樹為*S的右子樹.f→p→ClPr…S→SlC→f→ClPr…S→SlC→f→ClPr…S→SlC→第二種方法:令*p的直接前驅替代*p,然后再從二叉排序樹中刪去它的直接前驅.f→p→ClPr…q→qlS→SlC→f→p→ClPr…q→qlS→SlC→f→p→ClPr…q→qlSlC→返回50308020908540358832例如：4040以其前驅替代之，然后再刪除該前驅結點被刪結點前驅結點被刪關鍵字=5099StatusDeleteBST(BiTree&T,KeyTypekey){

//若二叉排序樹T中存在其關鍵字等于key的//數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結點，并返回//函數(shù)值TRUE，否則返回函數(shù)值FALSEif(!T)returnFALSE;

//不存在關鍵字等于key的數(shù)據(jù)元素else{}}//DeleteBST算法描述如下：……算法9.7if(EQ(key,T->data.key))

//找到關鍵字等于key的數(shù)據(jù)元素elseif(LT(key,T->data.key))

else{Delete(T);returnTRUE;} DeleteBST(T->lchild,key);

//繼續(xù)在左子樹中進行查找DeleteBST(T->rchild,key);

//繼續(xù)在右子樹中進行查找voidDelete(BiTree&p){

//從二叉排序樹中刪除結點p，//并重接它的左子樹或右子樹if(!p->rchild){}elseif(!p->lchild){}else{}}//Delete其中刪除操作過程如下所描述：………………算法9.8//右子樹為空樹則只需重接它的左子樹q=p;p=p->lchild;free(q);pp//左子樹為空樹只需重接它的右子樹q=p;p=p->rchild;free(q);ppq=p;s=p->lchild;while(!s->rchild){q=s;s=s->rchild;}

//s指向被刪結點的前驅//左右子樹均不空p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;//重接*q的左子樹free(s);pqs回顧示意圖9.3.2二叉排序樹5．二叉排序樹的查找分析對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關鍵字，構造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。由關鍵字序列3，1，2，5，4構造而得的二叉排序樹，由關鍵字序列1，2，3，4，5構造而得的二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+2+3+3）/5=2.2二叉排序樹的平均查找長度:最差的情況:

(n+1)/2最好的情況：平均的情況：P232

下面討論平均情況:不失一般性，假設長度為n的序列中有k個關鍵字小于第一個關鍵字，則必有n-k-1個關鍵字大于第一個關鍵字,由它構造的二叉排序樹：n-k-1k平均查找長度是n和k的函數(shù)ASL=P(n,k)(0kn-1)。假設n個關鍵字可能出現(xiàn)的n!種排列的可能性相同，則含n個關鍵字的二叉排序樹的平均查找長度：在等概率查找的情況下，由此可類似于解差分方程，此遞歸方程有解：9.3

動態(tài)查找表

9.3.2二叉排序樹9.3.3

平衡二叉樹9.3.4

B-樹和B+樹

9.3.1動態(tài)查找表的定義使用樹結構表示動態(tài)查找表；使用鏈式存儲結構實現(xiàn)查找、插入和刪除操作。-RLhh9.3.3二叉排序樹平衡二叉樹又稱AVL樹，是二叉排序樹的另一種形式。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。結點的平衡因子：該結點的左子樹高度減去它的右子樹高度。即：平衡二叉樹的特點為：樹中每個結點的左、右子樹深度之差的絕對值不大于1。即。例如:548254821是平衡二叉樹不是平衡二叉樹

構造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉技術。一般情況下，假設由于在二叉排序樹上插入結點而失去平衡的最小子樹根結點的指針為a（即a是離新插入結點最近，且平衡因子絕對值超過1的祖先結點），則失去平衡后進行調(diào)整的規(guī)律可歸納為下列四種情況：

LL型、LR型、RR型、LR型。LLBL2A1BARh-1BRh-1h插入結點0B0ABLBRAR?LL型：即新插入的結點在a的左子樹的左子樹上。此時應選擇a的左子樹的根結點b，然后進行調(diào)整；LR0C-1ABLCRAR0BCL?LR型：即新插入的結點在a的左子樹的右子樹上。此時應選擇a的左子樹的根結點b，和b的右子樹的根結點c，然后進行調(diào)整；BL2A-1BARh-1CRh-2插入結點1Ch-1CLh-1RRhBR-2A-1BALh-1BLh-1插入結點0B0AALBLBR?RR型：即新插入的結點在a的右子樹的右子樹上。此時應選擇a的右子樹的根結點b，然后進行調(diào)整；RL0C-1BALCRBR0ACL?RL型：即新插入的結點在a的右子樹的左子樹上。此時應選擇a的右子樹的根結點b，和b的左子樹的根結點c，然后進行調(diào)整；h-1BR-2A1BALCRh-2插入結點1Ch-1CLh-1例如:依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉一次先向右旋轉再向左旋轉LL型RL型aabbc例如:依次插入的關鍵字為5,4,2,8,6,9426589642895向左旋轉一次繼續(xù)插入關鍵字9RR型ab二叉排序樹的類型定義為：typedefstructBSTNode{ElemTypedata;intbf;//結點的平衡因子structBSTNode*lchild,*rchild;

//左、右孩子指針}BSTNode,*BSTree;

voidR_Rotate(BSTree&p){

//對以*p為根的二叉排序樹作右旋處理，處理之后p指向新的根結點，即旋轉處理之前的左子樹的根結點lc=p->lchild;

//lc指向的*p的左子樹根結點p->lchild=p->rchild;

//lc的右子樹掛接為*p的左子樹p->rchild=p;p=lc;

//p指向新的根結點}

//R_Rotate算法9.9

voidL_Rotate(BSTree&p){

//對以*p為根的二叉排序樹作左旋處理，處理之后p指向新的根結點，即旋轉處理之前的右子樹的根結點rc=p->rchild;

//rc指向的*p的右子樹根結點p->rchild=p->lchild;

//rc的左子樹掛接為*p的右子樹p->lchild=p;p=rc;

//p指向新的根結點}

//L_Rotate算法9.10#defineLH+1

//左高#defineEH0

//等高#defineRH-1

//右高StatusInsertAVL(BSTree&T,ElemTypee,

Boolean&taller){

//若在平衡的二叉排序樹T中不存在和e有相同關鍵字的結點，則插入一個數(shù)據(jù)元素為e的新結點，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉處理，布爾變量taller反映T長高與否

if(!T){

//插入新結點，樹“長高”，置taller為TRUET=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=TRUE;}算法9.11

else{

if(EQ(e.key,T->data.key))

//樹中已存在和e有相同關鍵字的結點

{taller=FALSE;return0;}

//則不再輸入

if(LT(e.key,T->data.key)){

//應繼續(xù)在*T的左子樹中進行搜索

if(!InsertAVL(T->lchild,e,taller))return0;

//未插入

if(taller)

//已插入到*T的左子樹中且左子樹“長高”

switch(T->bf){

//檢查*T的平衡度

caseLH;

//原本左子樹比右子樹高，需要做左平衡處理

LeftBalance(T);taller=FALSE;break;

caseEH;

//原本左、右子樹等高，現(xiàn)因左子樹增高而使樹增高

T->bf=LH;taller=TRUE;break;

caseRH;

//原本右子樹比左子樹高，現(xiàn)左、右子樹等高

T->bf=EH;taller=FALSE;break;

}

//switch(T->bf)算法9.11}//ifelse{

//應繼續(xù)在*T的右子樹中進行搜索

if(!InsertAVL(T->rchild,e,taller))return0;

//未插入

if(taller)

//已插入到*T的右子樹中且右子樹“長高”

switch(T->bf){

//檢查*T的平衡度

caseLH;

//原本左子樹比右子樹高，現(xiàn)左、右子樹等高

T->bf=EH;taller=FALSE;break;

caseEH;

//原本左、右子樹等高，現(xiàn)因右子樹增高而使樹增高T->bf=RH;taller=TRUE;break;

caseRH;

//原本右子樹比左子樹高，需要做右平衡處理

RightBalance(T);taller=FALSE;break;

}//switch(T->bf)}//else}//else

return1;}//InsertAVL算法9.11算法9.12voidLeftBalance(BSTree&T){

//對以指針T所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時，指針T指向新的根結點lc=T->lchild;//lc指向*T的左子樹根結點switch(lc->bf){

//檢查*T的左子樹的平衡度，并作相應平衡處理caseLH;

//新結點插入在*T的左孩子的左子樹，要作單右旋處理T->bf=lc->bf=EH;R_Rotate(T);break;caseRH;

//新結點插入在*T的左孩子的右子樹，要作雙旋處理rd=lc->rchild;

//rd指向*T的左孩子的右子樹根

switch(rd->bf){

//修改*T及其左孩子的平衡因子caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;

}

//switch(rd->bf)rd->bf=EH;L_Rotate(T->lchild);

//對*T的左子樹作左旋平衡處理R_Rotate(T);

//對*T的作右旋平衡處理

}

//switch(lc->bf)}

//LeftBalance在平衡樹上進行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進行比較的關鍵字的個數(shù)不超過平衡樹的深度。平衡樹的查找性能分析：

問：含n個關鍵字的二叉平衡樹可能達到的最大深度是多少？n=0空樹最大深度為0n=1最大深度為1n=2最大深度為2n=4最大深度為3n=7最大深度為4先看幾個具體情況:

反過來問，深度為h的二叉平衡樹中所含結點的最小值Nh是多少？h=0N0=0h=1h=2h=3一般情況下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用歸納法可證得Nh=Fh+2-1

因此，在二叉平衡樹上進行查找時，查找過程中和給定值進行比較的關鍵字的個數(shù)和

log(n)

相當。

由此推得，深度為h的二叉平衡樹中所含結點的最小值

Nh=h+2/5-1。

反之，含有

n

個結點的二叉平衡樹能達到的最大深度hn=log(5(n+1))-2。9.3

動態(tài)查找表

9.3.2二叉排序樹9.3.3

平衡二叉樹9.3.4

B-樹和B+樹

9.3.1動態(tài)查找表的定義使用樹結構表示動態(tài)查找表；使用鏈式存儲結構實現(xiàn)查找、插入和刪除操作。9.3.4

B-樹和B+樹1．B-樹的定義B-樹是一種平衡的多路查找樹：

一棵

m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：（1）所有非葉結點均至少含有m/2棵子樹，至多含有m

棵子樹；（2）根結點或為葉子結點，或至少含有兩棵子樹；（3）所有非終端結點含有下列信息數(shù)據(jù)：

（n，A0，K1，A1，K2，A2，…Kn，An）其中：

Ki為關鍵字，且均自小至大有序排列，即：

K1<K2<…<Kn；

Ai為指向子樹根結點的指針，且指針Ai-1所指子樹上所有關鍵字均小于Ki；An所指子樹上所有關鍵字均大于Kn；（4）樹中所有葉子結點均不帶信息，且在樹中的同一層次上；#definem3

//B-樹的階，暫設為3typedefstructBTNode{intkeynum;

//結點中關鍵字個數(shù)，即結點大小structBTNode*parent;

//指向雙親結點的指針KeyTypekey[m+1];

//關鍵字向量（0號單元不用）structBTNode*ptr[m+1];

//子樹指針向量

Record*recptr[m+1];

//記錄指針向量（0號單元不用）}BTNode,*BTree;

//B樹結點和B樹的類型B-樹結構的C語言描述如下:9.3.4

B-樹和B+樹2．B-樹的查找過程從根結點出發(fā)，沿指針搜索結點和在結點內(nèi)進行順序（或折半）查找兩個過程交叉進行。若查找成功，則返回指向被查關鍵字所在結點的指針和關鍵字在結點中的位置；若查找不成功，則返回插入位置。typedefstruct{BTNode*pt;//指向找到的結點的指針inti;//1..m，在結點中的關鍵字序號inttag;//標志查找成功(=1)或失敗(=0)}Result;//在B樹的查找結果類型假設返回的是如下所述結構的記錄：ResultSearchBTree(BTreeT,KeyTypeK)//在m階的B-樹T中查找關鍵字K,返回//查找結果(pt,i,tag)。若查找成功，則//特征值tag=1,指針pt所指結點中第i個//關鍵字等于K；否則特征值tag=0,等于//K的關鍵字應插入在指針pt所指結點//中第i個關鍵字和第i+1個關鍵字之間{}//SearchBTree……算法9.13p=T;q=NULL;found=FALSE;i=0;//初始化，p指向待查接點，q指向p的雙親

while(p&&!found){i=Search(p,K);

//在p->key[1..keynum]中查找，//i使得p->key[i]<=K<p->key[i+1]if(i>0&&p->key[i]==K)found=TRUE;//找到待查//關鍵字else{q=p;p=p->ptr[i];}}if(found)return(p,i,1);//查找成功elsereturn(q,i,0);

//查找不成功，返回k的插

//入位置信息9.3.4

B-樹和B+樹3．B-樹的插入過程

在查找不成功之后，需進行插入。顯然，關鍵字插入的位置必定在最下層的非葉結點，有下列幾種情況：1）插入后，該結點的關鍵字個數(shù)n<m，不修改指針;2）插入后，該結點的關鍵字個數(shù)

n=m，則需進行“結點分裂”，令s=m/2，在原結點中保留（A0，K1，……，Ks-1，As-1）；建新結點（As，Ks+1，……，Kn，An）；將（Ks，p）插入雙親結點；3）若雙親為空，則建新的根結點。

詳細過程，見教材p242—p245圖9.16例如:下列為3階B-樹50204080插入關鍵字=60,

608090,60809090

50806030,40203050808030

50算法9.14StatusInsertBTree(BTree&T,KeyTypeK,

BTreeq,inti){

//在m階B-樹T上結點*q的key[i]和key[i+1]之間插入關鍵字K。若引起結點過大，則沿雙親鏈進行必要的結點分裂調(diào)整，使T仍是m階B-樹。

x=K;ap=NULL;finished=FALSE;while(q&&!finished){Insert(q,i,x,ap);

//將x和ap分別插入到q->key[i+1]和q->ptr[i+1]if(q->keynum<m)finished=TRUE;

//插入完成

else{s=[m/2];split(q,s,ap);x=q->key[s];

//將q->key[s+1..m],q->ptr[s..m]和q>recptr[s+1..m]//移入新結點*ap

q=q->parent;if(q)i=Search(q,x);

//在雙親結點*q中查找x的插入位置

}//else

}//whileif(!finished)//T是空樹(參數(shù)q初值為NULL)或者根//結點已分裂為結點*q和*apNewRoot(T,q,x,ap);

//生成含信息(T,x,ap)

//的新的根結點*T，原T和ap為子樹指針returnOK;

}//InsertBTree9.3.4

B-樹和B+樹4．B-樹的刪除過程

和插入的考慮相反，首先必須找到待刪關鍵字所在結點，并且要求刪除之后，結點中關鍵字的個數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結點“借調(diào)”關鍵字，若其左和右兄弟結點均無關鍵字可借(結點中只有最少量的關鍵字)，則必須進行結點的“合并”。假若所刪關鍵字為非終端結點中的Ki,則可以指針Ai所指子樹中的最小關鍵字Y替代Ki，然后在相應的結點中刪去Y。詳細過程，見教材p245圖9.179.3.4

B-樹和B+樹5．B-樹的查找性能的分析

在B-樹中進行查找時，其查找時間主要花費在搜索結點（訪問外存）上，即主要取決于B-樹的深度。問：含N個關鍵字的m階B-樹可能達到的最大深度H為多少？反過來問：

深度為H的B-樹中，至少含有多少個結點？第2層

2個先推導每一層所含最少結點數(shù)：第1層

1個第H+1層

2(m/2)H-1個第4層

2(m/2)2個第3層

2m/2個

……

假設m階B-樹的深度為H+1，由于第H+1層為葉子結點，而當前樹中含有N個關鍵字，則葉子結點必為N+1個，N+1≥2(m/2)H-1H-1≤logm/2((N+1)/2)H≤logm/2((N+1)/2)+1由此可推得下列結果：結論：在含

N

個關鍵字的

B-樹上進行一次查找，需訪問的結點個數(shù)不超過

logm/2((N+1)/2)+19.3.4

B-樹和B+樹6．B+樹是B-樹的一種變型。（1）B+樹的結構特點：每個葉子結點中含有n個關鍵字和n

個指向記錄的指針；并且，所有葉子結點彼此相鏈接構成一個有序鏈表，其頭指針指向含最小關鍵字的結點；每個非葉結點中的關鍵字Ki即為其相應指針Ai所指子樹中關鍵字的最大值；所有葉子結點都處在同一層次上，每個葉子結點中關鍵字的個數(shù)均介于m/2和m之間。（2）查找過程在B+樹上，既可以進行縮小范圍的查找（自頂向下），也可以進行順序查找（在最底層，自左向右）；在進行縮小范圍的查找時，不管成功與否，都必須查到葉子結點才能結束；若在結點內(nèi)查找時，給定值≤Ki，則應繼續(xù)在

Ai所指子樹中進行查找。（3）插入和刪除的操作類似于B-樹進行，即必要時，也需要進行結點的“分裂”或“歸并”。9.2

靜態(tài)查找表9.3

動態(tài)查找表9.4

哈希表9.1

基本概念和術語9.4

哈希表9.4.1什么是哈希表9.4.2哈希函數(shù)的構造方法

9.4.3處理沖突的方法

9.4.4

哈希表的查找及其分析9.4.1

什么是哈希表前面兩節(jié)討論的表示查找表的各種結構的共同特點：記錄在表中的位置和它的關鍵字之間不存在一個確定的關系；查找的過程為給定值依次和關鍵字集合中各個關鍵字進行比較；查找的效率取決于和給定值進行比較的關鍵字個數(shù)。用這類方法表示的查找表，其平均查找長度都不為零。不同的表示方法，其差別僅在于：關鍵字和給定值進行比較的順序不同。

只有一個辦法：預先知道所查關鍵字在表中的位置。即，要求：記錄在表中的位置和其關鍵字之間存在一種確定的關系。對于頻繁使用的查找表，希望ASL=0。若以下標為000~999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關鍵字為學號，其值的范圍為xx000~xx999(前兩位為年份)。則查找過程可以簡單進行：取給定值（學號）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關鍵字。但是，對于動態(tài)查找表而言，有以下問題：因此在一般情況下，需在關鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關系，以f(key)作為關鍵字為key的記錄在表中的位置，通常稱這個函數(shù)f(key)為哈希函數(shù)。1)表長不確定；2)在設計查找表時，只知道關鍵字所屬范圍，而不知道確切的關鍵字。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例如：對于如下9個關鍵字設哈希函數(shù)f(key)=

(Ord(第一個字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDei問題:

若添加關鍵字Zhou,怎么辦？能否找到另一個哈希函數(shù)？

0123456789101112131)哈希函數(shù)是一個映象，即：將關鍵字的集合映射到某個地址集合上，它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可；從這個例子可見：2)由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而f(key1)=f(key2)。具有相同函數(shù)值的關鍵字對該哈希函數(shù)來說稱作同義詞。3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。因此，在構造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。哈希表的定義：根據(jù)設定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關鍵字在地址集中的“象”作為相應記錄在表中的存儲位置，如此構造所得的查找表稱之為“哈希表”。9.4

哈希表9.4.1什么是哈希表9.4.2哈希函數(shù)的構造方法

9.4.3處理沖突的方法

9.4.4

哈希表的查找及其分析9.4.2

哈希函數(shù)的構造方法對數(shù)字的關鍵字可有下列構造方法：若是非數(shù)字關鍵字，則需先對其進行數(shù)字化處理。1.

直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法哈希函數(shù)為關鍵字的線性函數(shù)H(key)=key或者H(key)=akey+b1.

直接定址法此法僅適合于：地址集合的大小==關鍵字集合的大小

假設關鍵字集合中的每個關鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。2.

數(shù)字分析法此法僅適合于：

能預先估計出全體關鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。

以關鍵字的平方值的中間幾位作為存儲地址。求“關鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關鍵字中各位的影響。3.

平方取中法此法僅適合于：

關鍵字中的每一位都有某些數(shù)字重復出現(xiàn)頻度很高的現(xiàn)象。

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

折疊法此法僅適合于：

關鍵字的數(shù)字位數(shù)特別多。

將設定哈希函數(shù)為:H(key)=keyMODp其中，p≤m(表長)并且p

應為不大于

m的素數(shù)

或是

不含

20以下的質(zhì)因子5.

除留余數(shù)法給定一組關鍵字為：12,39,18,24,33,21，若取p=9,則他們對應的哈希函數(shù)值將為：3,3,0,6,6,3例如：為什么要對

p加限制？可見，若p中含質(zhì)因子3，則所有含質(zhì)因子3的關鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。6.

隨機數(shù)法設定哈希函數(shù)為:H(key)=Random(key)其中，Random為偽隨機函數(shù)

通常，此方法用于對長度不等的關鍵字構造哈希函數(shù)。

實際造表時，采用何種構造哈希函數(shù)的方法取決于建表的關鍵字集合的情況(包括關鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。9.4

哈希表9.4.1什么是哈希表9.4.2哈希函數(shù)的構造方法

9.4.3處理沖突的方法

9.4.4

哈希表的查找及其分析9.4.3

處理沖突的方法

處理沖突”的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。通常有下列幾種方法：1.開放定址法3.鏈地址法2.再哈希法4.建立一個公共溢出區(qū)1.

開放定址法

為產(chǎn)生沖突的地址H(key)求得一個地址序列：H0,H1,H2,…,Hs1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di

)MODmi=1,2,…,s，m為哈希表表長對增量di

有三種取法：1)線性探測再散列

di=1，2，3，…，m-12)二次探測再散列

di=12,-12,22,-22,…,3)偽隨機探測再散列

di

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

di=i×H2(key)(又稱雙散列函數(shù)探測)即：產(chǎn)生的Hi

均不相同，且所產(chǎn)生的s(m-1)個Hi值能覆蓋哈希表中所有地址。則要求：

注意：增量

di

應具有“完備性”2.隨機探測時的

m

和

di沒有公因子。1.平方探測時的表長

m必為形如

4j+3

的素數(shù)（如:7,11,19,23,…等）；

在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現(xiàn)象稱作‘二次聚集’。例如:關鍵字集合{19,01,23,14,55,68,11,82,36}設定哈希函數(shù)H(key)=keyMOD11(表長=11)1901231455681901231468若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突11823655118236112136251H2(key)是另設定的一個哈希函數(shù)，它的函數(shù)值應和m互為素數(shù)。若m為素數(shù)，則H2(key)可以是1至m-1之間的任意數(shù)；若m為2的冪次，則H2(key)應是1至m-1之間的任意奇數(shù)。例如，當m=11時，

可設H2(key)=(3key)MOD10+1190123145568118236211