《数据结构与算法》第7章 查找

第7章查找7.1查找的基本概念

7.2顺序表的查找

7.3树表的查找

7.4哈希表及其查找7.1查找的基本概念查找 假定k1,k2,…,kn是互不相同的关键字值，有一个集合T，其中有n个记录，形式如下：(k1，I1)，(k2，I2)，…，(kn，In)其中Ij是与关键字值kj相关的信息，1≤j≤n。给定一个特定的关键字值K，查找问题是在T中确定记录（kj，Ij），使得kj

=K。查找表是记录的集合，每个记录至少包含一个关键字。查找实际上就是根据给定的关键字值，在查找表中找出一个记录，该记录的关键字值恰好等于给定的值。根据关键字匹配的情况，查找有两种可能的结果：一种是找到了相应的记录，即找到至少一个关键字值为kj

的记录使得kj=K，此称为成功查找；一种是找不到相应的记录，称为不成功查找。一般地，查找还分精确匹配查询和范围查询两种。所谓精确匹配查询是指检索关键字值完全匹配特定值的记录。范围查询是指检索关键字值在某个指定关键字值范围的所有记录。有的关键字，它的值一旦指定，就可以唯一地对应着一条记录，这种能够唯一确定一条记录的关键字称为主关键字。所有主关键字的值均不相同，它们与记录一一对应。有些关键字的值指定以后，不能唯一地对应一个记录，而是可能对应很多记录，这样的关键字称为次关键字。根据数据存储介质的不同，查找又分为两种类型。当数据量非常大，需要借助于外存存储数据时，相应的查找称为外部查找。反之，全部数据都可以存放在内存中时，相应的查找称为内部查找。目前有三类检索算法：分别是顺序和列表方法、根据关键字值直接访问和树索引方法。顺序和列表方法一般基于顺序表，依据顺序表中关键字的排列不同，又分为顺序查找、折半查找及索引顺序查找。根据关键字值直接访问方法即哈希方法，又称散列方法。树索引方法包括二叉排序树、B-树等查找方法。7.2顺序表的查找所谓顺序表，其逻辑结构即是线性表，存储结构多采用静态存储，也可以采用链表方式存储。 采用数组存储时，顺序表的类定义如下：

template<classKeyType>searchList; //向前声明

template<classKeyType> //节点类的定义

classElemType{

public:

friendclasssearchList<KeyType>; //声明searchList类为节点类的友类

ElemType();

~ElemType();

private:

KeyTypekey;

};

template<classKeyType> //被检索数据表类的定义

classsearchList{

public:

searchList();

~searchList();

int

search(KeyTypetarget); //检索关键字为target的记录

private:

ElemType<KeyType>*element;

int

MaxSize,CurrentSize;

}; 用链表表示顺序表时，定义类如下：

template<classKeyType> //节点类的定义

classElemType{

public:

friendclasssearchList<KeyType>; //声明友类

ElemType();

~ElemType();

private:

KeyTypekey;

ElemType<KeyType>*next;

}; template<classKeyType> //被检索数据表类的定义

classsearchList{

public:

searchList();

~searchList();

ElemType<KeyType>*search(KeyType&target);

private:

ElemType<KeyType>*element;

int

CurrentSize;

};7.2.1顺序查找顺序查找是最简单、最自然的查找方法，它的基本思想是用给定的关键字值与表中各个记录的关键字值逐个进行比较。初始时，给定的关键字与表中第一个记录的关键字相比较，若两个值相等表示找到目标，查找成功；否则将关键字与表中下一个记录的关键字继续比较并判断是否相等。如此循环。如果直到比较到最后一个记录的关键字时两个值都不相等，表明所存储的数据中没有要查找的数据，查找不成功。这种查找方法对顺序存储和链式存储都是适用的。 顺序查找算法如下：

template<classKeyType>

int

searchList<KeyType>::search(KeyTypetarget){ //成功，返回记录所在下标，否则返回0

element[0].key=target; //下标为0的记录为监视哨

inti=CurrentSize;

while(element[i].key!=target){ //对记录号从大到小，逐个查找

i--;

}

returni; //返回查找结果

};这个顺序查找方法也适用于关键字值有重复的情况。当关键字值出现重复时，从while循环中退出后，i记录的是查找目标在顺序表中最后一次出现的位置。 当采用链表表示顺序表时，顺序查找方法如下：

template<classKeyType>

ElemType<KeyType>*searchList<KeyType>::search(KeyType&target){

//返回的是指向所查找节点的指针，若不成功，则为NULL

ElemType<KeyType>*p=element,q=NULL;

while(p!=NULL){

if(p->key!=target){

q=p;

p=p->next;

}

else{

break;

}

}

returnp;

};顺序查找的效率如何呢？它在空间方面只要求一个记录大小的辅助空间（即element[0]），自然是微不足道的。对于它的时间复杂度的分析，需要建立一个评价标准。这就是平均查找长度（AverageSearchLength）的概念。对于一个给定的关键字k值，在具有n个记录的查找表中进行查找，最好的可能是经过一次比较就能查到。在顺序查找的情况下，最坏的可能是要经过n次比较才能查到。为了表示在平均意义下的查找次数，定义平均查找长度为： 其中，n为表中记录个数，Pi为查找第i个记录的查找概率，Ci为查到第i个记录时的比较次数。在我们给出的顺序查找的算法中，Ci=n-i+1。假设查找表中每个记录的概率相等，那么 。此时

这就是说，成功查找的平均查找长度为(n+1)/2。显然，不成功查找的查找次数为n+1。这个结果表明：顺序查找的平均查找长度与表中的记录个数成正比，无论成功查找还是不成功查找，皆可记为O(n)。当所有关键字的出现频率不一样时，还可以进一步改进顺序查找方法，使用关键字出现的频率信息来组织记录的排列：按照查找频率从高到低排列记录，先放置查找频率最高的记录，接下来是查找频率次高的记录，依此类推。这样组织的表称为自组织线性表。

对这样的线性表，它的查找仍然是从第一个位置开始顺序进行。由于各记录依查找概率从大到小依次排列，所以查找的平均比较次数比(n+1)/2要少，查找需要的预期比较数目是：Cn=1P1+2P2+…+nPn

其中Pi

是访问第i个记录的概率。目前有三个传统的启发式规则：保持一个根据频率排序的线性表最显然的方式是为每一个记录保存一个访问计数，而且一直按照这个顺序维护计数。这种方法称为计数方法。当访问频率变化较大时，重排记录会花费较多的时间。当找到一个记录时就把它放到线性表的最前端，而把其它记录后退一个位置。这类似于“最近最少使用”缓冲池替代策略，称为移至前端方法。把找到的记录与它在线性表中的前一个记录交换位置，这种启发式规则称为转置。7.2.2折半查找在顺序存储的条件下，若各记录是按其关键字值的大小依次存放的，则这个查找表称为有序表。在有序表中可采用折半查找（或称为二分查找）的方法进行查找。设各记录在表中按关键字值由小到大依次存放。折半查找的基本思想是：先取表的中间位置记录的关键字与给定关键字的值进行比较，如果给定值正好与该记录的关键字值相等，则查找成功；如果给定值比该记录的关键字值大，则要查找的记录一定在表的后半部分；如果给定值比该记录的关键字值小，则要查找的记录一定在表的前半部分。这样，当还没有查到目标时，都是在表的长度缩小一半后继续进行查找，依此反复进行。在最坏的情况下，当表的长度缩小为1时，若该位置记录的关键字仍然不等于给定的值，则可以肯定表中不存在所要找的记录，于是宣布查找不成功。例：有如下11个元素的有序表（其数据元素的关键字为整数），现在要查找关键字为24的数据元素。假设指针low和high分别指向待查元素所在区间的下界和上界，指针mid指向该区间的中间位置，即：。 初始状态如图7.1。图7.1二分查找初始状态查找过程如图7.2所示图7.2关键字为24的二分查找过程如果给定关键字值k=86，在同样的有序表上再看一看查找过程，见图7.3。图7.3关键字为86二分查找过程如图7.3所示，经过三次比较之后，mid=10，该位置的关键字值89>86，按规定应在前半区间[low,mid-1]继续查找，但此时新的区间上界mid-1=9，它已小于下界low=10，即新的区间已不存在，这就意味着查找表中根本没有关键字值为86的元素，应宣布查找不成功。折半查找的具体算法//折半查找template<classKeyType>int

searchList<KeyType>::BinSearch(KeyTypetarget){//若成功，返回记录号，否则返回－1

intlow=1,high=CurrentSize; //置区间初值

intfound=0,mid; //置是否找到标记found为0（未找到）

while(low<=high&&!found){ //当区间下界未超过上界且未找到时，循环查找

mid=(low+high)/2; //求中点

if(element[mid].key==target){ found=1; //已找到，置标记found为1 }

else{ if(target>element[mid].key){ low=mid+1; //在后半区间继续查找

} else{ high=mid-1; //在前半区间继续查找

} } } if(found){ returnmid; //查找成功，返回找到的记录的位置

} else{ return-1; //查找不成功，返回-1为标记

}};上述算法当成功查找时，能保证查找目标一定落在从low到high的区间内，并不能保证找到的关键字值是有序表中的第一次出现。这个过程可用图7.4表示：图7.4二分查找过程示意修改程序中的while循环，得到如下实现：//修改后的折半查找template<classKeyType>int

searchList<KeyType>::BinSearch(KeyTypetarget){//若成功，返回记录号，否则返回－1

intlow=1,high=CurrentSize; //置区间初值

intmid; while(low<high){ //当区间下界未超过上界时，循环查找

mid=(low+high)/2; //求中点

if(target>element[mid].key) low=mid+1; //在后半区间继续查找

else high=mid; //在前半区间继续查找

}; if(low==high) returnmid; //查找成功，返回找到的记录的位置

else return-1; //查找不成功，返回-1为标记} //算法结束如果有序表中存在目标，则使用这个算法能够得到目标在有序表中第一次出现的位置。这个过程如图7.5所示。图7.5折半查找过程示意折半查找的平均查找长度可以用二叉树进行分析。我们仍以上述的具有11个元素的有序表为例，从折半查找过程可知，查到表中第6个位置仅需一次运算，找到第3和第9个位置各需要两次运算，以此类推。查找过程如图7.6所示。图7.6用二叉树分析折半查找性能6901113478125平均查找长度 设有序表的长度为n=2h-1，则描述折半查找过程的二叉树为满二叉树，其深度h=log2(n+1)。在这棵二叉树中，层次为1的结点有1个，层次为2的结点有2个，…，层次为h的结点有2h-1-1个。现仍设表中每个记录的查找概率相等，即Pi=1/n，则查找成功时折半查找的平均查找长度：由上式可见，当查找成功时折半查找的平均查找长度对n来说是对数级的。另外，当查找不成功时，折半查找算法必须从二叉树的根走到叶才能知道，自然也是对数级的。当然，使用折半查找必须是在顺序存储方式下，且必须做到按记录的关键字值排序才行。折半查找时的一个关键位置是查找区间的中间位置。修改这种方法，预先存储记录的关键字值的预期分布情况，查找时一般不从查找区间的中间位置开始，而是根据关键字值，预测出它的可能位置，然后再在该位置附近的小区间内进行寻找。这种方法称为字典检索。7.2.3索引顺序表的查找索引顺序查找 又称分块查找，是顺序查找方法的一种改进。改进办法是将原来对所有n个记录逐个查找，变为先将n个记录分成若干组，再建一个索引表。当给定一个关键字后，先通过查索引表确定应在哪一组中查找，然后再在该组中顺序查找，索引表必须按关键字有序。“按块有序” 各子表（块）中第二块中一切记录的关键字必须大于第一块中最大关键字，第三块中一切记录的关键字必须大于第二块中最大关键字，依此类推，每块内部不要求按关键字有序。这种表的结构如图7.7所示。查找过程确定要找的记录所在的块（子表）在块中顺序查找图7.7索引顺序表的结构示意图平均查找长度 由于索引表是按关键字有序的，所以查索引表时可以用顺序查找也可以用折半查找，而在子表内只能用顺序查找。分块查找的平均查找长度也是这两步平均查找长度之和，即为：ASL=Lb+Lw

其中Lb为查找索引表以确定所在块的平均查找长度，Lw为在块内查找所要的记录的平均查找长度。

现在的问题是如何分块才能提高查找速度。我们假设对表中每个记录的查找概率相等，并且假设分块是均匀的。设有n个记录，平均分为b块，每块含有s个记录，即b=n/s。若查索引表和在块内查找均用顺序查找，则

在n已确定的前提下，根据求一元函数最小值的方法，可以求出当s=时，ASL取最小值，且它的值为+1。7.3.1二叉排序树二叉排序树（binarysorttree）

它或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树所有结点上记录的关键字值均小于它的根结点上记录的关键字值；若它的右子树不空，则右子树所有结点上记录的关键字值均大于它的根结点上记录的关键字值；它的左、右子树也都是二叉排序树。在图7.8所示的两棵树都是二叉排序树，在它们的结点上列出了所存记录的关键字。(a)中关键字为整数，在(b)中关键字为字符串（姓氏的汉语拼音），这些关键字都是可以比较大小的。图7.8二叉排序树示例81213165610112371(a)(b)hanliuzhaoliduanfangduguochen二叉排序树中的结点类说明如下：template<classKeyType>BST; //类的向前声明template<classKeyType>classBstNode{ public: friendclassBST<KeyType>;

BstNode(); ~BstNode(); private:

KeyTypekey; //关键字值

BstNode<KeyType>*lchild,*rchild;//左右子树指针};二叉排序树的类的说明如下：template<classKeyType>classBST{ public: BST(); ~BST();

BstNode<KeyType>*search(KeyType

k,BstNode<KeyType>*ptr); private:

BstNode<DataType>*root;};二叉排序树查找的基本思想

设要查找的目标为target，从根结点开始，如果根结点的关键字等于查找目标target，则查找成功，并返回指向目标的指针。如果目标target小于根结点的关键字值，则在它的左子树继续查找；如果目标target大于根结点的关键字值，则在它的右子树继续查找；依此类推。这个过程沿着从根到叶结点的一条路径向下查找，查找过程中遇到空指针时表示查找失败，二叉排序树中不存在查找目标target。//二叉排序树的查找template<classDataType>BstNode<KeyType>*BST<KeyType>::BstSearch(KeyType

target,BstNode<KeyType>*t){//返回指向所查找节点的指针，若不成功，则返回NULL

if((t==NULL)||(t->key==target)){ returnt; //当树为空或者已经找到节点时返回

} else{ if(t->key>target){ returnBstSearch(target,t->lchild);//搜索左子树

} else{ returnBstSearch(target,t->rchild);//搜索右子树

} }};template<classKeyType>BstNode<KeyType>*BST<KeyType>::Search(KeyTypetarget){

return(Search(target,root));};例：根据二叉排序树的查找算法，在图7.9所示的二叉排序树中，分别查找关键字为61和37的结点。图7.9二叉排序树示例47569098153461875204135二叉排序树的生成

二叉排序树的生成就是从空树开始依次将结点插入到树中的过程。在一棵二叉排序树中插入一个新结点的算法是：若二叉排序树为空树，则新结点为二叉排序树的根结点；若二叉排序树非空，则比较新结点的关键字值和根结点的关键字值，若新结点关键字小于根结点关键字，则新结点插入到根的左子树中，否则插入到根的右子树中。//二叉排序树的插入算法template<classDataType>voidBST<KeyType>::BstInsert(KeyType

k,BstNode<KeyType>*t){ //插入结点的关键字为k，树根为t

if(t==NULL){ t=newBstNode(); t->key=k; } else{ if(k<t->key){

BstInsert(k,t->lchild); } else{

BstInsert(k,t->rchild); } }}template<classKeyType>voidBST<KeyType>::Insert(KeyTypex){

BstInsert(x,root);}例：按照二叉排序树的插入算法，在图7.9所示的树中依次插入关键字为58和17的两个新结点。图7.10二叉排序树插入示例174756909815346187520413558若从空树开始，依次插入关键字分别为e、b、d、f、a、c和g的结点，建立一棵二叉树，则这棵树的建立过程如图7.11所示。图7.11二叉排序树的生成过程二叉排序树的删除 假设在二叉排序树上要删除的结点为x，它的双亲结点由指针f所指，不失一般性，设x为f的左孩子（若x为f的右孩子，删除算法类似）。这时，分三种情况考虑：x为叶结点，此种情况最为简单，删除该结点后，只须令f的左孩子指针为空即可。即令f->lchild=NULL。这个过程如图7.12所示。x只有左子树LTree或只有右子树RTree，删除x结点后，只须令LTree或RTree直接成为其双亲结点f的左子树即可。即令f->lchild=x->lchild，或f->lchild=x->rchild。x只有左子树LTree的情况如图7.13所示，x有右子树Rtree的情况与此类似。图7.12删除二叉排序树中的叶结点图7.13删除二叉排序树中有一个孩子的分支结点x结点的左、右子树均不空，这种情况比较复杂。因为删除x所指的结点后，其左、右子树不能全都连接在其双亲结点f的左孩子指针上，破坏了原来树的结构。必须找一个合适的方法，才能将LTree和RTree都安排妥当。为了保持树的结构，一般地是在树中寻找另一个结点w来顶替被删除的结点x，然后转而删除w。实际上，以w顶替x后，要保证满足二叉排序树的有序性。根据有序性，显然只能由被删结点的直接前趋或是直接后继来顶替，以其余任何结点来顶替都会增加逆序对，从而不能满足有序性。

直接前趋和直接后继 中序遍历二叉树时，左子树上所有结点都位于根结点之前，右子树上所有结点都位于根结点之后，而中序遍历二叉排序树时刚好得到一个有序的序列。这样，根的左子树中最后一个遍历结点应该是根的直接前趋，其右子树中第一个遍历结点应该是根的直接后继。任一结点的（中序遍历的）直接前趋是其左子树中的最后一个结点，即“右下角”，（中序遍历的）直接后继是其右子树中的第一个结点，即“左下角”。根据刚才的分析，以w填充x的位置后，仍能保证二叉排序树的特性。这样删除x就变为删除w。而w是x的直接前趋，它是x的左子树中的右下角，它的右孩子指针为空，这意味着w的孩子结点个数最多为1。这种情况可以归结为前述第一、二种情况。这个过程如图7.14所示。图7.14删除二叉排序树中有二个孩子的分支结点例：以7.10所示的二叉排序树为例，分别删除关键字35和90所在的结点。图7.15二叉排序树删除示例二叉排序树的删除算法如下：template<classDataType>voidBST<KeyType>::BstDelete(KeyType

x,BstNode<KeyType>*&t){

BstNode<KeyType>*p,q;

if(t!=NULL) { if(t->key>x){

BstDelete(x,t->lchild); //搜索左子树

} else{ if(t->key<x){

BstDelete(x,t->rchild); //搜索右子树

} else{ if(t->lchild==NULL&&t->rchild==NULL){//左右子树都为空

p=t; t=NULL; deletep; }

else{ if(t->lchild==NULL){//左子树空，右子树不为空，

p=t; t=t->rchild; deletep; } else{ if(t->rchild==NULL){//左子树不空，右子树为空

p=t; t=t->lchild; deletep; } else{ //左右子树都不为空

p=t; q=t->lchild; //转左子树

while(q->rchild!=NULL){//向右到右下角

p=q; q=q->rchild; }

t->data=q->data;

if(p!=t){ p->rchild=q->lchild; //重新连接*p的右子树

} else{ p->lchild=q->lchild; //重新连接*p的左子树

} deleteq; //释放结点

} } } } } }}template<classDataType>voidBST<KeyType>::BDelete(KeyTypek){

BstDelete(k,root);}查找效率

根据建树的算法，当关键字个数一定时，所生成二叉排序树的深度不仅与关键字个数有关，而且与这些关键字插入的次序有关。 二叉排序树的深度不仅决定了查找中最大比较次数，也影响了平均查找长度。现在仍假设对树中7个关键字的查找概率相等，都是1/7，则图7.11所示的树的平均查找长度为

ASL(7.11)=(1+2+2+3+3+3+4)=18/7例：图7.11所示的二叉排序树中的关键字，如果关键字的插入次序改变了，会生成不同的二叉排序树。图7.16不同深度的二叉排序树示例图7.16(a)树的平均查找长度为

ASL(7.16a)=(1+2+3+4+4+5+6)=25/7

实际上，图7.11(b)树已是单链形式，而图7.11(c)更是退化为线性表，因此它们的平均查找长度与对顺序表进行顺序查找时的平均查找长度相同。一般来说，对于n个记录，当它们的关键字随机出现时，所构成的二叉排序树还是比较均衡的。可以证明，在这样构成的二叉排序树上进行查找，其平均查找长度为O(log2n)。7.3.2平衡二叉树1962年，Adel’son-Vel’skii和E.M.Landis提出了一种二叉树结构，这种二叉树对于各级子树的深度是比较平衡的，称为平衡二叉树、高平衡树，又称AVL树。它满足二叉排序树的特性，树型上也是比较平衡的，可以达到较高的查找效率。

平衡二叉树

它或是一棵空树，或是具有下列性质的二叉排序树：它的左子树和右子树的深度之差的绝对值不超过1；它的左、右子树都是平衡二叉树。平衡因子

该结点的左子树的深度减去右子树的深度。若某个结点的平衡因子出现大于1或小于-1的情况，说明平衡遭到破坏，需要将二叉排序树进行调整，使之重新变为平衡。图7.17所示的为平衡的二叉排序树，图7.18所示的为不平衡的二叉排序树（'/'表示左子树高1，'-'表示左右子树等高，'\'表示右子树高1）。图7.17平衡的二叉排序树图7.18不平衡的二叉排序树例：假设有一组关键字出现的次序为{k，m，u}，按照二叉排序树的插入过程，从空树开始，依次插入k，m，u三个关键字后，生成的树如图7.19(a)所示。恢复平衡后的二叉树如图7.19(b)所示。图7.19平衡二叉排序树的向左旋转二叉平衡树中结点的插入

假设由于在平衡二叉树上插入一个结点以后，使得原来的二叉树失去平衡，由上例可见，只须在局部调整某一子树即可。设这棵失去平衡的最小子树的根结点被指针root所指，对于这棵子树可以分为四种情况进行调整。RR型 新结点插入在root结点右孩子的右子树中，从而失去平衡。此时将root的右孩子right_tree上提为子树的根结点，令root为right_tree的左孩子，right_tree的原右子树T3保持不变，其左子树T2变更为root的右子树，根据二叉排序树的特性，变换后的树仍符合要求。这样的调整称为单旋转，其调整过程如图7.20所示。图7.20AVL树的单旋转LL型

新结点插入在root结点的左孩子的左子树中，从而失去平衡。此时将root的左孩子left_tree上提为子树的根结点，令root为left_tree的右孩子，其余部分按二叉排序树的要求进行相应调整。LL型旋转类似于RR型旋转。RL型

新结点插入在root结点的右孩子的左子树中，从而失去平衡。此时将root的右孩子right_tree的左孩子sub_tree提升为子树的根结点，将root和right_tree分别作它的左、右孩子，其余部分按二叉排序树的要求进行相应调整。由二叉排序树的特性可知，变换后的树仍符合二叉排序树的要求。这样的变换称为双旋转，其调整过程如图7.21所示。图7.21AVL树的双旋转LR型 新结点插入在root结点的左孩子的右子树中，从而失去平衡。此时将root的左孩子left_tree的右孩子sub_tree提升为子树的根结点，将left_tree和root分别作为它的左、右孩子，其余部分按二叉排序树的要求进行相应调整。这个过程类似于RL旋转。AVL树中结点及树的说明如下：//***********AVL树**************///AVL树结点的定义template<classKeyType>AVLTree;template<classKeyType>classAVLNode{public:

AVLNode(); ~AVLNode(); friendclassAVLTree<KeyType>; //声明友类private:

KeyTypekey;

AVLNode*lchild,*rchild;

intbalance;};///AVL树的定义template<classKeyType>classAVLTree{public:

AVLTree(); ~AVLTree();

int

Insert(KeyTypex); voidR_Rotate(); voidL_Rotate();private:

AVLNode*root;};AVL树由失平衡到恢复平衡所进行的单旋转操作如下，以RR型为例：///左单旋转（RR型）template<classKeyType>voidAVLTree<KeyType>::L_Rotate(AVLNode*&Tree){

AVLNode*rightchild=Tree->rchild; Tree->rchild=rightchild->lchild;

rightchild->lchild=Tree; Tree->balance=0; //调整平衡因子

Tree=rightchild; //Tree指向新的根结点};AVL树由失平衡到恢复平衡所进行的双旋转操作如下，以RL型为例：///双旋转（RL型）template<classKeyType>voidAVLTree<KeyType>::LeftBalance(AVLNode*&Tree){

AVLNode*leftchild=Tree->child;

AVLNode*rightchild;

switch(leftchild->balance){ //检查左孩子的平衡因子

case1: //新插入结点在*leftchild的左子树

Tree->balance=0; //调整平衡因子

leftchild->balance=0;

R_Rotate(Tree); //做右单旋转

break; case-1://新插入结点在*leftchild的右子树，要做双旋转

rightchild=leftchild->rchild;

switch(rightchild->balance){ //检查*right的平衡因子以调整*Tree和*leftchild的平衡因子

case1: Tree->balance=-1;

leftchild->balance=0; break; case0: Tree->balance=0; leftchild.balance=0; break; case-1: Tree->balance=0;

leftchild->balance=1; break; }

rightchild->balance=0;

L_Rotate(Tree->lchild); //对*Tree的左子树做左单旋转

R_Rotate(root,root); //对*Tree做右单旋转

}}在AVL树中插入一个节点的实现如下：///AVL树的插入template<classKeyType>int

AVLTree<KeyType>::Insert(AVLNode*&Tree,KeyType

x,int&taller){//在AVL树Tree中插入关键字为x的结点，成功则返回1，否则返回0。//若因插入而使该AVL树失去平衡，则作平衡旋转处理。

intsuccess=0;

if(Tree==NULL){ //*Tree原为空树或者某结点的空链域，插入新的结点。

Tree=newAVLNode(x); success=1; //插入成功标志

taller=1; //置taller为1，表示树长高

} else{ if(x<Tree->key){ //应该继续在左树中搜索插入位置

success=Insert(Tree->lchild,x,taller); if(success==0){ //未插入

returnsuccess; }

if(taller==1){ //已经插入到左子树，并且左子树长高了

switch(Tree->balance){ //检查*Tree的平衡因子

case1: //原先左子树就比右子树高，做平衡处理

LeftBalance(Tree); taller=0; //不长高

break; case0: //原左右子树等高

Tree->balance=1; //改变平衡因子

taller=1; //长高

break; case-1: //原右子树高，现在左右子树等高

Tree->balance=0; //改变平衡因子

taller=0; //不长高

break; } } else{ if(x>Tree->key){ //在右子树中搜索

success=Insert(Tree->rchild,x,taller); if(success==0){ //未插入

returnsuccess; }

if(taller==1){//已经插入到右子树，并且右子树长高了

switch(Tree->balance){//检查*Tree的平衡因子

case1: //原先左子树高，现在左右子树等高

Tree->balance=0;//改变平衡因子

taller=0; //不长高

break; case0: //原先左右子树等高

Tree->balance=-1;//改变平衡因子

taller=1; //长高了

break; case-1://原先右子树比较高，需要做平衡处理

RightBalance(Tree); taller=0; //不长高

break; } } } } } } returnsuccess; //返回是否成功的信息};例：在图7.22(a)所示的平衡二叉树中，插入结点65。图7.22在平衡二叉树中插入一个结点的变化过程二叉排序树中的结点删除

问题可以归结为只需处理最多有一个孩子的结点的删除问题，不失一般性，这里也仅讨论AVL树中最多有一个孩子的结点的删除问题。如果要删除有两个孩子的结点，我们可以先用其直接前趋或是直接后继结点顶替它，然后再删除顶替它的这个结点。而这个结点最多只有一个孩子。 假设被删除结点为x，树根为root。以从x的父结点到root的路径上的每个结点p为根的子树的高度可能因删除x而变矮，结点的平衡因子也会随之改变，从而树失平衡。为了标记这个变化，用一个逻辑变量shorter来标记当前子树的树高是否变小。依次处理从x的父结点到root的路径上的每个结点p，如果以p为根的树高变小，即shorter为TRUE，则分以下三种情况分别进行处理；如果树高保持不变，shorter为FALSE时，则算法结束。第一种情况，p原来的平衡因子为0，根据x所在的子树情况，相应地修改p的平衡因子以适应新的状况。shorter为FALSE。如图7.23所示。图7.23删除并不改变树高第二种情况，p的平衡因子不是0，x位于p较高的子树上，删除x后，将p的平衡因为修改为0，shorter为TRUE，继续处理p的父结点。如图7.24所示。图7.24在高子树上删除第三种情况，p的平衡因子不是0，x位于p较矮的子树上，也就是说原来较矮的子树更矮了，以p为根的子树失平衡。此时需要进行旋转来恢复平衡。设q为p较高子树的根，分以下三种情况讨论：q的平衡因子为0，此时进行单旋转，q变为子树的根，而p变为q的孩子结点，其他部分做相应调整。shorter为FALSE。如图7.25所示。图7.25q的平衡因子为0q的平衡因子与p的平衡因子相等。此时进行单旋转，q变为子树的根，而p变为q的孩子结点，其他部分做相应调整。shorter变为TRUE。如图7.26所示。

图7.26p与q的平衡因子相等

q的平衡因子与p的平衡因子相反。此时进行双旋转，第一次以q为轴旋转，第二次以p为轴旋转。其他部分做相应调整。shorter变为TRUE。如图7.27所示。图7.27进行双旋转例：在图7.28所示的AVL树中，删除p结点。图7.28在AVL树中删除pp有两个孩子，假设以其直接前趋o顶替它。m的右子树如图7.29所示。图7.29m的右子树从被删结点o的父结点到根的路径上有n、o和m三个结点，依次进行处理。对结点n，删除的是它高子树上的结点，修改n的平衡因子，shorter为true。对结点o，删除是的它矮子树上的结点，这是前述的3.2情况，以o为轴进行向左旋转，shorter为true。调整后的树如图7.30所示。图7.30左旋转后的树对结点m，删除的是它矮子树上的结点，并且它与左孩子的平衡因子相反，这是前述的3.3情况，先做一个以e为轴的向左旋转，再做一个以m为轴的向右旋转。最后得到的平衡的树如图7.31所示。图7.31恢复平衡的AVL树二叉平衡树的查找效率

先分析深度为h的平衡二叉树所含有的最少结点数。 设Nh表示深度为h的平衡二叉树中含有的最少结点数，显然N1=1，N2=2，并且Nh=Nh-1+Nh-2+1（h>2）。可以证明，Nh约等于φh+2/-1，其中φ=（1+）/2。反之，令含有n个结点的平衡二叉树的最大深度为h，根据Nh的近似表示，可以解出h=logφ((n+1))-2。 这说明在平衡二叉树中，树的深度h与结点总数n仍为对数关系。也就是说，在平衡二叉树中进行查找的时间复杂度为O(logn)。这个结论虽与随机形成的二叉排序树的平均查找长度相同，但是平衡二叉树从根本上避免了退化的可能性，因此它无疑地是对二叉排序树的一种改进。7.3.3B-树B-树

1970年Bayer等人提出一种多叉平衡查找树，称为B-树。一棵m阶B-树或者为空，或者为满足下列性质的m叉树：树中每个结点至多有m棵子树；根结点至少有两棵子树；除根结点之外，每个结点至少有棵子树；所有叶结点都出现在同一层上；所有结点都包含如下形式的数据：（n,A0,K1,A1,K2,A2,…,Kn,An） 其中n为关键字的个数，Ki（i=1,…,n）为关键字，且满足K1<K2<…<Kn。Ai（i=0,1,…,n）为指向子树根结点的指针，且对于i=1,2,…,n-1，Ai所指子树上各结点的一切关键字均大于Ki，而小于Ki+1。A0所指子树上各结点的一切关键字均小于K1，An所指子树上各结点的一切关键字均大于Kn。对于叶结点，所有指针Ai皆为空。对于具有n个关键字的非叶结点，将有n+1棵子树。 当n=3时，每个结点中最多包含两个关键字、三个指针，最少时可以只含有一个关键字、两个指针，所以3阶B-树又称为2-3树。下图所示的是一棵5阶（m=5）B-树图7.32一棵5阶B-树B-树中元素的查找

B-树的结构保证了它是比较平衡的，限制了每个结点的子树都不能过少，且从根到叶的路径长度都相同，这对于提高查找效率显然是有利的。具体的查找方法与在二叉排序树中的查找方法类似。例如，在图7.32所示的5阶B-树上查找关键字n的过程是：首先从根开始，由于e<n<p，则应在位于e和p中间的指针所指的子树上进行查找；然后，又由于l<n，则应在l右边的指针所指的子树上进行查找；最后在含有m、n和o三个关键字的叶结点上查找成功。在m阶B-树上进行查找，其比较次数与两个因素有关：结点中关键字的数目（最多m-1个，由于它们是有序的，当m较大时可以用折半查找方法）树的深度现在假设共有N个关键字，且m是已确定的。可以证明，含N个关键字的m阶B-树的最大深度为:

B-树中元素的插入

若要在m阶B-树上插入一个关键字，其寻找插入位置的过程与查找失败的过程相同，待到在某个叶结点上找到相应的空指针后，不能像二叉排序树那样向下“伸出”一个新的叶结点，而要将待插入的关键字按次序加到原来的叶结点中。若插入后该结点的关键字数目不超过m-1，则插入完成；否则需将这个结点“分裂”为两个叶结点，并让叶结点中中间位置的关键字提升到父结点中。如果因此而令父结点中关键字个数超限，则继续这个结点分裂及关键字提升过程。在B-树叶结点中插入关键字而不是新增加一个叶结点，是为了保证B-树中的所有叶结点都必须在同一层上。例：一棵5阶B-树的生成过程如下图所示。

对于一棵5阶B-树，每个结点中关键字个数最多为4个，最少为2个，相应地指针个数最多为5个，最少为3个。图请见下页图7.33在5阶B-树中插入关键字时的变化情况B-树中元素的删除

如果要删除的关键字不在叶结点中，与二叉排序树中删除度为2的结点类似，找其直接前趋或是直接后继来顶替它，然后再删除这个直接前趋或是直接后继，而这个关键字一定在叶结点中。因此我们只需讨论删除B-树中叶结点中的关键字就可以了。分两种情况处理。如果叶结点中含有的关键字个数多于最低限度，则直接删除之。如果叶结点中含有的关键字个数正好等于最低限度，从中删除一个关键字后，这个结点的关键字个数将少于最低限度，此时考察与其相邻的兄弟结点。如果叶结点是其父结点的第一个或是最后一个孩子结点，则它只有一个相邻的兄弟结点，否则会有两个相邻的兄弟结点。设叶结点为A，再分两种情况考虑：如果至少有一个兄弟结点（设为B）中含有的关键字个数多于最低限度，则可以从B结点中“借”过一个关键字来。假设该兄弟结点B位于左侧，则将B中最大的关键字移至A、B的父结点C中，C中指向A和B两个指针之间的关键字下移到A中。对于B位于A之右侧的情况与此类似，将B中最小关键字移至父结点C中，然后将C中相应的关键字下移到A中。与A相邻的兄弟结点中没有多余的关键字可以借过来，即A和其兄弟结点中的关键字个数都达到最低限度，此时需要进行结点的合并。设将与A进行合并的兄弟结点为B，将A、B合并为一个结点D，同时，父结点C中分别指向A、B的两个指针之间的关键字也下降到D中。C中关键字个数及指针个数同时减1。如果C中关键字个数也低于最低限度了，则再递归处理父结点的情况，考察C的兄弟，看是否能“借”关键字或是需要与其兄弟结点进行合并。如果每次都需要进行结点的合并，最终将根结点中的唯一一个关键字下降，则树高减1。例：在一棵5阶B-树中，依次删除多个关键字。删除过程如图7.34至7.37所示。图7.34从5阶B-树中删除关键字h、r图7.35从5阶B-树中删除关键字p图7.36从5阶B-树中删除关键字d图7.37从5阶B-树中删除关键字d后的结果7.4哈希表及其查找前面介绍的几种查找方法，无论是顺序查找、折半查找还是在树表上进行查找，它们的共同特点是：为了找到表中某个记录，都要对给定的关键字值进行一系列的比较，之后才能确定所找的记录在表中的位置。而且其比较次数与表中记录的个数n有关（O(n)或O(logn)）。现在我们要介绍的方法是和以前完全不同的另一类重要的查找方法，它是通过对记录的关键字值进行某种运算后，直接确定该记录在表中的位置。因此，这种方法的平均查找长度将与表中记录的个数无关，从而可以大大提高查找速度。7.4.1什么是哈希哈希

哈希一词来自英文单词hash的音译，根据这个单词的原意，哈希表也称为杂凑表或散列表。相应的技术称为哈希技术、杂凑技术或散列技术，其主要特点是从关键字的值直接对应到表中的地址。例：例7.8假设在某旅馆中建立一个旅客管理—查询系统，该旅馆拥有一座大楼（楼层足够高，楼的每层有足够多的房间）供旅客居住，且假设每套客房只住一名旅客。为了便于管理和查询，现以旅客姓名为关键字（设不超过三个汉字），以姓名的汉字笔划数作为关键字的值，来决定他（她）所住的房间号。例如下面就是一张旅客姓名和所住房间号的对照表。表7.1旅客房间表旅客姓名房间号丁

一201于

立305王

方404田小华536刘力文624李中元744┆┆其中，姓的笔划数决定楼层号，名字的笔划数决定本层的房间号。用这种方法无论是安排旅客住宿（造表）还是查询某旅客的居住房间，都是十分方便的。但是若有两个旅客姓氏笔划相同，就有一点问题。例如在表7.1中已住旅客的情况下，又来了一位名叫卞云的旅客，她的姓名编码也是404，可是404号房间已经住有旅客王方，不能再住第二个人了，这就叫发生“冲突”。这个问题怎么处理呢？当然处理的方法很多，最简单的办法是看下一个房间号405，若405号房间为空，则安排卞云住在该房间；若405号房间已住有旅客，则看406号房间是否为空，依此类推，直到找到一个空房间为止。在这种安排下，若要询问卞云的住处，首先也要到404号房间查看，若此房间住的旅客不是卞云，则查下一个房间，依此类推，肯定能找到卞云住的房间。通过把关键字值映射到表中的一个位置来访问记录的过程称为哈希，把关键字值映射到位置的函数称为哈希函数，通常用h来表示。存放记录的数组称为哈希表，用T来表示。哈希表中的一个位置称为一个槽。哈希表T中槽的数目用变量M来表示，槽从0到M-1编号。哈希方法使得对于任何关键字值K和某个哈希函数h，0≤h(K)≤M-1，得到：key(T(i))=K哈希方法概括如下： 对于某个问题可能出现的关键字，估计出它的总数，准备出略大于这一总数的空间（例如多出总数的20%—30%），以存放关键字。然后，设计一个哈希函数H，它将关键字k转换成一个整数L，即H(k)=L。对于任何关键字，这个整数L都应在所准备的空间地址（或表的位置）的范围之内。若有两个不同的关键字k1、k2，即k1≠k2，但H(k1)=H(k2)=L，这就叫发生“冲突”。因此，对于哈希技术，主要研究两个问题：如何设计哈希函数。发生冲突后如何解决。7.4.2哈希函数的构造方法构造哈希函数时通常考虑的因素有：计算哈希函数所需的时间关键字的长度哈希表的大小关键字的分布情况记录的查找频率构造哈希函数的基本原则是：算法简单，运算量小；均匀分布，减少冲突。几种常用的构造哈希函数的方法直接定址法 这是一种计算最简单、且冲突最少的方法，在某些适合的情况下应尽量采用。这种哈希函数是关键字值的线性函数，即H(k)=k或H(k)=a*k+b，其中a、b为常数。

例：设要统计某地区从1949年到2000年每年的出生人数，统计结果将列在一张表中，此时年份为关键字。因为共有2000-1949+1=52年，所以表中设有1至52个位置。如何将关键字值对应到表中位置呢？只需取H(k)=k-1948即可，其中k为年份数。这样的哈希表示意如下： 数据表完成后，若要查1949至2000之间任意年份M出生的人数，则在表的第M-1948个位置即可找到。12…52年份19491950…2000人数…………平方取中法 这是一种较常用的构造哈希函数的方法。设关键字值的位数超出了空间地址的范围，又不能简单地截取其中的某几位作为哈希函数值。为了能使关键字值的每一位都对计算的结果起作用，可以先将关键字值自乘，然后截取中间几位对应到空间地址。例7.9设有一组关键字ABC，BCD，CDE，DEF,……，其对应的机内代码分别为010203，020304，030405，040506，……，假定地址空间大小为103，编号为0~999。现在按平方取中法构造哈希函数，则可取关键字机内代码平方后的中间三位作为存储位置，计算过程如表7.2所列。关键字机内代码机内代码的平方数哈希地址ABCBCDCDEDEF┆010203020304030405040506┆0104101209041225241609244640251640739036┆101252464739┆折叠法 折叠法是另一类处理多位关键字的方法。当关键字的位数较多，远超过空间地址的范围时，可将关键字分割为位数相等的几段，然后将各段叠加，叠加后将最高位的进位舍去，所得结果即为哈希地址。例：关键字值k=123203241712，哈希表长度为1000

(0~999)，则将k分为三位一段，共分成四段然后相加，去掉进位1之后得到哈希地址为279。这种方法的原理也是尽可能让关键字的每一位都起作用，以达到使哈希函数值均匀分布的目的。同时采取几位折叠，又避免了最后哈希地址太大，超出哈希表范围。基数转换法 这种方法是将关键字值先看成另一种进制的数，然后转换成原来进制的数（例如十进制），再选其中的几位作为哈希地址。例如现有十进制的关键字值210485，把它看成十三进制的数后，再转换成十进制数，其过程是：21048513=2*135+1*134+0*133+4*132+8*13+5=77193210然后从中选几位作为哈希地址即可。通常要求两个基数互素，且新基数比原基数大。除留余数法 这是一种常用的方法，它是通过对关键字值进行取模运算得到的。设给出关键字值为k，哈希表长度为m，则设计哈希函数为：

H(k)=kmodp

其中p为小于m的某个正整数。显然，哈希函数值在哈希表的长度范围之内。关于p的取法是很有讲究的，理论分析和试验结果均证明，p应取小于表长m的最大素数，才能达到使哈希函数值均匀分布的目的。例如当m=1000时，p应取997这个素数。这时对某些关键字可得结果如表7.3所示。表7.3关键字机内代码（k）H(k)=kmod997KEYAEYBAKEYBKEYABCDDCBA1105250111052502011105250211052501020304040302017567578648733733277.4.3处理冲突的几种方法冲突

冲突就是不同的关键字对应到相同的哈希地址。给定一个哈希函数h和两个关键字k1、k2，如果h(k1)=b=h(k2)，其中b是表中的一个槽，那么我们就说k1和k2对于b在哈希函数h下有冲突。

若对于关键字集合中的任一个关键字，经哈希函数映射到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。解决冲突的方法

基本上分为两类：开放地址法（闭哈希法）

当发生冲突时，用某种方法形成一个探测下一地址的序列，沿着这个序列一个个地查找，直到找到一个空地址就将关键字所在的记录存入。链地址法（开哈希法）

当发生冲突时，就拉出一条链，建立一个单链表，将具有相同哈希函数值的关键字所在的记录依次存入这个链表中。下面分别介绍这两类方法的具体实现方法。开放地址法

在这一类解决冲突的方法中又分为三种确定探测序列的方式：线性探测再散列；二次探测再散列；伪随机数再散列。假设哈希表长度为m，编号为0～m-1，哈希函数为H(k)。用线性探测再散列法解决冲突，求下一地址的公式是：di+1=(di+j)modm(j=1,2,…,s)

其中d1=H(k)。这个方法的意思是从哈希地址

H(k)出发，以等距离j（j可取不同的值）依次

搜索，当到表尾时可以转到表头循环搜索，直

到找到空位置为止。用二次探测再散列法解决冲突，求下一地址的公式是：

d2i=(d1+i2)modm (i=1,2,…)d2i+1=(d1-i2)modm