数据结构 第九章查找

第9章查找主要内容：静态查找表----顺序、折半、分块动态查找表----各种树表哈希表讨论各种查找方法的效率相关术语及概念查找表（SearchTable）:由同一类型的数据元素构成的集合。关键字（key）：用来标识一个数据元素的数据项。查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的一个记录，则查找成功，否则查找不成功。静态查找表（StaticSearchTable）:查找过程中查找表本身不发生变化的查找表。（无插入、删除操作）动态查找表（DynamicSearchTable）:查找过程中查找表本身发生变化(插入或删除元素)的查找表。查找方法评价

查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength):为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值对含有n个记录的查找表，查找成功时的平均查找长度为：

nASL=∑

pici

i=1n其中：pi为查找表中第i个记录的概率，且∑pi=1

i=1

ci为找到表中第i个元素所需比较次数9.1静态查找表ADTStaticSearchTable{

数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均具有相同类型，各元素具有可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：

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监视哨iiii查找成功返回7

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

n平均查找长度ASL=∑

pici

i=1顺序查找时比较次数取决于所查找记录在表中的位置。一般情况：Ci=n–i+1在等概率情况下：nASL=∑

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

i=1即：成功查找的平均比较次数约为顺序表长度的一半。若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算法实现：设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,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;}性能分析：

折半查找过程中，每经过一次比较就把查找范围缩小一半第i次比较可能涉及的元素个数

比较次数涉及元素下限涉及元素上限

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……+______________________________________________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由此可见，平均查找长度和最大查找长度相差不多。≈

log2(n+1)–1折半查找：比较次数少，查找快，但需先排序最大查找长度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有关，而且和每块中记录个数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动态查找表动态查找表的特点是：表结构本身是在查找过程中动态生成的。即对给定的关键字，若在表中存在，则查找成功，否则插入该关键字的记录。ADTDynamicSearchTable{

数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：

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、二插排序树的插入和删除二叉排序树的插入插入原则：若二叉排序树为空，则插入结点应为根结点；否则，继续在其左、右子树上查找，直至某个结点的左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树例：给定关键字序列{45，24，53，45，12，24，90}由生成过程可知：在二叉排序树中插入一个结点时，插入结点总是二叉排序树的叶子结点，即增加一个叶子结点，所以在插入结点时不需要改变树中其它结点，只修改一下指针即可实现。所以操作简单，主要操作是查找插入位置。构造二插排序树的过程，是对无序序列的排序过程二叉排序树具有类似于折半查找的特性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个结点的二叉排序树的平均查找长度和树的形态有关最好情况：平均查找长度和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个关键字的个数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!中二叉排序树进行平均，平均比较次数为O(log2n)4、平衡二叉树（BalancedBinaryTree）定义：平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树，它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。平衡因子BF（BalancedFactor）:

该结点左子树深度减去其右子树深度例：关键字序列（13,24,37,90,53）一般情况下，若插入一个叶子结点，相应子树的根结点变化大致有三种情况：1）结点原来平衡，现在变成左重或右重2）结点原来某一边重，而现在成为平衡的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)所有非终端结点中包含下列信息数据（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)为关键字的个数(或n＋1为子树个数)。所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

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);}查找分析在文件系统中，结点查找在磁盘上进行，关键字查找在内存中进行，所以查找结点是影响效率的主要因素。即：B树的层数是决定B树查找效率的主要因素。主要问题：最坏情况下，含有N个关键字的m阶B树的最大深度是多少？以2-3树为例：一般情况：在B树中，具有N个关键字，则有N+1个叶子结点，按每个结点尽可能少的关键字来组织B树，则根据定义：第一层至少有1个结点第二层至少有2个结点第三层至少有2(m/2)个结点第四层至少有2(m/2)*(m/2)个结点第l+1层至少有2(m/2)l-1个结点查找成功时，在前l层上，查找失败为l+1层因对于N个关键字的m阶B树有N+1个叶子所以N+1=2(m/2)l-1此时因各层取最小值，则l取最大值因此l<=logm/2(N+1)/2+1也就是说，在含有N个关键字的B树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过

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