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

第九章查找9.1基本概念9.2靜態(tài)查找表9.3動態(tài)查找表9.4哈希表

基本概念查找表：是由同一類型的數(shù)據(jù)元素(或記錄)構成的集合。靜態(tài)查找表：對查找表只作查詢或檢索操作動態(tài)查找表：在對查找表進行查找過程中加入插入和刪除操作查找：在一個含有眾多的數(shù)據(jù)元素(或記錄)的查找表中找出某個“特定的”數(shù)據(jù)元素(或記錄).關鍵字：是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值,用它可以標識一個數(shù)據(jù)元素(或記錄).主關鍵字：某關鍵字可以唯一標識一個記錄。次關鍵字：用以識別若干記錄的關鍵字影響查找效率的因素1.數(shù)據(jù)結構(查找表的存儲結構)2.查找算法3.記錄的存放形式(有序,無序)典型的關鍵字類型說明和數(shù)據(jù)元素類型說明：

TypedeffloatKeyType;//實型

Typedef

int

KeyType;//整型

Typedefchar*KeyType;//字符串型數(shù)據(jù)元素類型定義為：

typedef

struct{

KeyTypekey;//關鍵字域

……//其它域}ElemType;對兩個關鍵字的比較約定為如下的宏定義//對數(shù)據(jù)類型關鍵字#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)

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

struct{

ElemType*elem;//數(shù)據(jù)元素存儲空間基址，建表時按實際長度分

//配，0號單元留空

intlength;//表長度}SSTable;順序表的查找順序查找的查找過程從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個記錄，其關鍵字和給定值比較都不相等，則表明表中沒有所查記錄，查找不成功。順序查找的缺點：平均查找長度較大優(yōu)點：算法簡單且適應面廣

順序查找順序查找算法實現(xiàn)int

Search_Seq(SSTable

ST,KeyTypekey){//在順序表ST中順序查找其關鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0

ST.elem[0].key=key;//”哨兵“for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//從后往前找returni;//找不到時，i為0}//Search_Seq順序查找操作的性能分析平均查找長度(AverageSearchLength)

為確定記錄在查找表中的位置,需要和給定值進行比較的關鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度.

對于n個記錄的表,查找成功時的平均查找長度為ASL=∑i=1n

pici

pi:為查找表中第i個記錄的概率

ci:為查找到表中其關鍵字與給定值相等的第i個記錄時,和給定值已經(jīng)進行過比較的關鍵字個數(shù).順序查找平均查找長度在順序查找過程中,ci取決于所查記錄在表中的位置.一般情況下ci=n-i+1假設每個記錄的查找概率相等即pi=1/n則在等概率下順序查找平均查找長度為:ASLss=∑i=1n

pici

=1/n∑i=1n(n-i+1)ASLss

=(n+1)/2以有序表作為靜態(tài)查找表時。

折半查找的查找過程：先確定待查記錄所在的范圍(區(qū)間),然后逐步縮小范圍直到找到或找不到該記錄為止，一般折半查找都是以處于區(qū)間中間位置記錄的關鍵字和給定值比較，若相等，則查找成功若不等，則縮小范圍，直至新的區(qū)間中間位置記錄的關鍵字等于給定值或者查找區(qū)間的大小小于0時（表明查找不成功）為止。

有序表的查找折半查找算法

int

Search_Bin(SSTable

ST,KeyTypekey){//在有序表ST中折半查找其關鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0low=1;high=ST.length;//置區(qū)間初值while(low<=high){mid=(low+high)/2;if(EQ(key.ST.elem[mid].key)returnmid;//找到待查元素elseifLT(key.ST.elem[mid].key)high=mid-1;//繼續(xù)在前半?yún)^(qū)間查找

elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間查找}

return0;//順序表中不存在待查元素}Search_Bin例：已知如下11個數(shù)據(jù)元素的有序表(關鍵字既為數(shù)據(jù)元素的值)：(05,13,19,21,37,56,64,75,80,88,92）現(xiàn)要查找關鍵字為21的數(shù)據(jù)元素,mid=(high+low)/2上界取整0513192137566475808892lowmidhighhighmidLowmid7581110924136圖9.2折半查找操作過程的判定樹折半查找操作的性能分析折半查找操作的過程可以用二叉樹表示折半查找操作的性能分析假設有序表的長度n=2h-1,即h=log2(n+1),則描述折半查找的判定樹是深度為h的滿二叉樹,樹中層次為1的結點有一個,層次為2的結點有兩個,…,層次為h的結點有2h-1.再假設pi=

1/n.ASLbs=∑i=1n

pici=1/n∑j=1h

j.2j-1=(n+1)/n.log2(n+1)-1ASLbs=log2(n+1)-1以索引順序表表示靜態(tài)查找表。分塊查找又稱索引順序查找，是順序查找的一種改進方法。此查找表中，除表本身外，尚需建立一個“索引表”分塊查找過程：先確定待查記錄所在的塊(子表)，然后在塊中順序查找例：下圖為一個表及其索引表索引順序表的查找224886159索引表最大關鍵字起始地址22128203324483860748653子表(R1,R2,..,R4)(R5,R6,…,R8)(R9,R10….,R12)分塊查找過程：先確定待查記錄所在的塊(子表)，然后在塊中順序查找

9.2動態(tài)查找表二叉排序樹和平衡二叉樹B-樹和B+樹動態(tài)查找表特點：表結構本身是在查找過程中動態(tài)生成，既對于給定值key，若表中存在其關鍵字等于key的記錄，則查找成功返回，否則插入關鍵字等于key的記錄。ADTDynamicSearchTable{

數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類型相同，可唯一標識數(shù)據(jù)元素的關鍵字

數(shù)據(jù)關系R：數(shù)據(jù)元素同屬一個集合基本操作P：

InitDSTable(&DT);

操作結果：構造一個空的動態(tài)查找表DT

DestroyDSTable(&DT);

初始條件：動態(tài)查找表DT存在操作結果：銷毀動態(tài)查找表DT

SearchDSTable(DT,key);

初始條件：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值操作結果：若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”

InsertDSTable(&DT,e);初始條件：動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素操作結果：若DT中不存在其關鍵字等于e.key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為0DeleteDSTable(&DT,key);

初始條件：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值操作結果：若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則刪除之TraverseDSTable(DT,Visit());初始條件：動態(tài)查找表DT存在，Visit是對結點操作的應用函數(shù)操作結果：按某種次序對DT的每個接點調(diào)用函數(shù)Visit()

一次且至多一次。一旦Visit()失敗，則操作失敗}ADTDynamicSearchTable二叉排序樹：或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：⑴若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；⑵若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值⑶它的左，右子樹也分別為二叉排序樹二叉排序樹及其平衡二叉樹45531006190782437312二叉排序樹圖二叉排序樹查找過程二叉排序樹查找過程：當二叉排序樹不空時，首先將給定值和根結點的關鍵字比較，若相等，則查找成功，否則將依據(jù)給定值和根接點的關鍵字之間的大小關系，分別在左子樹或右子樹上繼續(xù)查找例：查找關鍵字61的記錄如圖4553100619078243731261>4561>5361<10061=61查找成功查找右子樹繼續(xù)查找右子樹查找左子樹BiTree

SearchBST(BiTree

T,KeyTypekey){//在根指針T所指二叉排序樹種遞歸地查找某關鍵字等于key的數(shù)據(jù)元素，若查找成功，則返回指向該數(shù)組元素結點地指針，否則返回空指針

if(!T)||EQ(key,T->data.key))return(T);//查找結束elseifLT(key,T->data.key)return(SearchBST(T->lchild.key));//在左子樹中繼續(xù)查找elsereturn(SearchBST(T->rchild,key));//在右子樹中查找}//SearchBST二叉排序樹查找算法插入過程：二叉排序樹的結構通常不時一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的結點時再進行插入。新插入的結點一定是一個新添加的葉子結點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點二叉排序樹的插入例：查找的關鍵字序列為{45,24,53,45,12,24,90}則生成的二叉排序樹如圖：Φ空樹45插入4524插入2453插入5312插入1290插入90StatusSearchBST(BiTree

T,KeyType

key,BiTree

f,BiTree&p)}//在根指針T所指二叉排序樹中遞歸地查找其關鍵字等于key的數(shù)據(jù)元素，若查找成功，則指針p指向該數(shù)據(jù)元素結點，并返回TRUE，否則指針p指向查找路徑上訪問的最后一個結點并返回FALSE，指針f指向T的雙親，其初始調(diào)用值為NULLif(!T){p=f;returnFALSE;}//查找不成功elseifEQ(key,T->data.key){p=T;returnTRUE;}//查找成功elseifLT(key,T->data.key)

searchBST(T->lchild,key,T,p);//在左子樹中查找elseSearchBST(T->rchild,key,T,p);//在右子樹中查}//SearchBST二叉排序樹的插入算法StatusInsertBST(BiTree&T,ElemTypee){//當二叉排序樹T中不存在關鍵字等于e.key的數(shù)據(jù)元素時，插入e并返回TRUE，否則返回FALSEif(!SearchBST(T,e.key,NULL,p){//查找不成功

s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//被插結點*s為新的根結點elseifLT(e.key,p->data.key)p->lchild=s;//被插結點*s為左孩子

elsep->rchild=s;//被插結點*s為右孩子

returnTRUE;}elsereturnFALSE;//樹中已有關鍵字相同的結點，不再插入}//InsertBST二叉排序樹的刪除設在二叉排序樹上被刪結點為*p(指向結點的指針p),其雙親結點為*f（結點指針為f)，且不失一般性，可設*p是*f的左孩子刪除分三種情況：⑴若*p結點為葉子結點，既PL和PR均為空樹。由于刪去葉子結點不破壞整棵樹的結構，則只需修改其雙親結點的指針即可⑵若*p結點只有左子樹PL或者只有右子樹PR，此時只有令PL或

PR直接成為其雙親結點*f的左子樹即可。⑶若*p結點的左子樹和右子樹均不空時，分兩種情況：方法一:是令*p的左子樹為*f的左子樹，而*p的右子樹為*s(p左孩子的最右孩子)的右子樹。方法二:是令*p的直接前驅s(p左孩子的最右孩子)替代*p,同時將s的左子樹作為其雙親的右子樹.或者是令*p的直接后繼s(p右孩子的最左孩子)替代*p,同時將s的右子樹作為其雙親的左子樹.FPfp以*f為根的子樹P1子樹P1PR子樹PR在二叉排序樹上刪除一個結點的算法StatusDeleteBST(BiTree&T,KeyTypekey){//若二叉排序樹T中存在關鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元素結點，并返回TRUE；否則返回FALSEIf(!T)returnFALSE;//不存在關鍵字等于key的數(shù)據(jù)元素Else{ifEQ(key,T->data.key)Delete(T);//找到關鍵字等于key的數(shù)據(jù)元素elseifLT(key,T->data.key)

DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);returnTRUE;}}//DeleteBST如前述三種情況綜合所得刪除操作算法：VoidDelete(BiTree&P){//從二叉排序樹中刪除結點p,并重接它得左或右子樹

if(!p->rchild){//右子樹空則只需重接它的左子樹

q=p;p=p->lchild;free(q);}elseif(!p->lchild){//只需重接它的右子樹

q=p;p=p->rchild;free(q);}從二叉排序樹中刪除結點pelse{//左右子樹均不空

q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild}//轉左，然后向右到盡頭

p->data=s->data;//s指向被刪結點的“前驅”

if(q!=p)q->rchild=s->lchild;//重接*q的右子樹elseq->lchild=s->lchild;//重接*q的左子樹Deletes;}}//Delete二叉排序樹的查找分析在二叉排序樹上查找其關鍵字等于給定值的結點的過程,恰是走了一條從根結點到該結點的路徑的過程,和給定值比較的關鍵字個數(shù)不超過樹的深度.因此,含有n個結點的二叉排序樹的平均查找長度和樹的形狀有關.最差情況:單枝樹ASL=(n+1)/2最好情況:平衡二叉樹ASL=log2(n+1)-1平衡二叉樹:或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1.平衡因子（BF)：該結點的左子樹的深度減去它的右子樹的深度.平衡二叉樹上所有結點的平衡因子只可能是-1,0,和1.在構造二叉排序樹的過程中,需要進行”平衡化”處理,成為二叉平衡樹平衡二叉樹

-1-101001平衡二叉樹其中-1,0,1為平衡因子設:a為二叉排序樹上插入結點而失去平衡的最小子樹的根結點的指針⑴單向右旋平衡處理(LL型平衡旋轉)⑵單向左旋平衡處理(RR型平衡旋轉)

⑶雙向旋轉(先左后右)平衡處理(LR型平衡旋轉)⑷雙向旋轉(先右后左)平衡處理(RL型平衡旋轉)插入結點失去平衡后進行調(diào)整規(guī)律構成的二叉排序樹為平衡樹方法：例：設關鍵字序列為(13,24,37,90,53),構成平衡樹過程如下Φ132413133724(a)空樹(b)插入130(c)插入24-10(d)插入37-2-10371324000(e)向左逆時針右旋轉平衡1353903724-20-210(f)相繼插入90和531390533724(g)第一次向右順時針旋轉3713905324-10000(h)第二次向左逆時針旋轉平衡之B-樹的結構:一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：⑴樹中每個結點至多有m棵子樹⑵若根結點不是葉子結點，則至少有兩棵子樹⑶除根之外的所有非終端結點至少有m/2棵子樹⑷所有的非終端結點中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,…,Kn,An)其中:Ki為關鍵字，且

Ki<Ki+1,Ai為指向子樹根結點的指針，n為關鍵字的個⑸所有的葉子結點都出現(xiàn)在同一層次上，并且不帶信息B-樹和B+樹

一棵4階的B-樹圖135199139127111118243783475364FFFFFFFFFFFFB-樹查找過程是一個順指針查找結點和在結點的關鍵字中進行查找交叉進行的過程B-樹結點類型說明：#definem3//B樹的階Typedef

struct

BTNode{

int

keynum;//結點大小

struct

BTNode*parent;//指向雙親結點

KeyTypeKey[m+1];//關鍵字向量，0號單元未用

struct

BTNode*ptr[m+1];//子樹指針向量

Record*recptr[m+1];//記錄指針向量}BTNode,*Btree;//B樹結點和B樹類型Typedef

struct{

BTNode*pt;//指向找到的結點

inti;//1…m，在結點中的關鍵字序號

inttag;//1查找成功，0查找失敗}Result;//B樹的查找結果類型B-樹查找算法實現(xiàn)ResultSearchBTree(Btree

T,KeyTypeK){//在n階B樹T上查找關鍵字K，返回結果(pt,i,tag).若查找成功，則tag=1.指針pt所指向結點第i個關鍵字等于K，否則tag=0，等于K的關鍵字應插入在指針pt所指向結點中第i個和i+1個關鍵字之間P=T;q=NULL;found=FALSE;i=0;While(p&&!found){n=p->keynum;i=Search(p,K);//在p->key[1..keynum]中查找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的插入位置信息}//SearchBTreeB-樹的查找分析在B-樹上進行查找包含兩種操作:1.在B-樹中找結點(在磁盤上進行)2.在結點中找關鍵字(在內(nèi)存中進行)顯然.在磁盤上進行一次查找比在內(nèi)存中進行一次查找耗費時間多的多.在磁盤上進行查找次數(shù),即待查關鍵字所在結點在B-樹上的層次數(shù),是決定B-樹查找效率的主要因素.考慮最壞情況,即待查結點在B-樹中的最大層次數(shù),也就是,求含N個關鍵字的m階B-樹的最大深度是多少?

先討論深度為L+1層的m階B-樹所具有的最少結點數(shù)

根據(jù)B-樹的定義:

第一層至少有1個結點;第二層至少有2個結點;第三層至少有2(m/2上取整)個結點;........第L+1層至少有2(m/2上取整)L-1結點因為含N個關鍵字的m階B-樹中葉結點為N+1個,因此有N+1>=2(m/2上取整)L-1

反之L<=log[m/2]((N+1)/2)+1也就是說,含N個關鍵字的m階B-樹上進行查找時,所涉及的結點數(shù)不超過log[m/2]((N+1)/2)+1B-樹的插入B-樹的生成是從空樹起，逐個插入關鍵字而得。由于B-樹結點的關鍵字個數(shù)必須>=m/2-1，所以，每次插入一個關鍵字不是在樹中填加一個葉子結點，而是首先在最低層的某個非終端結點中填加一個關鍵字，若該結點的關鍵字個數(shù)不超過m-1，則插入完成，否則要產(chǎn)生結點的“分裂”.如圖：B-樹的插入

在3階B-樹中進行插入示例4524539037100617050312btabcdefgh一棵B-樹4524539030

37100617050312btabcdefgh插入30之后45245390263037100617050312btabcdefgh4524

30539037100617050312btabcdefgh26d插入26之后4524305390

371006170

8550312btabcd’efgh26d4524305370903710050312btabcd’efgh266185g’d45

702430btab53901003726312615085插如85之后e’cdd’efgg’hStatusInsertBTree(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]和q->ptr[i]之間if(q->keynum<m)finished=TRUE;//插入完成

在B-樹上插入關鍵字算法：else{//否則分裂結點qs=m/2+1;

splist(q,ap);x=q->key[s];//將q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新結點*apq=q->parent;if(q)i=Search(q,x);//在雙親結點*q中查找x的插入位置}//else}//whileif(!finished)//如果T是空樹或者根結點分裂為結點*q和*ap

newRoot(T,q,x,ap);//生成含(T,x,ap)的新的根結點*T,原T和ap為子樹的指針}//InsertBTreeB-樹的刪除刪除一個關鍵字：首先找到該關鍵字所在的結點，并從中刪除之，若該結點為最下層的非終端結點，且其中的關鍵字數(shù)目不少于m/2，則刪除完成，否則要進行“合并”結點的操作。假若所刪關鍵字為非終端結點中的Ki，則可以指針所指子樹中的最小關鍵字Y替代Ki，

然后在相應的結點中刪去Y.所以,我們只要討論刪除最下層的非終端結點中的關鍵字的情形.B-樹的刪除

(1)被刪關鍵字所在結點中的關鍵字數(shù)目大于m/2上界取整-1,則只需從該結點中刪除關鍵字Ki和相應的指針Ai該結點,樹的其它部分不變.例：刪去下圖中關鍵字124524539037100617050312btabcdefgh例：刪去下圖中關鍵字12后的圖312bt45245390371006170503(2)被刪關鍵字所在結點中的關鍵字數(shù)目等于m/2上界取整-1，而與該結點相鄰的右兄弟(或左兄弟)結點中的關鍵字數(shù)目大于m/2上界取整-1，則需將其兄弟結點中的最小(或最大)的關鍵字上移至雙親結點中，而將雙親結點中小于(或大于)且緊靠該上移關鍵字的關鍵字下移至被刪關鍵字所在的結點中例：刪去下圖中關鍵字50312bt45245390371006170503例：下圖中刪去50后5390617050ef452437100361907053

bt刪去50,61上移至*e結點中，53移至*f⑶被刪關鍵字所在結點和其相鄰的兄弟結點中的關鍵字數(shù)目均等于m/2上界取整-1，假設該結點有右兄弟，且其右兄弟結點地址由雙親結點中的指針Ai所指，則在刪去關鍵字之后，它所有結點中剩余的關鍵字和指針，加上雙親結點中的關鍵字Ki一起，合并到Ai所指兄弟結點中(若沒有右兄弟，則合并至左兄弟結點中)：例：在下圖中刪去535390617050ef452437100361907053

bt4524371003906170

bt從該B-樹中刪去53，刪去53結點，并將53結點的的剩余信息(指針“空”)和雙親結點*e結點中的61一起合并到右兄弟結點*g中。刪除后變化如上圖。ehgabcd4524371003906170

bt再從該B-樹中刪去37。ehgabcd如果因此使雙親結點中的關鍵字數(shù)目小于m/2上界取整-1，則依次類推。如在上圖刪去53結點后的圖基礎上，刪去關鍵字37之后，雙親b結點中剩余信息(指針c)應和其雙親*a結點中關鍵字45一起合并至右兄弟結點*e中，刪除后如下圖：45901006170324bteghB+樹是B-樹的一個變型.一個m階B-樹和B+樹的區(qū)別:1.有n棵子樹的結點中含有n個關鍵字.2.所有葉結點中包含了全部關鍵字信息,及指向這些關鍵字的記錄.3.所有非終端結點可以看成是索引部分,結點中僅含有子樹中最大(或者最小)關鍵字見p246圖9.18

9.3哈希表什么是哈希表哈希函數(shù)的構造方法處理沖突的方法哈希表的查找及其分析哈希函數(shù)：在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f,使每個關鍵字和結構中一個唯一的存儲位置相對應，稱這個對應關系f為hash函數(shù)哈希表：通過hash函數(shù)計算，將集合中元素存儲在一個數(shù)組中，這個數(shù)組為hash表哈希沖突：對不同的關鍵字可能得到同一哈希地址，即key1≠key2,而f(key1)=f(key2),這種現(xiàn)象叫沖突

⑴直接定址法取關鍵字或關鍵字的某個線性函數(shù)值為哈希地址。即：H(key)=key或H(key)=a.key+b其中a和b為常數(shù)(這種哈希函數(shù)叫做自身函數(shù))⑵數(shù)字分析法將關鍵字中的某幾位進行運算后作為hash地址⑶折疊法將關鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進位)作為哈希地址哈希函數(shù)的構造方法⑸除留余數(shù)法取關鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址，既H(key)=keyMODpp<=m⑹隨機數(shù)法選擇一個隨機函數(shù)，取關鍵字的隨機函數(shù)值為它的哈希地址，即H(key)=random(key),其中random為隨機函數(shù)，通常，當關鍵字長度不等時采用此法構造哈希函數(shù)較恰當。處理沖突的方法⑴開放定址法公式：Hi=(H(key)+di)MODmi=1,2,…,k(k<=m-1)其中：H(key)為哈希函數(shù)；m為哈希表表長；di為增量序列，可有下列三種取法：①di=1,2,3,…,m-1,稱線性探測再散列；②di=12,-12,22,-22,32,…,+k2,(k<=m/2)稱二次探測再散列③di=偽隨機數(shù)序列，稱偽隨機探測再散列例：在長度為11的哈希表中已填有關鍵字分別為17,60,29的記錄(hash函數(shù)H(key)=keyMOD11)，現(xiàn)有第四個記錄，其關鍵字為38，由哈希函數(shù)H(38)=38MOD11得到哈希地址為5，產(chǎn)生沖突.下面分別用三種取法解決沖突601729012345678910設38插入前表如下所示60172938012345678910一：用線性探測法解決沖突MOD11=5沖突(5+1)MOD11=6沖突(5+2)MOD11=7沖突(5+3)MOD11=8插入38601729012345678910二：用二次探測法解決沖突MOD11=5沖突(5+12)MOD11=6沖突(5+(-12))MOD11=4插入38601729012345678910三：偽隨機探測法解決沖突取偽隨機數(shù)列為9,則38MOD11=5沖突(5+9)MOD11=3插入⑵再哈希法Hi=RHi(key)i=1,2,…,kRhi均是不同的哈希函數(shù)，既在同義詞產(chǎn)生地址沖突時計算機另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。⑶鏈地址法思想：將具有相同hash函數(shù)值(hash地址)的元素放在同一個鏈表中例：已知一組關鍵字為(19,14,23,01,68,11,10,55),則按哈希函數(shù)H(key)=keyMOD13和鏈地址