数据结构与算法-查找(2)教材

1第19讲动态查找（2）本讲知识点：(1)掌握平衡二叉树的相关基础知识(2)了解B树的简单操作(3)了解B+树的简单操作难点：平衡二叉树2二叉排序树回顾创建、插入、删除三种操作10318287123谷歌工程师秀强悍搜索技术引子4知识延伸云计算框计算强调后台资源的整合，为客户提供低成本的IT基础设施的配置强调前端用户需求的研究和响应，为用户提供一站式的互联网服务听起来让人觉得开心的MP3华中农大饭菜可口又便宜的食堂现在是否是向老板提出加薪的最好时机5查找的基本概念查找分类穿插进行实例研究查找

静态表的查找

动态查找表

哈希表顺序查找有序表的查找二叉排序树二叉平衡树B树B+树查找知识体系结构6AVL树

BalancedBinaryTree一、平衡二叉树平衡因子BF（BalanceFactor平衡度）：结点的平衡度是结点的左子树的高度－右子树的高度。平衡二叉树：每个结点的平衡因子都为＋1、－1、0的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。注意：完全二叉树必为平衡树，平衡树不一定是完全二叉树。7548254821是平衡树非平衡树在平衡树中，结点的平衡因子可以是1，0，-1。结点的平衡因子＝HL-HR一、平衡二叉树8在左图所示的平衡树中插入数据域为2的结点。插入之后仍应保持平衡二叉树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度为0危机结点如何用最简单、最有效的办法保持平衡二叉树的性质不变？9最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。542814一、平衡二叉树10基本思想：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。AVL树的构造11例：设序列{20，35，40，15，30，25}，构造平衡树。203540352040153015AVL树的构造12352040153025202515354030354030202515AVL树的构造例：设序列{20，35，40，15，30，25}，构造平衡树。13设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：

1.LL型

2.RR型

3.LR型

4.RL型平衡化旋转有两类：

单旋转(左旋和右旋)

双旋转(左旋加右旋和右旋加左旋)AVL树的平衡调整14

左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：1、LL情况：（LL：表示新插入结点在危机结点的

左子树的左子树上）AB+1h-10+2+1hh-1h-1LL改组BLBRARBA0h0h-1h-1BLBRAR危机结点改组前：高度为h+1

中序序列：ABBLBRAR改组后：高度为h+1

中序序列：ABBLBRAR注意：改组后平衡度为0AB15旋转：扁担原理；冲突：旋转优先61层→2层例:LL型单右旋转平衡处理108791291012876162、LR情况：（LR：表示新插入结点在危机结点的

左子树的右子树上）情况A：AB+1h-10+2-1h-1LR改组BLAR危机结点改组前：高度为h+1

中序序列：注意：改组后平衡度为0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改组后：高度为h+1

中序序列：ABBLARCCLCRA17AB+1h-10+2-1h-1LR改组BLAR危机结点改组前：高度为h+1

中序序列：注意：改组后平衡度为+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACLh-1CRh-2+10ABBLARCCRCL改组后：高度为h+1

中序序列：AABBLARCCRCL2、LR情况：（LR：表示新插入结点在危机结点的

左子树的右子树上）情况B：182、LR情况：（LR：表示新插入结点在危机结点的

左子树的右子树上）情况C：AB+10+2-1LR改组危机结点改组前：高度为2中序序列：注意：改组后平衡度为0,0,0CBC0ABCA新插入结点ABC改组后：高度为2中序序列：CB0A00

四种情况的区分：

如果的平衡度为＋1则为LL型改组；

否则为LR型改组：若的平衡度为＋1、－1、0；则分别为LRA、LRB、LRC型改组。BC19804080206010305070859545例:LR型先左旋再右旋平衡处理P264208040802060103050708595452180408020601030507085954522右改组（新插入结点出现在危机结点的右子树上进行的调整）的情况分析：1、RR情况：（RR：表示新插入结点在危机结点的

右子树的右子树上） 处理图形和LL镜象相似2、RL情况：（RL：表示新插入结点在危机结点的

右子树的左子树上）

A、处理图形和LRA镜象相似

B、处理图形和LRB镜象相似

C、处理图形和LRC镜象相似235424258665842向右旋转一次先向右旋转再向左旋转设有关键码序列{5,4,2,8,6,9}，构造平衡树LL型RL型实战24426589642895向左旋转一次继续插入关键字9RR型25在平衡树上查找过程中和给定值进行比较的关键字个数不超过树的深度。时间复杂度：

O(logn)性能分析26内查找——前面介绍的查找方法，均适用于查找存储在内存中的数据，统称为内查找方法，它们适用于较小的表，而对较大的、存储在外存储器上的文件就不合适了。B树是一种多路平衡查找树，这是一种适用于外查找的方法的数据结构。二、B树27B树的定义：一棵m阶的B树，或者为空树，或者是满足如下条件的m叉树：（1）树中每个结点至多有m棵子树；（2）若根结点不是叶子结点，则至少有2棵子树；（3）除根之外的所有非终端结点至少有[m/2]棵子树；即每个非根结点至少应有[m/2]-1个关键字，至多有m-1个关键字。

二、B树28B树的定义：

（4）所有的非终端结点至少包含以下数据项：（n,A0,K1,A1,K2,……Kn,An），其中，n为关键字总数，Ki（1≤i≤n）是关键字，Ai是指向子树根结点的指针。关键字是递增有序的：K1<K2<……Kn，且Ai(0≤i≤n)所指子树中所有结点的关键字均小于Ki+1，An所指子树中所有结点的关键字均大于Kn。（5）所有的叶子结点都在同一层上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。二、B树29

nA0K1A1……KnAnn+1个分支135118111127139347536419924378例如：一棵4阶的B树最多4棵子树，则最多3个关键字30在B树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找，交叉进行的过程。（1）在B树中找结点；

（2）在结点中找关键字。B树的查找31要查找关键字k的记录，首先从根结点开始，若找到则找所对应的记录，否则沿P所指的子树继续查找，其中

P0K<K1P=PnK>KnPi

Ki

<K<Ki+1若直到叶子结点还未找到，则查找失败。B树的查找32设要插入关键值为k的记录，指向k所在记录的指针为p。首先找到k应插入的叶子结点，将k和p插入。然后，判断被插入结点是否满足m叉B树的定义，即插入后结点的分支数是否大于m（结点的关键字数是否大于m-1)，若不大于，则插入结束；否则，要把该结点分裂成两个。分裂方法：申请一个新结点，由指针p’指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也要分裂，则在分裂后再往上插入。B树的插入33452431237505390617095插入30

3730插入8585618570539070例如:一棵3阶B树34若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)K’取代K，然后从叶子中删去K’。在B树的叶子结点上删除关键字分三种情况讨论。1、keynum>Min,只需直接删除即可。2、keynum=Min,且所在结点的左或右兄弟结点keynum>Min3、keynum=Min,且所在结点左右兄弟结点keynum=MinB树的删除35jcfmrabdeghiklnpstux例如：删除5阶B树的h、r、p、d结点。第1步：h->keynum>Min,只需直接删除即可。gi36jcfmrabdegiklnpstux第2步：

r->keynum=Min，且r所在结点非叶子结点，s移动到r的位置mtuxms例如：删除5阶B树的h、r、p、d结点。37jcfmsabdegiklnptuxp->keynum=Min，且p所在结点的右兄弟结点keynum>Min，s下移动，t上移第3步：nsmtux例如：删除5阶B树的h、r、p、d结点。38jcfmtabdegiklnsuxd->keynum=Min，且删除后，d所在结点及其左右兄弟结点均无多余结点。第4步：e合并例如：删除5阶B树的h、r、p、d结点。39jfmtabcegiklnsux合并fjmtgiklnsuxabce例如：删除5阶B树的h、r、p、d结点。40含有8个关键字的3阶B树，最多有几个结点，最少有几个结点？画出其形态。***************

*实战41长度为12的表{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec}，按此顺序建立一棵3阶B树，画出其形态。JanMayNovAugMarOctAprDecFebJulJunSep实战42

B树的查找时间主要花费在搜索结点（访问外存）上，即主要取决于B树的深度问：含N个关键字的m阶B树的深度H为多少？先推导每一层所含最少结点数： 第1层1

第2层2

第3层2

m/2

第4层2(

m/2

)2

第H+1层2(

m/2

)H-1性能分析43假设m阶B树的深度为H+1，由于第H+1层为叶子结点