数据结构-基于C语言的描述第2版课件 第8章 查找

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

查找是数据处理领域中使用最频繁且最重要的一种基本操作，几乎在任何一个计算机系统软件和应用软件中都会涉及到；当问题所包括的数据量相当大时，查找效率在一些实时查询系统中格外重要。第8章主要内容查找第章8《数据结构–基于C语言的描述》（第2版）-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第8章主要内容8.1

查找的基本概念8.2

静态查找表8.3

动态查找表8.4哈希表查找第章8《数据结构–基于C语言的描述》（第2版）-清华大学出版社8.1查找的基本概念

查找应用涉及到计算机及其诸多领域。例如，字典中查找某个字的读音和含义，编译器中对源程序中变量名的管理、数据库系统中的信息维护等。typedefstruct{ //查找记录类型ElemTypekey;//关键字项

InfoTypeotherinfo;//其他数据项}RedType;8.1查找的基本概念

●

查找表：由同一类型的记录构成的集合。对查找表经常进行的操作有：（1）查询某个“特定的”元素（或记录）是否在表中；（2）检索某个“特定的”元素（或记录）的各种属性；（3）在查找表中插入一个元素（或记录）；（4）在查找表中删除某个元素（或记录）。

●

查找分类：按查找目的可以分为静态查找和动态查找；按查找记录在内存或外存可以分为内查找和外查找。

（1）不涉及插入和删除操作的查找称为静态查找，查找失败时，只返回一个不成功标志，查找结果不改变查找表；

（2）涉及插入和删除操作的查找称为动态查找，查找失败时，需要将被查找记录插入到查找表中，查找结果可能会改变查找表。

●

关键字：记录中某个数据项的值，用它可标识一个记录。

●

查找：在查找表中找出满足给定条件的记录。

如果在查找表中找到了与给定值相匹配的记录，则称为查找成功；否则，称为查找失败。

●

查找结构：当查找作为主要操作时，为了提高查找效率，需要专门为查找操作设置数据结构。

查找结构主要有：静态查找表，动态查找表，哈希表。

●

平均查找长度：为了确定要查找的记录位置，与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。

对于含有n个记录的表，查找成功时的平均查找长度为：pi

是查找第i个记录的概率；如果不特别声明，则认为每个记录的查找概率相等，即p1=p2…=pn=1/n。ci

是找到表中第i个记录所需要的比较次数。

ci

与算法密切相关，决定于算法；pi

与算法无关，决定于具体应用。若pi

是已知的，则平均查找长度ASL只是问题规模n的函数。

查找不成功时的平均查找长度是查找失败对应的关键字的比较次数。

8.2静态查找表

静态查找表特点：表结构在查找之前已生成。静态查找可采用顺序查找、折半查找和分块查找技术。在表的组织方式中，静态查找表是最简单的一种。8.2.1静态查找表的类型定义ADTStaticSearchTable{Data：具有相同特性的数据元素集合。各个元素均含有类型相同、可唯一标识元素的关键字。

Relation：数据元素同属于一个集合。Operation：

Create(&ST,n)操作结果：构造一个含n个元素的静态查找表ST。Destroy(ST)初始条件：静态查找表ST已存在。操作结果：销毁静态查找表ST。Search(ST,k)初始条件：静态查找表ST已存在，k为和关键字类型相同的给定值。操作结果：若ST中存在其关键字等于k的元素，则函数值为该元素的值或在表中的位置，否则为“空”或“0”。Traverse(ST)初始条件：静态查找表ST已存在。操作结果：按某种次序输出静态查找表ST的每个元素。}ADTStaticSearchTable

抽象数据类型8.2静态查找表8.2.1静态查找表的类型定义

存储结构类型

静态查找表可以采用顺序表或线性链表表示，本节中只讨论它在顺序存储结构模块中的实现。设静态查找表采用顺序存储结构，其类型定义如下：typedefstruct{RedType *r; //基址，建表时按实际值分配，r[0]空int length; //表长}SSTable;8.2静态查找表8.2.2顺序表的查找

以顺序表表示的静态查找表，可以采用顺序查找技术。设计

从顺序表的一端向另一端逐个将关键字与给定值进行比较：

（1）如果相等，则查找成功，返回该记录在表中位置；

（2）如果未找到与给定值相等的关键字，则查找失败，返回0。例8-1

已知一个顺序表中记录关键字如下所示。采用顺序查找技术：当给定值k是24时，查找成功，返回3；当给定值k是64时，查找失败，返回0。8.2静态查找表

哨兵是待查值，放在查找方向“尽头”处（低或高下标处），免去在查找中每次比较后都要判断查找位置是否越界，节省时间，提高查找速度。8.2.2顺序表的查找8.2静态查找表算法8-1intSearch_Seq(SSTableST,ElemTypek){//在顺序表ST中顺序查找关键字等于k的记录；若找到则返回其在表中位置，否则返回0ST.r[0].key=k; //ST.r[0]为“哨兵”i=ST.length;while(ST.r[i].key!=k)--i;returni;}//Search_Seq8.2.2顺序表的查找

对于具有n个记录的顺序表，查找第i个记录：

●在查找失败时关键字的比较次数是n+1次。因此，顺序查找的时间复杂度为O(n)。

优点：算法简单且适应面广，且对表结构没有任何要求，无论是顺序表还是链表，无论记录是否按关键字有序，均可应用。8.2静态查找表

缺点：平均查找长度较大，当查找规模很多大时，查找效率较低。

●在查找成功时需要进行n-i+1次关键字的比较。如果设每个记录的查找概率相等，即pi=1/n（1≤i≤n），顺序查找的平均查找长度为：

分析8.2.3有序表的查找

以有序表表示的静态查找表，可以采用折半查找技术。

设有序表为递增有序。取表的中间记录作为比较对象：

（1）如果给定值与中间记录关键字相等，则查找成功，返回该记录在表中位置；

（2）如果给定值小于中间记录关键字，则在中间记录左半区查找；

（3）如果给定值大于中间记录关键字，则在中间记录右半区查找。

不断重复上述过程，直到查找成功；或者未找到与给定值相等的关键字，则查找失败，返回0。8.2静态查找表设计8.2.3有序表的查找例8-2

已知一个有序表中记录的关键字如下所示。采用折半查找技术：当给定值k是18时，查找成功，返回3。8.2静态查找表采用折半查找技术：8.2.3有序表的查找例8-2

已知一个有序表中记录的关键字如下所示。8.2静态查找表当给定值k是39时，查找失败，返回0。8.2.3有序表的查找8.2静态查找表intSearch_Bin(SSTableST,ElemTypek){//在有序表ST中折半查找关键字等于k的记录；//若找到则返回其在表中位置，否则返回0low=1;high=ST.length; //设置查找区间初值while(low<=high){mid=(low+high)/2;if(k==ST.r[mid].key)returnmid; //查找成功，返回记录在表中位置elseif(k<ST.r[mid].key)high=mid–1;elselow=mid+1;}return0; //查找失败，返回0}//Search_Bin算法8-28.2.3有序表的查找8.2静态查找表分析

折半查找过程可采用二叉树描述：11个记录折半查找过程的判定树（结点值是记录序号）

把当前查找区间中间位置上记录作为根，左子表和右子表中记录分别作为根的左子树和右子树。该二叉树称为描述折半查找的判定树或比较树。判定树不是完全二叉树，但其叶子所在层次之差最多为1，则n个结点的判定树深度和n个结点完全二叉树相同。折半查找判定树深度为

log2n

+1。在有序表(10,15,18,20,26,28,33,36,38,43,48)的判定树中，查找26找到有序表中任一记录的过程是走了一条从根到与该记录相应结点的路径，和给定值进行比较的关键字个数恰为该结点在判定树上的层次数。8.2.3有序表的查找

●在查找成功时：8.2静态查找表28182026分析在查找成功时，会找到树中某个结点，则成功时的平均查找长度：8.2.3有序表的查找

●在查找成功时：8.2静态查找表分析因此，折半查找方法在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个结点的判定树的深度为

log2n

+1。在有序表(10,15,18,20,26,28,33,36,38,43,48)加外部结点的判定树中，查找46

折半查找时查找不成功的过程是走了一条从根到外部结点的路径，和给定值进行比较的关键字个数等于路径上内部结点个数。8.2.3有序表的查找

●在查找失败时：8.2静态查找表28384343<46分析在判定树中所有结点空指针域上加一个指向外部结点指针。圆形结点为内部结点；方形结点为外部结点。在查找不成功时，会找到树中某个外部结点，则不成功时的平均查找长度：8.2.3有序表的查找

●在查找失败时：8.2静态查找表分析

因此，折半查找方法在查找不成功时和给定值进行比较的关键字个数最多也不超过

log2n

+1。8.2.3有序表的查找

●在查找失败时：8.2静态查找表

折半查找的时间复杂度为O(log2n)。

优点：与顺序查找相比，平均查找长度小且查找速度快。分析

缺点：只限于顺序有序表，不适于线性链表。

以索引顺序表表示的静态查找表，可以采用分块查找技术

。8.2.4索引顺序表的查找8.2静态查找表

按照表内记录的某种属性把表分成n（n>1）个块（子表），并从各块中抽取最大关键字构成一个“索引表”，索引表具有如下性质：

●每个元素对应一个块，包括块内最大关键字值和块中第一个记录位置；

●

后一个块中所有记录关键字值应比前一个块中所有记录关键字值大，且块内关键字值的大小可以无序。由于查找表分块有序，则索引表为有序表。索引表的类型定义typedefstruct{ElemType key; //块内最大关键字值

int stadr; //块中第一个记录位置}IndexItem;typedefstruct{IndexItem *elem; //索引数组基址，0号单元不用int length; //块数量}IndexTable;8.2.4索引顺序表的查找8.2静态查找表8.2.4索引顺序表的查找8.2静态查找表

（1）在索引表中进行折半查找或顺序查找，以确定待查记录“所在块”；然后在已限定的那一块中进行顺序查找；设计

（2）由索引项组成的索引表按关键字有序，所以确定块的查找可以采用顺序查找，也可以采用折半查找；

（3）块中的记录可以是任意排列的，所以在块内的查找只能采用顺序查找。故分块查找的算法即为顺序查找和折半查找的简单合成。8.2.4索引顺序表的查找8.2静态查找表例8-3

已知一个索引顺序表中记录的关键字如图所示，采用分块查找技术：

确定块：如果给定值k=50，则将k与索引表中各块最大关键字值进行比较，由于33<k<66，因此可以确定k在第2个块中；

确定块内范围：由于k所在块的“地址指针”指向块内第一个记录，即ST.r[6]，因此查找记录应该在表中ST.r[6]和ST.r[10]之间；

查找：给定的查找值k=ST.r[7].key，查找成功，返回7。

●

在索引表中进行折半查找或顺序查找，以确定待查记录“所在块”；●在已限定的那一块中进行顺序查找。8.2.4索引顺序表的查找8.2静态查找表例8-3

已知一个索引顺序表中记录的关键字如图所示，采用分块查找技术：

在实际应用中：（1）分块查找不一定要将线性表分成大小相等的若干块，可以根据表的特征进行分块；（2）每一块既可放在不同的顺序表中，也可存放在一个单链表中。8.2.4索引顺序表的查找8.2静态查找表intSearch_Idx(SStableST,IndexTableID,ElemTypek){//在索引顺序表ST中分块查找关键字等于k的记录；//若找到则返回其在表中位置，否则返回0low=1;high=ID.length; //设置查找块区间初值found=0; //查找块标志：为1找到，为0未找到算法8-3

while((low<=high)&&(!found)){ //折半查找索引表ID，确定查找块区间mid=(low+high)/2;if(k<ID.elem[mid].key)high=mid-1;elseif(k>ID.elem[mid].key)low=mid+1;else{ //找到查找块found=1;low=mid;

}

}

s=ID.elem[low].stadr; //下一步的查找范围定位在第low块8.2.4索引顺序表的查找8.2静态查找表if(high<ID.length)t=ID.elem[low+1].stadr–1;elset=ST.lengthif(ST.r[t].key==k)returnt; //找到待查记录，返回其在表中位置else{ //在ST.r[s..t]中进行顺序查找ST.r[0]=ST.r[t+1];ST.r[t+1].key=k;for(p=s;ST.r[p].key!=k;p++);ST.r[t+1]=ST.r[0];if(p!=(t+1))returnk;elsereturn0;}}//Search_Idx算法8-38.2.4索引顺序表的查找8.2静态查找表

分块查找是两次查找过程，整个查找过程平均查找长度是两次查找平均查找长度之和。将具有n个记录的索引顺序表分成b块，第1块至第b-1块的记录个数均为s=

n/b

，第b块的记录个数等于或小于s；如果表中每个记录的查找概率相等，则每个块的查找概率为1/b，块中每个记录的查找概率为1/s。

（1）如果以顺序查找来确定块，则分块查找成功时的平均查找长度为：

（2）如果以折半查找来确定块，则分块查找成功时的平均查找长度为：分析

优点：在表中插入或删除一个记录时，只要找到该记录所属块就可以只在该块内进行插入和删除运算。因为块内记录存放任意，所以插入或删除较容易，不需要移动大量记录。

缺点：增加一个辅助数组的存储空间和将初始表分块排序的运算。8.3动态查找表

动态查找表特点：表结构在查找过程中动态生成。静态查找表中折半查找效率最高，O(log2n)；但维护表有序性效率为O(n)。动态查找表以几种特殊二叉树作为表的组织形式，其存储结构采用二叉链表。二叉排序树和平衡二叉树、B-

树、B+

树，以及键树。8.3动态查找表8.3.1动态查找表的类型定义ADTDynamicSearchTable{Data：具有相同特性的数据元素的集合，各个元素均含有类型相同，可唯一标识元素关键字。

Relation：数据元素同属于一个集合。

Operation：

InitDSTable(&DT)操作结果：构造一个空动态查找表DT。…………SearchDSTable(DT,k)初始条件：动态查找表DT已存在，k为和关键字类型相同的给定值。操作结果：如果DT中存在其关键字等于k的元素，则函数值为该元素的值或在表中位置，否则为“空”。InsertDSTable(&DT,e)初始条件：动态查找表DT已存在，e为待插入的元素。操作结果：如果DT中不存在其关键字等于e.key的元素，则插入e到DT。…………}ADTDynamicSearchTable

抽象数据类型8.3动态查找表

二叉排序树又称二叉查找树，它或者是一棵空的二叉树，或者是具有下列性质的二叉树：

（1）如果其左子树不空，则左子树上所有结点的值均小于根的值；（2）如果其右子树不空，则右子树上所有结点的值均大于根的值；（3）其左右子树也都是二叉排序树。

二叉排序树是记录之间满足一定次序关系的二叉树，中序遍历二叉排序树可以得到一个按关键字有序的序列。

二叉排序树

设动态查找表采用二叉链表存储结构，其类型定义如下：typedefstructBSTNode{RedType data; //数据域

structBSTNode*lchild,*rchild; //左、右孩子指针域}BSTNode;

typedefBSTNode*BSTree;8.3.2二叉排序树和平衡二叉树●二叉排序树

设在二叉排序树中查找关键字等于k的记录结点。采用递归方式完成查找。递归模型如下：

在二叉排序树上进行查找，和折半查找类似，也是一个逐步缩小查找范围的过程。设计

●

基本项：当二叉排序树是空树时，查找失败，返回空指针；

当k等于根的关键字时，查找成功，返回该结点指针；

8.3动态查找表8.3.2二叉排序树和平衡二叉树●二叉排序树

二叉排序树的查找

●归纳项：当k小于根的关键字时，在其左子树中继续查找；否则在其右子树中继续查找。算法8-4BSTNode*SearchBST(BiTreeT,ElemTypek){//在二叉排序树T上查找关键字为k的结点：若成功则返回该结点指针；若失败则返回空指针

if(T==NULL)returnNULL;elseif(k==T->data.key)returnT;elseif(k<T->data.key)returnSearchBST(T->lchild,k);elsereturnSearchBST(T->rchild,k);}//SearchBST8.3动态查找表8.3.2二叉排序树和平衡二叉树●二叉排序树

二叉排序树的查找

设在二叉排序树中插入关键字等于k的记录结点指针为p。采用递归方式完成插入。递归模型如下：

二叉排序树插入98后的二叉排序树

●基本项：当p所指向结点关键字=根关键字时，给出相应信息；

当二叉树为空时，将p所指向结点作为根结点插入；

设计8.3动态查找表8.3.2二叉排序树和平衡二叉树●二叉排序树

二叉排序树的插入

●

归纳项：当p所指向结点关键字<根关键字时，将其插入到根左子树中；

当p所指向结点关键字≥根关键字时，将其插入到根右子树中。8.3动态查找表算法8-5voidInsertBST(BSTree&T,RedTyper){//若二叉排序树T中不存在关键字r.key的记录，则插入r；否则给出相应信息if(!(SearchBST(T,r.key))){

s=newBSTNode;s->data=r;s->lchild=NULL;s->rchild=NULL;

Insert(T,s);}}voidInsert(BSTree&T,BSTNode*p){//在二叉排序树T上插入p结点，

if(T==NULL)T=p;elseif(p->data.key<T->data.key)Insert(T->lchild,p);elseInsert(T->rchild,p);}//Insert●二叉排序树

二叉排序树的插入先序遍历的思想8.3.2二叉排序树和平衡二叉树

设n个待插记录放在数组r[n]中，依次取出每个记录r[i]，重复：（1）创建一个数据域为r[i]的结点，并令该结点的左右指针域均为空；（2）调用二叉排序树的插入算法，将该结点插入到二叉排序树中。设计例8-4设待插记录关键字序列为{63,90,70,55,67,42,98}，从空树开始构造二叉排序树。插入63插入90插入70插入55插入67插入42插入988.3动态查找表●二叉排序树

二叉排序树的构造（1）插入结点次序不同，所构造的二叉排序树形状就不同：（2）对应同一组待插记录，可以有不同的二叉排序树形式；（3）不同的二叉排序树可能具有不同深度，会直接影响查找效率。

8.3.2二叉排序树和平衡二叉树8.3动态查找表8.3.2二叉排序树和平衡二叉树算法8-6voidCreateBST(BSTree&T,RedTyper[],intn){//由n个待插记录组成的数组r[]构造二叉排序树Tfor(i=0;i<n;++i){

InsertBST(T,r[i]);

//参见算法8-5}}//CreateBST●二叉排序树

二叉排序树的构造8.3动态查找表

●

从二叉排序树中删除一个结点后要仍能保持二叉排序树性质；

●

当删除分支结点时会破坏二叉排序树中原有结点之间的链接关系，此时需要重新修改指针，使得删除结点后仍为一棵二叉排序树。●二叉排序树

二叉排序树的删除8.3.2二叉排序树和平衡二叉树8.3.2二叉排序树和平衡二叉树8.3动态查找表

设待删除结点为p，其双亲结点为f；令PL

和PR

分别表示p结点的左子树和右子树，删除有三种情况：

p结点为叶子，既没有左子树也没有右子树。p是f的左孩子p是f的右孩子●二叉排序树

二叉排序树的删除设计（1）如果p是f左孩子，则只需将p的双亲f的左指针域置空；（2）如果p是f右孩子，则只需将p的双亲f的右指针域置空。8.3.2二叉排序树和平衡二叉树8.3动态查找表

设待删除结点为p，其双亲结点为f；令PL

和PR

分别表示p结点的左子树和右子树，删除有三种情况：

p结点只有左子树PL

或右子树PR。

p是f的左孩子●二叉排序树

二叉排序树的删除设计（1）如果p是f左孩子，则只需将PL

或PR

直接成为其双亲f的左子树；8.3.2二叉排序树和平衡二叉树8.3动态查找表

设待删除结点为p，其双亲结点为f；令PL

和PR

分别表示p结点的左子树和右子树，删除有三种情况：

p结点只有左子树PL

或右子树PR。

p是f的右孩子●二叉排序树

二叉排序树的删除设计（1）如果p是f左孩子，则只需将PL

或PR

直接成为其双亲f的左子树；（2）如果p是f右孩子，则只需将PL

或PR

直接成为其双亲f的右子树。8.3.2二叉排序树和平衡二叉树设计●二叉排序树

二叉排序树的删除8.3动态查找表

设待删除结点为p，其双亲结点为f；令PL

和PR

分别表示p结点的左子树和右子树，删除有三种情况：

p结点的左子树PL

和右子树PR

均非空（假设p是f的左孩子）。特殊情况：p的右孩子是p的中序后继（1）将中序后继结点的数据复制到p结点中，相当于删去了p结点；p的中序后继将中序后继取代pQ（2）删除中序后继结点（相当于被删结点只有右子树，情况）。8.3.2二叉排序树和平衡二叉树设计●二叉排序树

二叉排序树的删除8.3动态查找表

设待删除结点为p，其双亲结点为f；令PL

和PR

分别表示p结点的左子树和右子树，删除有三种情况：

p结点的左子树PL

和右子树PR

均非空（假设p是f的左孩子）。一般情况：p的右子树中最左下面的结点是p的中序后继p的中序后继将中序后继取代p

当找到删除位置后，在二叉排序树中删除结点的操作的时间依赖与寻找被删除结点的中序后继的操作。（1）将中序后继结点的数据复制到p结点中，相当于删去了p结点；Q（2）删除中序后继结点（相当于被删结点只有右子树，情况）。8.3动态查找表8.3.2二叉排序树和平衡二叉树例8-5已知一个关键字序列为{19,14,22,01,66,21,83,27,56,13,10,50}。插入24后的二叉排序树删除22后的二叉排序树二叉排序树●二叉排序树

二叉排序树的删除（1）按照给定关键字输入次序建立二叉排序树；（2）插入关键字为24的记录结点；（3）删除关键字为22的记录结点。24算法8-7●二叉排序树

二叉排序树的删除voidDeleteBST(&T,ElemType,k){//若二叉排序树T中存在关键字等于k的记录，则删除该记录结点；否则给出相应信息

parent=NULL;p=T; //parent指向p双亲。初始值为空while(p){ //从根开始查找关键字为k的待删结点 if(k==p->data.key)break； //如果已找到，则跳出查找循环

parent=p；

if(k<p->data.key)p=p->lchild; elsep=p->rchild；

}if(!p)Error("关键字等于k的记录不存在！")elseDelete(T,p,parent);}//DeleteBSTvoidDelete(BSTree&T,BSTNode*p,BSTNode*f){//在二叉排序树T上删除p结点，f是p的双亲

if(!(p->lchild)&&!(p->rchild)){//对应情况①，叶结点 if(f->lchild==p)f->lchild=NULL; elsef->rchild=NULL; deletep;}elseif(!(p->rchild)){ //对应情况②-(a)，只有左子树 if(f->lchild==p)f->lchild=p->lchild; elsef->rchild=p->lchild; deletep;}elseif(!(p->lchild)){ //对应情况②-(b)，只有右子树 if(f->lchild==p)f->lchild=p->rchild; elsef->rchild=p->rchild; deletep;}else{ //对应情况③，左右子树均不空 fq=p;q=p->rchild; while(q->lchild!=NULL){ fq=q;q=q->lchild; } p->data=q->data; if(fq==p)fq->rchild=q->rchild; elsefq->lchild=q->rchild; deleteq;}}//Delete8.3动态查找表8.3.2二叉排序树和平衡二叉树8.3.2二叉排序树和平衡二叉树分析

●

在二叉排序树上进行查找时的平均查找长度和二叉树形态有关；●二叉排序树8.3动态查找表

在最好情况下，二叉排序树在生成过程中，树的形态比较匀称(称为平衡)，最终得到的是一棵形态与折半查找的判定树相似的二叉排序树，它的平均查找长度和log2n成正比。

在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得到的二叉排序树蜕化为一棵深度为n的歪斜树，它的平均查找长度和单链表上的顺序查找相同，均和n成正比。一般二叉排序树歪斜二叉排序树输入：45,24,53,12,37,100输入：12,24,37,45,53,100分析

●

在二叉排序树上进行查找时的平均查找长度和二叉树形态有关；●二叉排序树8.3动态查找表

●查找算法、插入算法和删除算法的平均时间复杂度均为O(log2n)。

（1）平均时间性能：均衡的二叉排序树和折半查找一样。平衡调整可得到形态均衡的二叉树

（2）维护表有序性：二叉排序树无需移动结点，只需修改指针即可完成插入，且其平均执行时间均为O(log2n)，因此更有效。而折半查找进行插入操作时，维护表有序性所花费的时间代价是O(n)。8.3.2二叉排序树和平衡二叉树

平衡二叉树是一棵形态均匀的二叉排序树，具有较高检索效率。通常只要二叉树深度为log2n，就可以看作是平衡的。8.3动态查找表●平衡二叉树

●

最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。

平衡二叉树(AVL)或是一棵空树，或是一棵具有下列性质二叉排序树：（1）根结点的左子树和右子树的深度最多相差1。（2）根结点的左子树和右子树也都是平衡二叉树。

●

结点的平衡因子：该结点的左子树深度与右子树深度之差。8.3.2二叉排序树和平衡二叉树

平衡二叉树上所有结点的平衡因子只可能是-1、0和1。因此只要二叉树上有一个结点的平衡因子绝对值大于1，该二叉树就不平衡。tyepdefstructBSTNode{ //将平衡因子考虑到AVL树结点结构中RedType data;int bf; //结点的平衡因子

structBSTNode *lchild,*rchild;}BSTNode;typedefBSTNode*BSTree;

8.3动态查找表●平衡二叉树

平衡二叉树(AVL)或是一棵空树，或是一棵具有下列性质二叉排序树：（1）根结点的左子树和右子树的深度最多相差1。（2）根结点的左子树和右子树也都是平衡二叉树。平衡二叉树非平衡二叉树结点的值为平衡因子8.3.2二叉排序树和平衡二叉树8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

在构造二叉排序树的过程中，每当插入一个结点：

（1）检查是否因插入而破坏了树的平衡性；

（2）如果是，则找出最小不平衡子树；

（3）在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。8.3.2二叉排序树和平衡二叉树8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。LL型平衡调整，又称单向右旋平衡处理。

插入前，平衡子树插入后，不平衡A和BR

发生冲突原则：旋转优先8.3.2二叉排序树和平衡二叉树调整：支撑点由A改为B，顺时针旋转平衡8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。RR型平衡调整，又称单向左旋平衡处理。插入前，平衡子树插入后，不平衡A和BL

发生冲突原则：旋转优先8.3.2二叉排序树和平衡二叉树调整：支撑点由A改为B，逆时针旋转平衡8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。LR型平衡调整，又称双向旋转（先左后右）平衡处理。

插入前，平衡子树插入后，不平衡08.3.2二叉排序树和平衡二叉树8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。LR型平衡调整，又称双向旋转（先左后右）平衡处理。

第一次调整A的左子树，逆时针旋转B和CL

发生冲突原则：旋转优先8.3.2二叉排序树和平衡二叉树8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。LR型平衡调整，又称双向旋转（先左后右）平衡处理。

A和CR

发生冲突原则：旋转优先第二次支撑点由A调整到C，顺时针旋转8.3.2二叉排序树和平衡二叉树平衡8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。RL型平衡旋转，又称双向旋转（先右后左）平衡处理。插入前，平衡子树插入后，不平衡8.3.2二叉排序树和平衡二叉树8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。RL型平衡旋转，又称双向旋转（先右后左）平衡处理。B和CR

发生冲突原则：旋转优先8.3.2二叉排序树和平衡二叉树第一次调整A的右子树，顺时针旋转8.3动态查找表●平衡二叉树

平衡二叉树的调整规律

一般情况下，设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整的规律归纳起来有以下4种情况。RL型平衡旋转，又称双向旋转（先右后左）平衡处理。A和CL

发生冲突原则：旋转优先8.3.2二叉排序树和平衡二叉树第二次支撑点由A调整到C，逆时针旋转平衡8.3动态查找表●平衡二叉树

平衡二叉树的调整规律例8-6设关键字集合为{20,35,40,15,30,25}，在一棵空的二叉排序树上构造一棵平衡二叉树。

插入20和35，平衡插入40，不平衡RR型调整：逆时针旋转，平衡插入15和30，平衡8.3.2二叉排序树和平衡二叉树8.3动态查找表●平衡二叉树

平衡二叉树的调整规律例8-6设关键字集合为{20,35,40,15,30,25}，在一棵空的二叉排序树上构造一棵平衡二叉树。

插入25，不平衡LR型调整：第一次逆时针旋转LR型调整：第二次顺时针旋转8.3.2二叉排序树和平衡二叉树平衡8.3动态查找表●平衡二叉树

平衡二叉树的旋转实现LL型平衡调整，又称单向右旋平衡处理。

voidR_Rotate(BSTree&p){//对以p为根结点的二叉排序树作单向右旋处理，处理后p指向新的树根结点lc=p->lchild; //令lc指向p的左子树根结点p->lchild=lc->rchild; //令lc的右子树为p的左子树lc->rchild=p; //令p为rc的右子树p=lc; //令p指向新的根结点}//R_Rotate算法8-88.3.2二叉排序树和平衡二叉树8.3动态查找表●平衡二叉树

平衡二叉树的旋转实现RR型平衡调整，又称单向左旋平衡处理。算法8-9voidL_Rotate(BSTree&p){//对以p为根结点的二叉排序树作单向左旋处理，处理后p指向新的树根结点rc=p->rchild; //令rc指向p的右子树根结点p->rchild=rc->lchild; //令rc的左子树为p的右子树rc->lchild=p; //令p为rc的左子树p=rc; //令p指向新的根结点}//L_Rotate8.3.2二叉排序树和平衡二叉树8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的旋转实现算法8-10LR型平衡调整，又称双向旋转（先左后右）平衡处理。

#define LH +1 //左高#define EH 0 //等高#define RH -1 //右高voidLeftBalance(BSTree&T){//对以T为根结点的二叉排序树作先左后右平衡旋转处理，处理后T指向新的树根结点

lc=T->lchild;switch(lc->bf){ //检查T左子树平衡度并作相应平衡处理caseLH: //新结点插在T左孩子左子树，作LL处理T->bf=lc->bf=EH;R_Rotate(T);break;caseRH: //新结点插在T左孩子右子树，作LR处理rd=lc->rchild; //令rd指向T左孩子的右子树根结点8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的旋转实现算法8-10LR型平衡调整，又称双向旋转（先左后右）平衡处理。

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;}rd->bf=EH;L_Rotate(T->lchild); //对T的左子树作RR处理

R_Rotate(T); //对T作LL处理

}}//LeftBalance8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的旋转实现RL型平衡旋转，又称双向旋转（先右后左）平衡处理。#define LH +1 //左高#define EH 0 //等高#define RH -1 //右高voidRightBalance(BSTree&T){//对以T为根结点的二叉排序树作先右后左平衡旋转处理，处理后T指向新的树根结点

rc=T->rchild;switch(rc->bf){ //检查T右子树平衡度，并作相应平衡处理caseRH: //新结点插在T右孩子右子树，作RR处理T->bf=rc->bf=EH;L_Rotate(T);break;caseLH: //新结点插在T右孩子左子树，作RL处理ld=rc->lchild; //令ld指向T右孩子的左子树根结点算法8-118.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的旋转实现RL型平衡旋转，又称双向旋转（先右后左）平衡处理。switch(ld->bf){ //修改T及右孩子的平衡因子

caseLH:T->bf=LH;rc->bf=EH;break;caseEH:T->bf=rc->bf=EH;break;caseRH:T->bf=EH;rc->bf=RH;break;}ld->bf=EH;R_Rotate(T->rchild); //对T的右子树作LL处理

L_Rotate(T); //对T作RR处理

}}//RightBalance算法8-11

若T的左子树BF为1，则做单向右旋平衡处理，且在右旋处理后将根结点和其右子树根结点的BF改为0，树的深度不变；

若T的左子树BF为-1，则做先左后右双向旋转平衡处理，且在旋转处理后修改根结点和其左右子树根结点的BF，树的深度不变。

（4）如果r.key大于T的根的关键字，且T的右子树中不存在关键字和r.key相等的结点，则插入纪录r的新结点在T的右子树上，并当插入后的右子树深度增1时，分别就不同情况处理之。与（3）中所述相对称。

8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的插入

（1）如果T为空，则插入纪录r的新结点作为T的根，树深度增1；

（2）如果r.key等于T的根的关键字，则不进行插入；

（3）如果r.key小于T的根的关键字，且T的左子树中不存在关键字和r.key相等的结点，则插入纪录r的新结点在T的左子树上，并当插入后的左子树深度增1时，分别处理：

●当T的根结点的BF为-1时，将根的BF改为0，T的深度不变；

●

当T的根结点的BF为0时，将根的BF改为1，T的深度增1；

●

当T的根的BF为1时，判断。设计8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的插入算法8-12#defineLH+1 //左高#defineEH0 //等高#defineRH-1 //右高intInsert_AVL(BSTree&T,RedTyper,int&taller){//若在AVL树T中不存在和r.key相等的记录结点，则插入新结点r，并返回1；否则返回0//若因为插入而使二叉排序树失去平衡，则作平衡旋转处理，taller为1或0反映T长高或否

if(!T){ //插入r；若树“长高”，则taller为1T=newBSTNode;T->data=r;T->lchild=T->rchild=NULL;T->bf=EH;taller=1;

}else{if(e.key==T->data.key) //若T存在和r.key相等结点，则不插入

{taller=0;return0;}8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的插入算法8-12if(r.key<T->data.key){ //继续在T左子树中搜索

if(!Insert_AVL(T->lchild,r,taller))return0;

if(taller) //已插入到T左子树中，且左子树“长高”

switch(T->bf){ //检查T的平衡度

caseLH:LeftBalance(T);taller=0;break;//插入前左子树比右子树高；作左平衡处理,树未增高caseEH: T->bf=LH;taller=1;break;//插入前左右子树等高；插入后左子树增高，树增高

caseRH: T->bf=EH;taller=0;break;//插入前右子树比左子树高；插入后左右子树等高，树未增高

}

}8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的插入算法8-12else{ //继续在T右子树中搜索if(!Insert_AVL(T->rchild,r,taller))return0;if(taller) //已插入到T右子树中，且右子树“长高”switch(T->bf){ //检查T的平衡度caseLH: T->bf=EH;taller=0;break;//插入前左子树比右子树高；插入后左右子树等高，树未增高caseEH: T->bf=LH;taller=1;break;//插入前左右子树等高；插入后右子树增高，树增高caseRH: RightBalance(T);taller=0;break;//插入前右子树比左子树高；作右平衡处理,树未增高}}}return1;}//Insert_AVL8.3动态查找表8.3.2二叉排序树和平衡二叉树●平衡二叉树

平衡二叉树的查找性能分析

（1）在AVL树上进行查找的过程与二叉排序树相同，在查找过程中，和关键宇进行比较的次数不超过树深度。（2）n个结点的AVL树的平均深度为log2n，因此，在AVL树上进行查找的时间复杂性为O(log2n)。

B-

树是一种平衡的多路查找树，它适合在磁盘等直接存取设备上组织动态的查找表，在文件系统中非常有用。

一棵m阶的B-

树，或为空树，或为满足下列特性的m叉树：（1）树中每个结点至多有m棵子树；（2）如果根不是叶结点，则至少有两棵子树；（3）除根之外的所有非终端结点至少有

m/2

棵子树；（4）所有非终端结点中包含信息(n,a0,k1,a1,k2,……,kn,an)。其中：ki(1≤i≤n)为记录关键字且ki＜ki+1(1≤i≤n)；ai(0≤i≤n)为指向子树根的指针且所指子树中结点关键字均小于ki+1，an所指子树中结点关键字均大于kn。n(

m/2

-1≤n≤m-1)为记录关键字个数（或n+l为子树个数）。（5）所有叶结点都出现在同一层次上，且不带信息（可看作是外部结点或查找失败结点，实际上这些结点并不存在，指向这些结点指针为空）。8.3动态查找表8.3.3B-树B+

树和键树●B-

树

B-

树的定义一棵4阶的B-

树●B-

树中的结点的规模一般是一个磁盘页，而结点中所包含的关键字及孩子的数目取决于磁盘页的大小。●

对于磁盘上一棵比较大的B-

树，通常每个结点所拥有的孩子数目（即结点的度数）m为50至2000不等。●选取较大的结点度数可以降低树的深度，以及减少查找任意关键字所需要的磁盘访问次数。●

通常根可以始终置于主存中，因此在这棵B-

树中查找任一关键字至多只需要二次访问外存。8.3动态查找表8.3.3B-树B+

树和键树●B-

树

B-

树的定义8.3动态查找表8.3.3B-树B+

树和键树●B-

树

B-

树的类型定义#define m3 //B-树的阶，暂设为3typedefstructBTNode{int keynum; //结点中关键字的个数，即结点大小

ElemType key[m+1]; //关键字数组，key[0]未用

structBTNode*parent; //指向双亲结点

StructBTNode*ptr[m+1]; //子树指针数组ptr[0..keynum]RedType *recptr[m+1]; //记录指针数组，recptr[0]未用}BTNode,*Btree;typedefBTNode*BTree；B-树查找结果的类型定义如下：typedefstruct{BTNode*pt;//指向找到的结点

int i; //在结点中关键字序号i

(1..m)int tag;

//查找成功时为1，否则为0}Result; 8.3动态查找表8.3.3B-树B+

树和键树●B-

树

B-

树的查找规律

在B-

树上进行查找的过程是一个顺指针查找结点，以及在结点的关键字中进行查找交叉进行的过程。

查找关键字42查找关键字238.3动态查找表8.3.3B-树B+

树和键树●B-

树

B-

树的查找规律算法8-13ResultSearchBTree(BtreeT,ElemTypek){//在m阶B-树上查找关键字k，返回结果(pt,i,tag)//若查找成功，则tag=1，pt->key[i]=k；否则tag=0，返回k的插入位置信息

p=T;q=NULL;found=0;i=0; //初始化while(p&&(!found)){ n=p->keynum; i=Search(p,k); //查找i，使p->key[i]<=k<p->key[i+1] if((i>0)&&(p->key[i]==k))found=1; else{q=p;p=p->ptr[i];}}if(found)return(p,i,1); //查找成功elsereturn(q,i,0); //查找失败，返回k的插入位置信息}//SearchBTree8.3动态查找表8.3.3B-树B+

树和键树●B-

树

B-

树的插入规律B-

树的生成从空树开始，逐个插入关键字。但由于B-

树结点中关键字个数必须大于等于

m/2

-1