查找讲义.ppt

在含 N 个关键字的 B-树上进行一次查找，需访问的结点个数不超过 log?m/2?((N+1)/2)+1 结论： 是B-树的一种变型 四、B+树 二叉平衡树是二叉查找树的另一种形式，其特点为： 树中每个结点的左、右子树深度之差的绝对值不大于1 。 例如: 5 4 8 2 5 4 8 2 1 是平衡树 不是平衡树 结点的平衡因子：该结点的左子树的深度减去 ( -1 0 1 ) 右子树的深度 构造二叉平衡（查找）树的方法是： 在插入过程中，采用平衡旋转技术。 假设由于在二叉排序树上插入结点而 失去平衡的最小子树根结点为A，沿插入 路径取直接下两层的结点为B和C，如果这 三个结点处于一条直线上，则采用单旋转 进行平衡化；如果这三个结点处于一条折线 线上，则采用双旋转进行平衡化。失去平衡 后进行调整的规律可归纳为下列4种情况： 调整方法：以结点B为旋转轴，将结点A向右旋转成为 B的右子树，结点B代替原来A的位置，原来B的右子树 成为A的左子树。 原因：在A 的左子树根结点的左子树上插入结点， A的平衡因子由1增至2，至使以A为根的子树失去平衡。 A B h C h BR h AR 插入结点 （1）单向右旋平衡处理：(LLR) LL R A B h+1 C h BR h AR 调整方法：以结点B为旋转轴，将结点A向左旋转成为 B的左子树，结点B代替原来A的位置，原来B的左子树 成为A的右子树。 原因：在A 的右子树根结点的右子树上插入结点， A的平衡因子由-1增至-2，至使以A为根的子树失去平衡。 A B h C h BL h AL 插入结点 （2）单向左旋平衡处理：(RRL) RR L A B h+1 C h BL h AL 调整方法：先以C为旋转轴，将结点B向左旋转成为 C的左子树，结点C代替原来B的位置，原来C的左子树 成为B的右子树。 原因：在A 的左子树根结点的右子树上插入结点， A的平衡因子由1增至2，至使以A为根的子树失去平衡。 （3）先左后右平衡处理：(LRLR) A B h-1 CL h-1 CR h AR 插入结点 C h BL B A h AR h CL h BL C h-1 CR B A h AR h CL h BL C h-1 CR 再以C为旋转轴，将A向右旋转成为 C的右子树，结点C代替原来A的位置，原来C的右子树 成为B的左子树。 L R 再以C为旋转轴，将A向左旋转成为 C的左子树，结点C代替原来A的位置，原来C的左子树 成为B的右子树。 调整方法：先以C为旋转轴，将结点B向右旋转成为 C的右子树，结点C代替原来B的位置，原来C的右子树 成为B的左子树。 原因：在A 的右子树根结点的左子树上插入结点， A的平衡因子由-1增至-2，至使以A为根的子树失去平衡。 （4）先右后左平衡处理：(RLRL) A B h-1 CR h-1 CL h AL 插入结点 C h BR BR A h AL h CR h B C h-1 CL B A h AL h CR h BR C h-1 CL R L A B C A B C 例如:依次插入的关键字为5, 4, 2, 8, 6, 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转 一次 先向右旋转 再向左旋转 B C A C B A C B A 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字 9 C A B 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。 平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？ n = 0 空树 最大深度为 0 n = 1 最大深度为 1 n = 2 最大深度为 2 n = 4 最大深度为 3 n = 7 最大深度为 4 先看几个具体情况: 反过来问，深度为 h 的二叉平衡树中所含结点的最小值 Nh 是多少？ h = 0 N0 = 0 h = 1 h = 2 h = 3 一般情况下 N1 = 1 N2 = 2 N3 = 4 Nh = Nh-1 + Nh-2 + 1 利用归纳法可证得 Nh = Fh+2 - 1 因此，在二叉平衡树上进行查找时， 查找过程中和给定值进行比较的关键字的个数和 log(n) 相当。 由此推得，深度为 h 的二叉平衡树中所含结点的最小值 Nh = ?h+2/5 - 1。 反之，含有 n 个结点