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

第9章查找主要內容：靜態(tài)查找表----順序、折半、分塊動態(tài)查找表----各種樹表哈希表討論各種查找方法的效率相關術語及概念查找表（SearchTable）:由同一類型的數(shù)據(jù)元素構成的集合。關鍵字（key）：用來標識一個數(shù)據(jù)元素的數(shù)據(jù)項。查找（Searching）：根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的記錄或數(shù)據(jù)元素，若表中存在這樣的一個記錄，則查找成功，否則查找不成功。靜態(tài)查找表（StaticSearchTable）:查找過程中查找表本身不發(fā)生變化的查找表。（無插入、刪除操作）動態(tài)查找表（DynamicSearchTable）:查找過程中查找表本身發(fā)生變化(插入或刪除元素)的查找表。查找方法評價

查找速度占用存儲空間多少算法本身復雜程度平均查找長度ASL(AverageSearchLength):為確定記錄在表中的位置，需和給定值進行比較的關鍵字的個數(shù)的期望值對含有n個記錄的查找表，查找成功時的平均查找長度為：

nASL=∑

pici

i=1n其中：pi為查找表中第i個記錄的概率，且∑pi=1

i=1

ci為找到表中第i個元素所需比較次數(shù)9.1靜態(tài)查找表ADTStaticSearchTable{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均具有相同類型，各元素具有可唯一標識數(shù)據(jù)元素的關鍵字。數(shù)據(jù)關系R：數(shù)據(jù)元素同屬一個集合?；静僮鱌：

Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());}ADTStaticSearchTabletypedef

struct{KeyTypekey; ….}ElemType;

typedef

struct{ElemType *elem;int length;}SSTable;一、順序表的查找int

Search_Seq(SSTableST,keyTypekey){ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}查找過程：從表的一端開始逐個進行記錄的關鍵字和給定值的比較。i例01234567891011

251392117966415288822找6464監(jiān)視哨iiii查找成功返回7

查找3535iiiiiiiiiiii查找不成功返回0性能分析：

n平均查找長度ASL=∑

pici

i=1順序查找時比較次數(shù)取決于所查找記錄在表中的位置。一般情況：Ci=n–i+1在等概率情況下：nASL=∑

(n–i+1）/n=(n+1)/2

i=1即：成功查找的平均比較次數(shù)約為順序表長度的一半。若key在表中不存在，則需進行n+1次比較設查找成功概率為p，則查找失敗的概率為q=1-p則：ASL=p*(n+1)/2+q*(n+1)=p(n+1)/2+(1-p)(n+1)=(n+1)(1-p/2)設查找成功和失敗的概率各為50%，即p=q=1/2則：ASL=?(n+1)順序查找：算法簡單，對表中元素排列沒有要求，實際應用較多，特別是記錄少時較有效。檢索時間較長二、有序表查找條件：順序存儲并且有序舉例：1234567891011513192137566475808892找21lowhighmid1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmidmid=(1+11)/2=6high=mid-1=5mid=(1+5)/2=3low=(mid+1)=4mid=(4+5)/2=4成功：返回4lowhighmid1234567891011513192137566475808892找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmidmid=(1+11)/2=6low=(mid+1)=7mid=(7+11)/2=9high=(mid-1)=8mid=(7+8)/2=7low=(mid+1)=8mid=(8+8)/2=8high<low查找不成功：返回0high=(mid-1)=7high算法實現(xiàn)：設表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定值初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k==r[mid].key，查找成功若k<r[mid].key，則high=mid-1若k>r[mid].key，則low=mid+1重復上述操作，直至low>high時，查找失敗intSearch_Bin(SSTableST,keyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)high=mid–1;elselow=mid+1;}return0;}性能分析：

折半查找過程中，每經(jīng)過一次比較就把查找范圍縮小一半第i次比較可能涉及的元素個數(shù)

比較次數(shù)涉及元素下限涉及元素上限

11=201=21–1

22=213=22–1

34=227=23–1

48=2315=24–1………

j2j-12j–1設表中有n個元素，則2j-1<n<=2j–1取上限：n=2j–1則最大查找長度j=「log2(n+1)∣

平均查找長度在n個元素的查找表中有：

1個元素需1次比較

2=21………2……4=22………3……8=23………4……………2h-1………h(huán)……+______________________________________________2h-1設n=2h-1

n平均查找長度ASL=∑

pici

i=11h=—∑j*2j-1nj=1

n平均查找長度ASL=∑

pici

i=11h=—∑j*2j-1(n=2h-1)nj=11=—(h*2h–n)n1=—(h*(n+1)–n)n1=—(n+1)h–1n

n+1

=—log2(n+1)–1n由此可見，平均查找長度和最大查找長度相差不多?！?/p>

log2(n+1)–1折半查找：比較次數(shù)少，查找快，但需先排序最大查找長度j=「log2(n+1)∣三、分塊查找將順序表分成多塊，塊內元素任意存放，但塊間有序。12345678910111213141516171822121389203342443824486058745786532248861713索引表查38查找過程：先在索引表中查找記錄所在塊，再在塊內查找。由索引項組成的索引表是按關鍵字有序的，則確定塊的查找可以用順序查找或折半查找，而塊中記錄是任意排列的，則在塊中只能順序查找。性能分析：分塊查找的平均長度為：

ASL=Lb+Lw其中：Lb為查找索引表確定所在塊的平均查找長度

Lw為在塊中查找元素的平均查找長度設將長度為n的表均勻分成b塊，每塊含有s個記錄則b=「n/s∣

假定記錄的查找概率相等則每塊查找概率為1/b即：s/n若用順序查找確定所在塊

1b1s則：ASL=Lb+Lw=—∑j+—∑ibj=1si=1

b+1s+1=—+—2

2

1n=—(—+s)+12

s

1nASL=—(—+s)+12

s平均查找長度不僅和n有關，而且和每塊中記錄個數(shù)s有關在給定n的前提下，當s=n時，ASL取最小值

ASL=n+1≈n設順序表有10000個記錄順序查找一個記錄的平均查找長度為：（n+1)/2即：5000次比較分塊查找：s=n=100，即分成100塊，每塊100個元素分塊查找平均查找長度為：n=100次折半查找：最大查找長度為「log2(n+1)∣=14次ASL最大最小兩者之間表結構無要求有序表分塊有序表存儲結構順序鏈表順序順序鏈表三種查找方法比較順序查找折半查找分塊查找9.2動態(tài)查找表動態(tài)查找表的特點是：表結構本身是在查找過程中動態(tài)生成的。即對給定的關鍵字，若在表中存在，則查找成功，否則插入該關鍵字的記錄。ADTDynamicSearchTable{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均含有類型相同，可唯一標識數(shù)據(jù)元素的關鍵字。數(shù)據(jù)關系R：數(shù)據(jù)元素同屬一個集合?；静僮鱌：

InitDSTable(&DT);

DestroyDSTable(&DT);

SearchDSTable(DT,key);

InsertDSTable(&DT,e);

DeleteDSTable(&DT,key);

TraverseDSTable(DT,Visit());}ADTDynamicSearchTable一、二叉排序樹和平衡二叉樹1、二叉排序樹及其查找過程定義：二叉排序樹或是一棵空樹，或是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值若它的右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值它的左、右子樹也分別為二叉排序樹45125390337619924由定義得到性質：二叉排序樹的中序序列為遞增有序序列在二叉排序樹中查找關鍵字key操作：

①

若根結點的關鍵字等于給定關鍵字key，則返回指向根的指針

②

若根結點的關鍵字小于key，

則在其左子樹上查找，否則在其右子樹上查找45125390337619924BiTree

SearchBST(BiTreeT,keyTypekey){if((!T)||EQ(key,T->data.key))return(T);elseifLT(key,T->data.key))return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}2、二插排序樹的插入和刪除二叉排序樹的插入插入原則：若二叉排序樹為空，則插入結點應為根結點；否則，繼續(xù)在其左、右子樹上查找，直至某個結點的左子樹或右子樹為空為止，則插入結點應為該結點的左孩子或右孩子二叉排序樹生成：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹例：給定關鍵字序列{45，24，53，45，12，24，90}由生成過程可知：在二叉排序樹中插入一個結點時，插入結點總是二叉排序樹的葉子結點，即增加一個葉子結點，所以在插入結點時不需要改變樹中其它結點，只修改一下指針即可實現(xiàn)。所以操作簡單，主要操作是查找插入位置。構造二插排序樹的過程，是對無序序列的排序過程二叉排序樹具有類似于折半查找的特性StatusSearchBST(BiTree

T,keyType

key,BiTree

f,BiTree&p){if(!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);}StatusInsert_BST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rhild=NULL;if(!p)T=s;elseifLT(e.key,p->data.key)p->lchild=s;

lsep->rchild=s;returnTRUE;}elsereturnFALSE;}二叉排序樹結點的刪除要刪除二叉排序樹中的p結點，分三種情況：①若P為葉子結點，則直接刪除。②若P只有左子樹PL或只有右子樹PR，則用其左（右）子樹的根代替被刪除結點PSPPLQ中序遍歷：PLPSQSPLQ中序遍歷：PLSQ中序遍歷：PPRSQSPRQ中序遍歷：PRSQSPPRQ③若P結點的左、右子樹均不空，則沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹變成為S的雙親Q的右子樹，用S取代p中序遍歷：FPCPRCLQQLSSLFSCPRCLQQLSL中序遍歷：CLC……QLQSLSPPRFCLC……QLQSLSPRFFPCPRCL中序遍歷：CLCPPRFFCPRCL中序遍歷：CLCPRF③若P結點的左、右子樹均不空，則若C無右子樹，用C取代p刪除算法StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;else{ifEQ(key,T->data.key)Delete(T);elseifLT(key,T->data.key)DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);returnTRUE;}}voidDelete（

BiTree

＆p）{if(!p->rchild){q=p;p=p->lchild;free(q);}elseif(!p->lchild){q=p;p=p->rchild;free(q);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}}FPCPRCLQQLSSL3、二叉排序樹的查找分析關鍵字序列（45,24,53,12,37,93）452412533793ASL=(1+2+2+3+3+3)/6=14/6關鍵字序列（12,24,37,45,53,93）122437455393ASL=(1+2+3+4+5+6)/6=21/6含有n個結點的二叉排序樹的平均查找長度和樹的形態(tài)有關最好情況：平均查找長度和log2n成正比，即O(log2n)最壞情況：平均查找長度為(n+1)/2，即O(n)平均情況：設有n個關鍵字序列，其中i個小于第1個關鍵字，則有n-i-1個大于第1個關鍵字,

其平均查找長度為p(n,i)根i個n-i-1個P(i)P(n-i-1)p(n,i)=[1+i*(p(i)+1)+(n-i-1)*(p(n-i-1)+1)]/n假設n個關鍵字的排列是隨機的，即小于第1個關鍵字的個數(shù)i從0到n-1按等概率計算1n-1P(n)=—∑p(n,i)ni=0

2n-1=1+—∑i*p(i)n≥2n2i=1因：P(0)=0;P(1)=1可證明：P(n)≤1+4log2n對n!中二叉排序樹進行平均，平均比較次數(shù)為O(log2n)4、平衡二叉樹（BalancedBinaryTree）定義：平衡二叉樹或者是一棵空樹，或者是具有下列性質的二叉樹，它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。平衡因子BF（BalancedFactor）:

該結點左子樹深度減去其右子樹深度例：關鍵字序列（13,24,37,90,53）一般情況下，若插入一個葉子結點，相應子樹的根結點變化大致有三種情況：1）結點原來平衡，現(xiàn)在變成左重或右重2）結點原來某一邊重，而現(xiàn)在成為平衡的3）結點原來就是左重或右重，而新結點加在重的一邊有兩種情況需要調整(1)由于新結點加到本來就重的一邊，如右重新結點插入到右邊的右子樹中（相對為左重插入到左邊的左子樹中）ABα

h-1β

h-1γ

h-2-1中序序列：αAβBγ

RRABα

h-1β

h-1γ

h00中序序列：αAβBγ

h+1h+1voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}rcp左重插入到左邊的左子樹中21中序序列：αBβAγ

LL中序序列：αBβAγ

ABγ

h-1β

h-1α

hABγ

h-1β

h-1α

h00h+1h+1voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}plc(2)原樹右重，新結點插入到右邊的左子樹中（相對為左重插入到左邊的右子樹中）-21中序序列：αAβCγBδRLABα

h-1γ

h-2β

h-1Cδh-11中序序列：αAβCγBδABα

h-1γ

h-2β

h-1Cδh-1ABα

h-1γ

h-2β

h-1Cδ

h-10-10插入前深度：h+1調整后深度：h+1#defineLH+1#defineEH0#defineRH-1typedef

struct

BSTNode{

ElemTypedata;

intbf;

struct

BSTNode*lchild,*rchild;}BSTNode,*BSTree;voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}StatusInsertAVL(BSTree&T,ElemTypee,Boolean&taller){if(!T){T=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=TRUE;}else{ifEQ(e.key,T->data.key)

{taller=FALSE;return0;}ifLT(e.key,T->data.key){if(!InsertAVL(T->lchild,e,taller))return0;if(taller)switch(T->bf){caseLH:

LeftBalance(T);taller=FALSE;brack;caseEH:T->bf=LH;taller=TRUE;break;caseRH:T->bf=EH;taller=FALSE;break;}//switch}//ifelse{

else{if(!InsertAVL(T->rchild,e,taller))return0;if(taller)switch(T->bf){caseLH:T->bf=EH;taller=FALSE;break;caseEH:T->bf=RH;taller=TRUE;break;caseRH:

RightBalance(T);taller=FALSE;brack;}//switch}//else}/elsereturn1;}0voidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){

caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;caseRH:rd=lc->right;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504030604520Tlc000112voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}40306045Tlc502000010深度不變voidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;

caseRH:rd=lc->right;switch(rd->bf){

caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504030604542Tlc0100-12voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}深度不變rd-100000voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}50456040T3042lcrdrd45506040T3042lcvoidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;

caseRH:rd=lc->right;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;

caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504045Tlc0-1-2voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}深度不變rd000voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}504540Tlcrdrd455040TlcvoidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;

caseRH:rd=lc->right;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;

caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504030604548Tlc0-100-12voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}深度不變rd000010voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}50456040T3048lcrd48rd45506040T30lcvoidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}二、B-樹和B+樹一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：(1)樹中每個結點至多有m棵子樹;(2)若根結點不是葉子結點，則至少有兩棵子樹;(3)除根之外的所有非終端結點至少有m/2棵子樹(4)所有非終端結點中包含下列信息數(shù)據(jù)（n,A0，K1,A1,K2,A2，…Kn,An）其中：Ki(i=1,…,n)為關鍵字，且Ki＜Ki＋1(i=1,…,n－1)；Ai(i=0,…,n)為指向子樹根結點的指針，且指針Ai－1所指子樹中所有結點的關鍵字均小于Ki(i=1,…,n)，An所指子樹中所有結點的關鍵字均大于Kn，n(m/2-1≤n≤m-1)為關鍵字的個數(shù)(或n＋1為子樹個數(shù))。所有的葉子結點都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指針為空）。

4階B-樹

hgfedcba135118111127139199243784764533t＃definem3typedef

struct

BTNode{

int

keynum;

struct

BTNode*parent;

keyTypekey[m+1];

struct

BTNode*ptr[m+1];Record*recptr[m+1];}BTNode*BTree;

typedef

struct{

BTNode*pt;

inti;

inttag;}Result;查找算法ResultSearchBTree(BtreeT,KeyTypeK){p=T;q=NULL;found=FALSE;i=0;while(p&&!found){n=p->keynum;i=Search(p,k);if(i>0&&p->key[i]==k)found=TRUE;else{q=p;p=p->ptr[i];}

｝

if(found)return(p,i,l);elsereturn(q,i,0);}查找分析在文件系統(tǒng)中，結點查找在磁盤上進行，關鍵字查找在內存中進行，所以查找結點是影響效率的主要因素。即：B樹的層數(shù)是決定B樹查找效率的主要因素。主要問題：最壞情況下，含有N個關鍵字的m階B樹的最大深度是多少？以2-3樹為例：一般情況：在B樹中，具有N個關鍵字，則有N+1個葉子結點，按每個結點盡可能少的關鍵字來組織B樹，則根據(jù)定義：第一層至少有1個結點第二層至少有2個結點第三層至少有2(m/2)個結點第四層至少有2(m/2)*(m/2)個結點第l+1層至少有2(m/2)l-1個結點查找成功時，在前l(fā)層上，查找失敗為l+1層因對于N個關鍵字的m階B樹有N+1個葉子所以N+1=2(m/2)l-1此時因各層取最小值，則l取最大值因此l<=logm/2(N+1)/2+1也就是說，在含有N個關鍵字的B樹上進行查找時，從根結點到關鍵字所在結點的路徑上涉及的結點數(shù)不超過

l<=logm/2(N+1)/2+1例：N=1999998m=199l最大為4插入算法StatusInsertBTree(Btree&T,KeyTypeK,Btreeq,inti){x=K;ap=NULL;finished=FALSE;while(q&&!finished){Insert(q,i,x,ap);if(q->keynum<m)finished=TRUE;else{s=m/2;split(q,s,ap);x=q->key[s];q=q->parent;if(q