2,第19讲 动态查找（2）,本讲知识点：(1)掌握平衡二叉树的相关基础知识(2)了解B树的简单操作(3)了解B+树的简单操作难点：平衡二叉树,3,二叉排序树回顾,创建、插入、删除三种操作,4,谷歌工程师秀强悍搜索技术,引子,5,知识延伸,云计算,框计算,强调后台资源的整合，为客户提供低成本的IT基础设施的配置,强调前端用户需求的研究和响应，为用户提供一站式的互联网服务,听起来让人觉得开心的MP3,华中农大饭菜可口又便宜的食堂,现在是否是向老板提出加薪的最好时机,6,查找的基本概念查找分类穿插进行实例研究,查 找,静态表的查找动态查找表哈希表,,,顺序查找 有序表的查找,,,二叉排序树 二叉平衡树 B树 B+树,查找知识体系结构,7,AVL树 Balanced Binary Tree,一、平衡二叉树,平衡因子BF（Balance Factor 平衡度）：结点的平衡度是结点的左子树的高度－右子树的高度 平衡二叉树：每个结点的平衡因子都为 ＋1、－1、0 的二叉树或者说每个结点的左右子树的高度最多差一的二叉树 注意：完全二叉树必为平衡树，平衡树不一定是完全二叉树8,在平衡树中，结点的平衡因子可以是1，0，-1。
结点的平衡因子＝HL-HR,一、平衡二叉树,9,,,,,,,,,,在左图所示的平衡树中插入数据域为2的结点插入之后仍应保持平衡二叉树的性质不变14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,平衡树,,,,,,,,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,,,,,,,,原平衡度为 0,危机结点,如何用最简单、最有效的办法保持平衡二叉树的性质不变？,10,最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树4,一、平衡二叉树,11,基本思想：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树AVL树的构造,12,例：设序列{20，35，40，15，30，25} ，构造平衡树。
20,,,,,AVL树的构造,13,,,,,30,,,AVL树的构造,例：设序列{20，35，40，15，30，25} ，构造平衡树14,设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：1. LL型2. RR型3. LR型4. RL型,平衡化旋转有两类：单旋转 (左旋和右旋)双旋转 (左旋加右旋和右旋加左旋),AVL树的平衡调整,15,,,左改组（新插入结点出现在危机结点的左子树上 进行的调整）的情况分析： 1、LL 情况：（LL：表示新插入结点在危机结点的左子树的左子树上）,,,A,B,+1,h-1,0,,,+2,+1,,,h,,,h-1,,h-1,,,,,LL 改组,BL,BR,AR,,,B,A,0,h,0,,,,h-1,,h-1,BL,BR,AR,,,危机结点,改组前：高度为 h + 1中序序列：,A,B,,,BL,BR,AR,改组后：高度为 h + 1中序序列：,A,B,,,BL,BR,AR,注意：改组后 平衡度为 0,A,B,16,旋转：扁担原理；冲突：旋转优先,,1层→2层,例:LL型 单右旋转平衡处理,17,,,,,,,,,,2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上）情况A：,,A,B,+1,h-1,0,,+2,-1,,,,h-1,,,,LR 改组,BL,AR,,危机结点,改组前：高度为 h + 1中序序列：,注意：改组后 平衡度为 0,0,-1,C,B,C,,CL,CR,,h-2,h-2,,,h-1,,0,,+1,,,C,B,0,h-1,,,,h-1,BL,AR,A,,CR,,h-2,CL,,h-1,-1,0,,A,B,,BL,AR,C,,CL,CR,改组后：高度为 h + 1中序序列：,,A,B,,BL,AR,C,,CL,CR,A,18,,,,,,,,,,,A,B,+1,h-1,0,,+2,-1,,,,h-1,,,,LR 改组,BL,AR,,危机结点,改组前：高度为 h + 1中序序列：,注意：改组后 平衡度为 +1,0,0,C,B,C,,CR,CL,,h-1,h-2,,,h-2,,0,,-1,,,C,B,0,h-1,,,,h-1,BL,AR,A,,CL,,h-1,CR,,h-2,+1,0,,A,B,,BL,AR,C,,CR,CL,改组后：高度为 h + 1中序序列：,A,,A,B,,BL,AR,C,,CR,CL,2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上）情况B：,19,2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上）情况C：,,,,,,,,,,A,B,+1,0,,+2,-1,,,,LR 改组,,危机结点,改组前：高度为 2中序序列：,注意：改组后 平衡度为 0,0,0,C,B,C,0,,A,B,C,A,新插入结点,A,B,C,改组后：高度为 2中序序列：,,C,B,0,A,0,0,四种情况的区分：如果 的平衡度为＋1 则为 LL型改组；否则为 LR型改组：若 的平衡度为＋1、－1 、0 ；则分别为 LRA、LRB、LRC型改组。
B,C,20,,45,,例:LR型 先左旋再右旋平衡处理 P264,21,80,,,40,,80,,,20,,,60,,,10,30,50,70,85,95,,45,,,22,80,,,40,,80,,,20,,,60,,10,30,50,70,85,95,,45,,,,23,右改组（新插入结点出现在危机结点的右子树上 进行的调整） 的情况分析： 1、RR 情况：（RR：表示新插入结点在危机结点的右子树的右子树上）处理图形和 LL 镜象相似 2、RL 情况：（RL：表示新插入结点在危机结点的右子树的左子树上）A、处理图形和 LRA 镜象相似B、处理图形和 LRB 镜象相似C、处理图形和 LRC 镜象相似,24,5,4,2,,,,4,2,,5,,,,,8,,6,,,,6,5,,,8,4,2,,向右旋转 一次,先向右旋转 再向左旋转,,,设有关键码序列{5, 4, 2, 8, 6, 9}，构造平衡树,LL型,RL型,实战,25,4,2,,,,6,5,,,8,9,,6,4,2,,,,8,9,,,5,,,向左旋转一次,继续插入关键字 9,,RR型,26,在平衡树上查找过程中和给定值进行比较的关键字个数不超过树的深度。
时间复杂度： O(logn),性能分析,27,内查找——前面介绍的查找方法，均适用于查找存储在内存中的数据，统称为内查找方法，它们适用于较小的表，而对较大的、存储在外存储器上的文件就不合适了 B树是一种多路平衡查找树，这是一种适用于外查找的方法的数据结构二、B树,28,B树的定义：一棵m阶的B树，或者为空树，或者是满足如下条件的m叉树： （1）树中每个结点至多有m棵子树； （2）若根结点不是叶子结点，则至少有2棵子树； （3）除根之外的所有非终端结点至少有[m/2]棵子树；即每个非根结点至少应有[m/2]-1个关键字，至多有m-1个关键字二、B树,29,B树的定义： （4）所有的非终端结点至少包含以下数据项： （n,A0,K1,A1,K2,……Kn,An），其中，n为关键字总数，Ki（1≤i≤n）是关键字，Ai是指向子树根结点的指针关键字是递增有序的：K1
二、B树,30,,,,n+1个分支,,,,,,,,,例如：一棵4阶的B树,最多4棵子树，则最多3个关键字,31,在B树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找，交叉进行的过程1）在B树中找结点；（2）在结点中找关键字B树的查找,32,要查找关键字k的记录，首先从根结点开始，若找到则找所对应的记录，否则沿P所指的子树继续查找，其中P0 K KnPi Ki < K < Ki+1 若直到叶子结点还未找到，则查找失败B树的查找,33,设要插入关键值为k的记录，指向k所在记录的指针为p 首先找到k应插入的叶子结点，将 k和p插入然后，判断被插入结点是否满足m叉B树的定义，即插入后结点的分支数是否大于m（结点的关键字数是否大于m-1)，若不大于，则插入结束；否则，要把该结点分裂成两个 分裂方法：申请一个新结点，由指针p’指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也要分裂，则在分裂后再往上插入B树的插入,34,45,,,,24,3 12,37,50,53 90,61 70,95,,,,,,,,插入30,,37,插入85,,,61,85,,,,53,90,,例如: 一棵3阶B树,35,,若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)K’取代K，然后从叶子中删去K’。
在B树的叶子结点上删除关键字分三种情况讨论 1、keynum>Min,只需直接删除即可 2、keynum=Min, 且所在结点的左或右兄弟结点keynum>Min 3、keynum=Min,且所在结点左右兄弟结点keynum=Min,B树的删除,36,例如：删除5阶B树的h、r、p、d结点第1步：h->keynum>Min,只需直接删除即可g i,37,第2步： r->keynum=Min，且r所在结点非叶子结点，s移动到r的位置,m,t u x,m s,,例如：删除5阶B树的h、r、p、d结点38,p->keynum=Min，且p所在结点的右兄弟结点keynum>Min，s下移动，t上移,第3步：,n s,m t,u x,,,例如：删除5阶B树的h、r、p、d结点39,d->keynum=Min，且删除后，d所在结点及其左右兄弟结点均无多余结点第4步：,e,,合并,例如：删除5阶B树的h、r、p、d结点40,j,f,m t,a b c e,g i,k l,n s,u x,,,,,,,,,合并,,例如：删除5阶B树的h、r、p、d结点41,含有8个关键字的3阶B树，最多有几个结点，最少有几个结点？画出其形态。
实战,42,长度为12的表{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec}，按此顺序建立一棵3阶B树，画出其形态实战,43,B树的查找时间主要花费在搜索结点（访问外存）上，即主要取决于B树的深度问：含N个关键字的m阶B树的深度H为多少？ 先推导每一层所含最少结点数：第1层 1第2层 2第3层 2m/2第4层 2(m/2)2第H+1层 2(m/2)H-1,性能分析,44,假设m阶B树的深度为H+1，由于第H+1层为叶子结点，则有N+1个叶子结点，N+1≥2(m/2)H-1则 H-1≤logm/2((N+1)/2)H≤logm/2((N+1)/2)+1所以，在含N个关键字的B树上进行一次查找，需访问的结点个数不超过logm/2((N+1)/2)+1,。