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

1、主讲教师：章 英数据结构与算法 2第19讲 动态查找（2）本讲知识点：本讲知识点： (1)掌握平衡二叉树的相关基础知识掌握平衡二叉树的相关基础知识 (2)了解了解B树的简单操作树的简单操作 (3)了解了解B+树的简单操作树的简单操作难点：难点：平衡二叉树平衡二叉树3二叉排序树回顾创建、插入、删除三种操作10318287124谷歌工程师秀强悍搜索技术谷歌工程师秀强悍搜索技术引子5知识延伸云计算云计算框计算框计算强调后台资源的整合，为客户提供低强调后台资源的整合，为客户提供低成本的成本的ITIT基础设施的配置基础设施的配置强调前端用户需求的研究和响应，强调前端用户需求的研究和响应，为用户提供一站式

2、的互联网服务为用户提供一站式的互联网服务听起来让人觉得听起来让人觉得开心的开心的MP3MP3华中农大饭菜可华中农大饭菜可口又便宜的食堂口又便宜的食堂现在是否是向老现在是否是向老板提出加薪的最板提出加薪的最好时机好时机6n 查找的基本概念查找的基本概念n 查找分类查找分类n 穿插进行实例研究穿插进行实例研究查查找找n 静态表的查找静态表的查找n 动态查找表动态查找表n 哈希表哈希表顺序查找顺序查找有序表的查找有序表的查找二叉排序树二叉排序树二叉平衡树二叉平衡树B B树树B+B+树树查找知识体系结构7AVL树树 Balanced Binary Tree一、平衡二叉树一、平衡二叉树平衡因子平衡因子B

3、F（Balance Factor 平衡度）平衡度）：结点：结点的平衡度是结点的左子树的高度右子树的高度。的平衡度是结点的左子树的高度右子树的高度。平衡二叉树：平衡二叉树：每个结点的平衡因子都为每个结点的平衡因子都为 1、1、0 的二叉树。或者说每个结点的左右子树的高的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。度最多差一的二叉树。注意：注意：完全二叉树必为平衡树，平衡树不一定完全二叉树必为平衡树，平衡树不一定是完全二叉树。是完全二叉树。8548254821是平衡树是平衡树 非平衡树非平衡树在平衡树中，结点的平衡因子可以是在平衡树中，结点的平衡因子可以是1，0，-1。结点的平衡因子结

4、点的平衡因子HL-HR一、平衡二叉树一、平衡二叉树9在左图所示的平衡树中插入数据域为在左图所示的平衡树中插入数据域为2的结点。的结点。 插入之后仍应保持平衡二叉树的性质不变。插入之后仍应保持平衡二叉树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树平衡树141253928635360501718730+1+1-1-1-1000000002+1+1原平衡原平衡度为度为 0危机结点危机结点如何用最简单、最有效的办法保持如何用最简单、最有效的办法保持平衡二叉树的性质不变？平衡二叉树的性质不变？10最小不平衡子树：最小不平衡子树：在平衡二叉树的构造

5、过程中，以距在平衡二叉树的构造过程中，以距离离插入结点插入结点最近的、且平衡因子的绝对值大于最近的、且平衡因子的绝对值大于1 1的结的结点为点为根根的子树。的子树。 542814一、平衡二叉树一、平衡二叉树11基本思想：基本思想：在构造二叉排序树的过程中，每插入在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整二叉排序树特性的前提下，调整最小不平衡子树最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使中各结点之间

6、的链接关系，进行相应的旋转，使之成为新的平衡子树。之成为新的平衡子树。AVL树的构造树的构造12例：设序列例：设序列20，35，40，15，30，25 ，构造平衡树。构造平衡树。203540352040153015AVL树的构造树的构造13352040153025202515354030354030202515AVL树的构造树的构造例：设序列例：设序列20，35，40，15，30，25 ，构造平衡树。构造平衡树。14设结点设结点A为为最小不平衡子树最小不平衡子树的根结点，对该子树进行的根结点，对该子树进行平衡调整归纳起来有以下四种情况：平衡调整归纳起来有以下四种情况： 1. LL型型 2. R

7、R型型 3. LR型型 4. RL型型平衡化旋转有两类：平衡化旋转有两类： 单旋转单旋转 (左旋和右旋左旋和右旋) 双旋转双旋转 (左旋加右旋和右旋加左旋左旋加右旋和右旋加左旋)AVL树的平衡调整树的平衡调整15 左改组左改组（新插入结点出现在危机结点的左子树上（新插入结点出现在危机结点的左子树上进行的调整）进行的调整）的情况分析的情况分析：1、LL 情况：（情况：（LL：表示新插入结点在危机结点的表示新插入结点在危机结点的 左子树左子树的的左子树上左子树上）AB+1h-10+2+1hh-1h-1LL 改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点改组前：高度为改组前：

8、高度为 h + 1 中序序列：中序序列：ABBLBRAR改组后：高度为改组后：高度为 h + 1 中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后 平衡度为平衡度为 0AB16旋转：扁担原理；冲突：旋转优先旋转：扁担原理；冲突：旋转优先61层层2层层例例:LL型型 单右旋转平衡处理单右旋转平衡处理 108791291012876172、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的 左子树左子树的的右子树上右子树上） 情况情况A：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点改组前：改组前： 高度为高度为 h + 1 中序序列

9、：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改组后：改组后： 高度为高度为 h + 1 中序序列：中序序列：ABBLARCCLCRA18AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点改组前：改组前： 高度为高度为 h + 1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 +1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACLh-1CRh-2+10ABBLARCCRCL改组后：改组后： 高度为

10、高度为 h + 1 中序序列：中序序列：AABBLARCCRCL2、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的 左子树左子树的的右子树上右子树上） 情况情况B：192、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的 左子树左子树的的右子树上右子树上） 情况情况C：AB+10+2-1LR 改组改组危机结点危机结点改组前：改组前： 高度为高度为 2 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 0,0,0CBC0ABCA新插入结点新插入结点ABC改组后：改组后： 高度为高度为 2 中序序列：中序序列：CB0A

11、00 四种情况的区分：四种情况的区分： 如果如果 的平衡度为的平衡度为1 则为则为 LL型改组；型改组； 否则为否则为 LR型改组：若型改组：若 的平衡度为的平衡度为1、1 、0 ；则分别为；则分别为 LRA、LRB、LRC型改组。型改组。BC20804080206010305070859545例例:LR型型 先左旋再右旋平衡处理先左旋再右旋平衡处理 P264 218040802060103050708595452280408020601030507085954523右改组右改组（新插入结点出现在危机结点的右子树上（新插入结点出现在危机结点的右子树上进行的调整）进行的调整） 的情况分析：的情况

12、分析：1、RR 情况：情况：（RR：表示新插入结点在危机结点的表示新插入结点在危机结点的 右子树右子树的的右子树上右子树上） 处理图形和处理图形和 LL 镜象相似镜象相似2、RL 情况：情况：（RL：表示新插入结点在危机结点的表示新插入结点在危机结点的 右子树右子树的的左子树上左子树上） A、处理图形和处理图形和 LRA 镜象相似镜象相似 B、处理图形和处理图形和 LRB 镜象相似镜象相似 C、处理图形和处理图形和 LRC 镜象相似镜象相似245424258665842向右旋转一次先向右旋转再向左旋转设有关键码序列设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树，构造平衡树LL型型R

13、L型型实战实战25426589642895向左旋转一次继续插入关键字继续插入关键字 9RR型型26在平衡树上查找过程中和给定值进行比较的在平衡树上查找过程中和给定值进行比较的关键字个数不超过树的深度。关键字个数不超过树的深度。时间复杂度：时间复杂度： O(logn)性能分析性能分析27 内查找内查找前面介绍的查找方法，均适用于前面介绍的查找方法，均适用于查找存储在内存中的数据，统称为内查找方查找存储在内存中的数据，统称为内查找方法，它们适用于较小的表，而对较大的、存法，它们适用于较小的表，而对较大的、存储在外存储器上的文件就不合适了。储在外存储器上的文件就不合适了。 B树树是一种是一种多路平衡

14、多路平衡查找树，这是一种适用查找树，这是一种适用于于外查找外查找的方法的数据结构。的方法的数据结构。二、二、B树树28 B树的定义：树的定义：一棵一棵m阶的阶的B树，或者为空树，树，或者为空树，或者是满足如下条件的或者是满足如下条件的m叉树：叉树： （1）树中每个结点至多有）树中每个结点至多有m棵子树；棵子树； （2）若根结点不是叶子结点，则至少有）若根结点不是叶子结点，则至少有2棵棵子树；子树； （3）除根之外的所有非终端结点至少有）除根之外的所有非终端结点至少有m/2棵子树；棵子树； 即每个非根结点至少应有即每个非根结点至少应有m/2-1个关键字，个关键字，至多有至多有m-1个关键字。个关

15、键字。 二、二、B树树29 B树的定义：树的定义： （4）所有的非终端结点至少包含以下数据项：）所有的非终端结点至少包含以下数据项： （n,A0,K1,A1,K2,Kn,An），），其中，其中，n为关为关键字总数，键字总数，Ki（1in）是关键字，是关键字，Ai是指向子树根是指向子树根结点的指针。关键字是递增有序的：结点的指针。关键字是递增有序的：K1K2Kn，且且Ai(0in)所指子树中所有结点的关键字均小于所指子树中所有结点的关键字均小于Ki+1，An所指子树中所有结点的关键字均大于所指子树中所有结点的关键字均大于Kn。 （5）所有的叶子结点都在同一层上，并且不带）所有的叶子结点都在同一层

16、上，并且不带信息信息（可以看作是外部结点或查找失败的结点，实际上（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。这些结点不存在，指向这些结点的指针为空）。二、二、B树树30 nA0K1A1KnAnn+1n+1个分支个分支135118111127139347536419924378例如：一棵例如：一棵4阶的阶的B树树最多最多4棵子树，则最多棵子树，则最多3个关键字个关键字31 在在B树上进行查找的过程是一个顺指针查找结树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找，交叉进行的过点和在结点的关键字中进行查找，交叉进行的过程。程。 （1）在）在

17、B树中找结点；树中找结点； （2）在结点中找关键字。）在结点中找关键字。B树的查找树的查找32 要查找关键字要查找关键字k的记录，首先从根结点开始，的记录，首先从根结点开始，若找到则找所对应的记录，否则沿若找到则找所对应的记录，否则沿P所指的子所指的子树继续查找，其中树继续查找，其中 P0 K Kn Pi Ki K Min,只需直接删除即可。只需直接删除即可。 2、keynum=Min, 且所在结点的左或右兄弟结点且所在结点的左或右兄弟结点keynumMin 3、keynum=Min,且所在结点左右兄弟结点且所在结点左右兄弟结点keynum=MinB树的删除树的删除36jc fm ra bd

18、eg h ik ln ps t u x例如：删除例如：删除5阶阶B树的树的h、r、p、d结点。结点。第第1步：步：h-keynumMin,只需直接删除即可。只需直接删除即可。g i37jc fm ra bd eg ik ln ps t u x第第2步：步： r-keynum=Min，且，且r所在结点非所在结点非叶子结点，叶子结点，s移动到移动到r的位置的位置mt u xm s例如：删除例如：删除5阶阶B树的树的h、r、p、d结点。结点。38jc fm sa bd eg ik ln pt u xp-keynum=Min，且，且p所在结点的右兄弟结点所在结点的右兄弟结点keynumMin，s下移动

19、，下移动，t上移上移第第3步：步：n sm tu x例如：删除例如：删除5阶阶B树的树的h、r、p、d结点。结点。39jc fm ta bd eg ik ln su xd-keynum=Min，且删除后，且删除后，d所在结点及其所在结点及其左右兄弟结点均无多余结点。左右兄弟结点均无多余结点。第第4步：步：e例如：删除例如：删除5阶阶B树的树的h、r、p、d结点。结点。40jfm ta b c eg ik ln su xf j m tg ik ln su xa b c e例如：删除例如：删除5阶阶B树的树的h、r、p、d结点。结点。41 含有含有8个关键字的个关键字的3阶阶B树，最多有几个结树，

20、最多有几个结点，最少有几个结点？画出其形态。点，最少有几个结点？画出其形态。* * * * * *实战实战42 长度为长度为12的表的表Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，按此顺序建立一棵，按此顺序建立一棵3阶阶B树，画出其形树，画出其形态。态。JanMay NovAugMar OctAprDec FebJul JunSep实战实战43 B树的查找时间主要花费在搜索结点（访问外存）树的查找时间主要花费在搜索结点（访问外存）上，即主要取决于上，即主要取决于B树的深度树的深度问：含问：含N个关键字的个关键字的m阶阶B树的深度树的深度H为多

21、少？为多少？先推导每一层所含最少结点数：先推导每一层所含最少结点数：第第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+12( m/2 )H-1 则则 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1所以，在含所以，在含N个关键字的个关键字的B树上进行一次查找，树上进行一次查找，需访问的结点个数不超过需访问的结点个数不超过log m/2 (N+1)/2)+1性能分析性能分析45 B+树的定义：树的定义：B+树是应文件系统所需而出的树是应文件系统所需而出的一种一种B树的变型树。树的变型树。 一棵一棵m阶