第19讲平衡B-散列

1、 一、平衡二叉树的查找一、平衡二叉树的查找 二、散列查找二、散列查找难点难点平衡因子平衡因子BFBF（Balance Factor Balance Factor 平衡度）平衡度）：结点的平：结点的平衡度是结点的左子树的高度右子树的高度。衡度是结点的左子树的高度右子树的高度。平衡二叉树：平衡二叉树：每个结点的平衡因子都为每个结点的平衡因子都为 1 1、1 1、0 0 的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。的二叉树。注意：注意：完全二叉树必为平衡树，平衡树不一定是完全完全二叉树必为平衡树，平衡树不一定是完全二叉树。二叉树。5482

2、54821是平衡树是平衡树 非平衡树非平衡树在平衡树中，结点的平衡因子可以是在平衡树中，结点的平衡因子可以是1 1，0 0，-1-1。结点的平衡因子结点的平衡因子HL-HR在左图所示的平衡树中插入数据域为在左图所示的平衡树中插入数据域为2的结点。的结点。 插入之后仍应保持平衡二叉树的性质不变。插入之后仍应保持平衡二叉树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树平衡树141253928635360501718730+1+1-1-1-1000000002+1+1原平衡原平衡度为度为 0危机结点危机结点如何用最简单、最有效的办法保持如何用最

3、简单、最有效的办法保持平衡二叉树的性质不变？平衡二叉树的性质不变？00最小不平衡子树：最小不平衡子树：在平衡二叉树的构造过程中，在平衡二叉树的构造过程中，以距以距离离插入结点插入结点最近的、且平衡因子的绝对值大于最近的、且平衡因子的绝对值大于1的结的结点为点为根根的子树。的子树。 542814基本思想基本思想：在构造二叉排序树的过程中，每插入一个：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整性的前提下，调

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

5、 2. RR型型 3. LR型型 4. RL型型 左改组左改组（新插入结点出现在危机结点的左子树上（新插入结点出现在危机结点的左子树上进行的调整）进行的调整）的情况分析的情况分析：1、LL 情况：（情况：（LL：表示新插入结点在危机结点的：表示新插入结点在危机结点的 左子树左子树的的左子树左子树上上）AB+1h-10+2+1hh-1h-1LL 改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点改组前：高度为改组前：高度为 h + 1 中序序列：中序序列：ABBLBRAR改组后：高度为改组后：高度为 h + 1 中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后 平

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

7、BLARCCLCR改组后：改组后： 高度为高度为 h + 1 中序序列：中序序列：ABBLARCCLCRAAB+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：表示新插入结点在危机结点的：表示新插入结点在危机结点的 左子树左子树的的

8、右子树上右子树上） 情况情况B：2、LR 情况：（情况：（LR：表示新插入结点在危机结点的：表示新插入结点在危机结点的 左子树左子树的的右子树上右子树上） 情况情况C：AB+10+2-1LR 改组改组危机结点危机结点改组前：改组前： 高度为高度为 2 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 0,0,0CBC0ABCA新插入结点新插入结点ABC改组后：改组后： 高度为高度为 2 中序序列：中序序列：CB0A00 四种情况的区分：四种情况的区分： 如果如果 的平衡度为的平衡度为1 则为则为 LL型改组；型改组； 否则为否则为 LR型改组：若型改组：若 的平衡度为的平衡度为1

9、、1 、0 ；则分别为；则分别为 LRA、LRB、LRC型改组。型改组。BC右改组右改组（新插入结点出现在危机结点的右子树上（新插入结点出现在危机结点的右子树上进行的调整）进行的调整） 的情况分析：的情况分析：1、RR 情况：情况：（RR：表示新插入结点在危机结点的：表示新插入结点在危机结点的 右子树右子树的的右子树上右子树上） 处理图形和处理图形和 LL 镜象相似镜象相似2、RL 情况：情况：（RL：表示新插入结点在危机结点的：表示新插入结点在危机结点的 右子树右子树的的左子树上左子树上） A、处理图形和、处理图形和 LRA 镜象相似镜象相似 B、处理图形和、处理图形和 LRB 镜象相似镜象

10、相似 C、处理图形和、处理图形和 LRC 镜象相似镜象相似5424258665842向右旋转一次先向右旋转再向左旋转实战：设有关键码序列实战：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树，构造平衡树LL型型RL型型426589642895向左旋转一次继续插入关键字继续插入关键字 9RR型型在平衡树上查找过程中和给定值进行比较的在平衡树上查找过程中和给定值进行比较的关键字个数不超过树的深度。关键字个数不超过树的深度。 O(logn)二叉平衡树的删除操作和插入操作类似。略二叉平衡树的删除操作和插入操作类似。略顺序查找、折半查找、二叉排序树查找等。顺序查找、折半查找、二叉排序树查找等。

11、这些查找技术都是通过一系列的给定值与关键码的比这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。码的比较次数。查找操作要完成什么任务？查找操作要完成什么任务？待查值待查值k k确定确定k k在存储结构中的位置在存储结构中的位置我们学过哪些查找技术？这些查找技术的共性？我们学过哪些查找技术？这些查找技术的共性？在存储位置和关键码之间建立一个确定的对应关系在存储位置和关键码之间建立一个确定的对应关系能否不用比较，通过关键码直接确定存储位置？能否不用比较，通过关键码直接确定存储位置？散列的基本思想：

12、散列的基本思想：在记录的存储地址和它的关键在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。比较，一次读取就能得到所查元素的查找方法。关关键键码码集集合合ki riH( (ki) )H散列表：散列表：采用散列技术将记录存储在一块连续的采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。存储空间中，这块连续的存储空间称为散列表。关关键键码码集集合合ki riH( (ki) )H散列表散列表数组数组散列函数：散列函数：将关键码映射为散列表中适当存储位置将关键码映射为散列表中

13、适当存储位置的函数。的函数。散列表散列表关关键键码码集集合合ki riH( (ki) )H散列函数散列函数数组数组散列地址：散列地址：由散列函数所得的存储位置址由散列函数所得的存储位置址 。散列表散列表关关键键码码集集合合ki riH( (ki) )H散列函数散列函数散列地址散列地址下标下标数组数组散列技术仅仅是一种查找技术吗？散列技术仅仅是一种查找技术吗？散列既是一种查找技术，也是一种存储技术。散列既是一种查找技术，也是一种存储技术。散列只是通过记录的关键码定位该记录，没有完整地表达散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是记录之间的逻辑关系，所以

14、，散列主要是面向查找面向查找的存储的存储结构。结构。散列是一种散列是一种完整的存储结构完整的存储结构吗？吗？散列技术一般不适用于允许多个记录有同样关键码的情散列技术一般不适用于允许多个记录有同样关键码的情况。散列方法也不适用于范围查找，换言之，在散列表况。散列方法也不适用于范围查找，换言之，在散列表中，我们不可能找到最大或最小关键码的记录，也不可中，我们不可能找到最大或最小关键码的记录，也不可能找到在某一范围内的记录。能找到在某一范围内的记录。散列技术最适合回答的问题是：散列技术最适合回答的问题是：如果有的话，哪个记录如果有的话，哪个记录的关键码等于待查值的关键码等于待查值。 散列技术适合于哪

15、种类型的查找？散列技术适合于哪种类型的查找？散列技术的关键问题：散列技术的关键问题： 散列函数的设计。如何设计一个简单、均匀散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。、存储利用率高的散列函数。 冲突的处理。如何采取合适的处理冲突方法冲突的处理。如何采取合适的处理冲突方法来解决冲突。来解决冲突。冲突：冲突：对于两个不同关键码对于两个不同关键码kikj，有有H(ki)H(kj)，即两个不同的记录需要存放在同，即两个不同的记录需要存放在同一个存储位置，一个存储位置，ki和和kj相对于相对于H称做称做同义词同义词。 关关键键码码集集合合ki riH(ki)kjH(kj)设计散列函

16、数一般应遵循以下原则：设计散列函数一般应遵循以下原则： 计算计算简单简单。散列函数不应该有很大的计算量，否。散列函数不应该有很大的计算量，否则会降低查找效率。则会降低查找效率。 函数值即散列地址分布函数值即散列地址分布均匀均匀。函数值要尽量均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。用并减少冲突。散列函数散列函数0101、直接定址法直接定址法散列函数是关键码的线性函数散列函数是关键码的线性函数，即：即：H(key) = a key + b （a，b为常数）为常数）例：关键码集合为例：关键码集合为10, 30, 50

17、, 70, 80, 90，选取的散列函，选取的散列函数为数为H( (key) )=key/10，则散列表则散列表为：为： 0 1 2 3 4 5 6 7 8 9103050708090适用情况？适用情况？事先知道关键码，且个数等于地址集合大小。事先知道关键码，且个数等于地址集合大小。 根据关键码在各个位上的分布情况，选取分布比较根据关键码在各个位上的分布情况，选取分布比较均匀均匀的若干位组的若干位组成散列地址。成散列地址。 例：关键码为例：关键码为8位十进制数，散列地址为位十进制数，散列地址为2位十进制数位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7

18、4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 散列函数散列函数0202、数字分析法、数字分析法适用情况适用情况:能预先估计出全部关键码的每一位上各种数能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新字出现的频度，不同的关键码集合需要重新分析。分析。散列函数散列函数0202、数字分析法、数字分析法将关键码从左到右分割成位数相等的几部分，将这几将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。部分叠加求和，取后几位作为散列地址。 散列函数散列函数0303、折叠法、折叠法例：设关键码为例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。，散列地址为三位。 2 5 3 4 6 3 5 8 7 + 0 5