《数据结构复习(8)》由会员分享，可在线阅读，更多相关《数据结构复习(8)（34页珍藏版）》请在金锄头文库上搜索。
1、数据结构复习（8）中国科学院研究生院第九章 查找n基本概念n静态查找表n顺序表的查找n有序表的查找n索引顺序表的查找n动态查找表n二叉排序树n平衡二叉树nB-树和B+树n哈希表（HASH）Wang Wenjie基本概念（1）n查找表：同类数据元素构成的集合。 包含：静态查找表：在表中查询某个元素或其属性 。动态查找表：在表中查询某个元素或其属性 ， 在表中插入、删除某个元素n主关键字，次关键字数据元素可能由多个数据项组成，其中能够 唯一识别该元素的数据项称主关键字；能识 别若干元素的称次关键字。Wang Wenjie基本概念（2）n查找：根据给定的值，在查找表中找到某个关键字的值等于 给定的值
2、的数据元素。查找成功：表中存在所要查找的元素。查找不成功：表中不存在所要查找的元素。n平均查找长度：在查找成功时，平均查找长度ASL是指为确定 数据元素在表中的位置所进行的关键码比较次数的期望值。 Pi为表中第i个数据元素的查找概率Ci为表中第i个数据元素的关键码与给定值相等时，按算法定位 时关键码的比较次数。 Wang Wenjie顺序表查找（1） n查找过程：从表中最后一个元素开始，逐个比较， 相等则比较成功，否则直到查找完所有的元素。n优点：对线性表的结点的逻辑次序无要求（不必按 关键码值排序），对线性表存储结构无要求（顺序 和链式都可以）n缺点：平均检索长度长，与表中结点个数成正比。W
3、ang Wenjie顺序表查找（2） n平均查找长度：就上述算法而言，对于n个数据元 素的表 ，Ci=n-i+1 n 设每个数据元素的查找概率相等 查找成功：pi = 1/n ci= 1,2,3n ASL=1/n1+2+n = (n+1)/2查找不成功：ASL = n+1 , (n, n-11, 0)Wang Wenjie有序表的查找（1） n有序表即是表中数据元素按关键码升序或降序排列 。 n折半查找的思想为：在有序表中，取中间元素作为 比较对象，若给定值与中间元素的关键码相等，则 查找成功；若给定值小于中间元素的关键码，则在 中间元素的左半区继续查找；若给定值大于中间元 素的关键码，则在中
4、间元素的右半区继续查找。不 断重复上述查找过程，直到查找成功，或所查找的 区域无数据元素，查找失败。 Wang Wenjie有序表的查找（2） 性能分析 ：n从折半查找过程看，以表的中点为比较对象，并以中点将表 分割为两个子表，对定位到的子表继续这种操作。所以，对 表中每个数据元素的查找过程，可用二叉树来描述，称这个 描述查找过程的二叉树为判定树。 n查找表中任一元素的过程，即是判定树中从根到该元素结点 路径上各结点关键码的比较次数，也即该元素结点在树中的 层次数。对于n个结点的判定树，树高为k，则有2k-1- 1n2k-1，即k-1log2(n+1)k，所以k= log2n+1。因此，折半查
5、找在查找成功时，所进 行的关键码比较次数至多为k= log2n+1 。Wang Wenjie有序表的查找（3） 平均查找长度(以树高为k的满二叉树(n=2k-1)为例 )：n假设表中每个元素的查找是等概率的，即 Pi=1/n ，则树的 第i层有2i-1个结点，因此，折半查找的平均查找长度为：ASL= 120+221+k2k-1= log2(n+1)-1log2(n+1)-1所以，折半查找的时间效率为O(log2n)。Wang Wenjie有序表的查找（4） 优点：平均检索长度小，粗略地说：每经过一次关键字比较， 则将查找范围缩小一半 缺点：排序花费时间Wang Wenjie索引顺序表查找(1)
6、n(表+索引表）也称为分块查找n分块查找要求将查找表分成若干个子表，并 对子表建立索引表，查找表的每一个子表由 索引表中的索引项确定。索引项包括两个字 段：n关键码字段：存放对应子表中的最大关键码值n指针字段：存放指向对应子表的指针 ， 并且要求索引项按关键码字段有序Wang Wenjie索引顺序表查找(2)n查找时，先用给定值kx在索引表中检测索引 项，以确定所要进行的查找在查找表中的查 找分块 (由于索引项按关键码字段有序，可 用顺序查找或折半查找) ，然后，再对该分 块进行顺序查找。 Wang Wenjie动态查找表 n二叉排序树n平衡二叉树nB-树和B+树Wang Wenjie二叉排序
7、树（1）二叉排序树定义n 二叉排序树（Binary Sort Tree）或者是一棵空树；或者 是具有下列性质的二叉树：n 若左子树不空，则左子树上所有结点的值均小于根结 点的值；若右子树不空，则 右子树上所有结点的值均大于 根结点的值。n 左右子树也都是二叉排序树。n二叉排序树实际上是将线性表中的结点信息组织成二叉树形 式，以达到与折半查找相同的检索效率，又具有链表那样的 插入、删除操作的灵活性Wang Wenjie二叉排序树（2）n在二叉排序树中查找n中序遍历可以得到关键字从小到大的有序序列n无序序列可以通过构造一棵二叉排序树而变成一个有序 序列，构造树的过程就是对无序序列进行排序的过程。n
8、 二叉排序树的构造229图9.8 其特点为每次插入都是在叶子上。最好情况： log2N最差情况： （N+1)/2平均查找长度与折半查找同数量级Wang Wenjie二叉排序树（3）n在二叉排序树的删除n n删除叶结点删除叶结点，只需将其双亲结点指向它的指针清零，再，只需将其双亲结点指向它的指针清零，再 释放它即可。释放它即可。n n被删结点缺右子树被删结点缺右子树，可以拿它的左子女结点顶替它的位，可以拿它的左子女结点顶替它的位 置，再释放它。置，再释放它。n n被删结点缺左子树被删结点缺左子树，可以拿它的右子女结点顶替它的位，可以拿它的右子女结点顶替它的位 置，再释放它。置，再释放它。n n被
9、删结点左、右子树都存在被删结点左、右子树都存在，可以在它的右子树中寻找，可以在它的右子树中寻找 中序下的第一个结点中序下的第一个结点( (关键码最小关键码最小),),用它的值填补到被删用它的值填补到被删 结点中，再来处理这个结点的删除问题。结点中，再来处理这个结点的删除问题。Wang Wenjie二叉排序树（4）Wang Wenjie二叉平衡树(AVL树)（1）n二叉排序树的结构不同，则查找效率就不一样，在最优的情 况下，删除或插入结点就会破坏其最右的结构。要保持高效 率的查找，可以采用平衡二叉树结构nAVL定义：平衡因子：右子树深度减去左子树深度为 1， 0 ， 1的二叉排序树。n n结点的
10、平衡因子结点的平衡因子n n每个结点附加一个数字，给出该结点右子树的高度减去左每个结点附加一个数字，给出该结点右子树的高度减去左 子树的高度所得的高度差。这个数字即为结点的平衡因子子树的高度所得的高度差。这个数字即为结点的平衡因子 balancebalance 。n n根据根据AVLAVL树的定义，任一结点的平衡因子只能取树的定义，任一结点的平衡因子只能取 -1-1，0 0和和 1 1 。Wang Wenjie二叉平衡树(AVL树)（2）n n如果一个结点的平衡因子的绝对值大于如果一个结点的平衡因子的绝对值大于1 1 ，则这棵二叉搜索树就失去了平衡，不，则这棵二叉搜索树就失去了平衡，不 再是再
11、是AVLAVL树。树。n n如果一棵二叉搜索树是高度平衡的，它如果一棵二叉搜索树是高度平衡的，它 就成为就成为 AVLAVL树。如果它有树。如果它有 n n 个结点，其个结点，其 高度可保持在高度可保持在O(logO(log2 2n n) )，平均搜索长度也平均搜索长度也 可保持在可保持在O(logO(log2 2n n) )。Wang Wenjie二叉平衡树(AVL树)（3）n n平衡化旋转平衡化旋转n n如果在一棵平衡的二叉搜索树中插入一如果在一棵平衡的二叉搜索树中插入一 个新结点，造成了不平衡。此时必须调个新结点，造成了不平衡。此时必须调 整树的结构，使之平衡化。整树的结构，使之平衡化。
12、n n平衡化旋转有两类：平衡化旋转有两类：n n单旋转单旋转 ( (左旋和右旋左旋和右旋) )n n双旋转双旋转 ( (左平衡和右平衡左平衡和右平衡) )Wang Wenjie二叉平衡树(AVL树)（4）n n每插入一个新结点时，每插入一个新结点时，AVLAVL树中相关结点的树中相关结点的 平衡状态会发生改变。因此，在插入一个新平衡状态会发生改变。因此，在插入一个新 结点后，需要结点后，需要从插入位置沿通向根的路径回从插入位置沿通向根的路径回 溯溯，检查各结点的平衡因子检查各结点的平衡因子( (左、右子树的左、右子树的 高度差高度差) )。n n如果在某一结点发现高度不平衡，停止回溯如果在某一
13、结点发现高度不平衡，停止回溯 。n n从发生不平衡的结点起，沿刚才回溯的路径从发生不平衡的结点起，沿刚才回溯的路径 取直接下两层的结点。取直接下两层的结点。Wang Wenjie二叉平衡树(AVL树)（5）n n如果这三个结点处于一条直线上，则采用单旋转进如果这三个结点处于一条直线上，则采用单旋转进 行平衡化行平衡化。单旋转可按其方向分为左单旋转和右单。单旋转可按其方向分为左单旋转和右单 旋转，其中一个是另一个的镜像，其方向与不平衡旋转，其中一个是另一个的镜像，其方向与不平衡 的形状相关。的形状相关。n n如果这三个结点处于一条折线上，则采用双旋转进如果这三个结点处于一条折线上，则采用双旋转进
14、 行平衡化行平衡化。双旋转分为先左后右和先右后左两类。双旋转分为先左后右和先右后左两类。右单旋转右单旋转左单旋转左单旋转 左右双旋转左右双旋转右左双旋转右左双旋转Wang Wenjie二叉平衡树(AVL树)（6）n n左单旋转左单旋转h hhA C EB D hh h+1BA C ED hhh+1C EABDn n如果在子树如果在子树E E中插入一个新结点，该子树高度增中插入一个新结点，该子树高度增1 1导致结点导致结点A A的的 平衡因子变成平衡因子变成+2+2，出现不平衡。，出现不平衡。n n沿插入路径检查三个结点沿插入路径检查三个结点A A、C C和和E E。它们处于一条方向为它们处于一
15、条方向为“ “ ” ”的的 直线上，需要做左单旋转。直线上，需要做左单旋转。n n以结点以结点C C为旋转轴，让结点为旋转轴，让结点A A反时针旋转。反时针旋转。+1+1+2+20 0+1+10 00 0Wang Wenjie二叉平衡树(AVL树)（7）n n右单旋转右单旋转n n在左子树在左子树D D上插入新结点使其高度增上插入新结点使其高度增1 1，导致结点，导致结点A A的平衡因子的平衡因子 增到增到 - -2 2，造成了不平衡。，造成了不平衡。n n为使树恢复平衡，从为使树恢复平衡，从A A沿插入路径连续取沿插入路径连续取3 3个结点个结点A A、B B和和D D，它它 们处于一条方向
16、为们处于一条方向为“ “/ /” ”的直线上，需要做右单旋转。的直线上，需要做右单旋转。n n以结点以结点B B为旋转轴，将结点为旋转轴，将结点A A顺时针旋转。顺时针旋转。h hhA C EB Dhh+1BA C ED hhh+1CEAB Dh0 00 0- -1 1- -1 1- -2 2Wang Wenjie二叉平衡树(AVL树)（8）先左后右双旋转先左后右双旋转n n在子树在子树F F或或GG中插入新结点，该子树的高度增中插入新结点，该子树的高度增1 1 。结点。结点A A的平衡因子变为的平衡因子变为 - -2 2，发生了不平衡。，发生了不平衡。n n从结点从结点A A起沿插入路径选取起沿插入路径选取3 3个结点个结点A A、B B和和E E ，它们位于一条形如它们位于一条形如“ “ ” ”的折线上，因此需要的折线上，因此需要 进行先左后右的双旋转。进行先左后右的双旋转。n n首先以结点首先以结点E E为旋转轴，将结
