平衡二叉树和B树ppt课件

由关键字序列3 1 2 5 4构造而得的二叉搜索树 由关键字序列1 2 3 4 5构造而得的二叉搜索树 ASL 1 2 3 4 5 5 3 ASL 1 2 2 3 3 5 2 2 平均查找长度 平均查找长度 ASL pi ci pi是节点i的查找概率 ci是比较次数 或所处的层数 成功 ASL 1 2 2 3 3 5 2 2 ASL有查找成功和不成功之分 失败 ASL 3 3 4 4 4 4 6 3 7 上面的矩形实际表示了一个区间 a b 即 1 1 and 2 2 and 3 平衡二叉树 树中每个结点的左 右子树高度之差的绝对值不大于1 即 平衡二叉树 hl hr 1 结点的平衡因子 该结点的左子树的深度减去它的右子树的深度 平衡二叉树所有结点的平衡因子只可能为 1 0 1 非平衡树 0 1 2 2 0 0 0 1 1 平衡树 平衡二叉树 平衡二叉树 插入或删除1个节点都有可能使得平衡二叉树变的不再平衡 关键是子树的高度是否发生了变化 新插入的节点一定是叶子节点 平衡因子为0 其父节点的高度可能发生变化 图1 图2 图3 图4 1 新节点插在平衡因子值为1的节点的右 或者 1的节点的左 父节点不会不平衡 父节点的高度没有变化 不会波及祖先节点的高度发生变化 1 0 1 0 高度变化的传播 2 新节点插在平衡因子值为0的节点左或右 父节点不会不平衡 但因为父节点变高 可能波及祖先节点不平衡 高度变化的传播 插入1个新节点后 可能造成父节点增高 进而波及其它的祖先节点 直至根节点 新结点X插在左重结点A 假设A是波及的路径上离新结点插入位置最近的左重结点 的左孩子的左分支上 并使得该分支变高 X 2 1 LL型二叉树的平衡 注意 BL BR AR的高度相同 均为h 1 调整过程 1 将BA向右旋转90度 把B的右孩子变为A的左孩子2 A变为B的右孩子 B代替A的位置 X 1 2 X 0 0 LL型二叉树的平衡 新结点X插在左重结点A A是离新结点插入位置最近的左重结点 的左孩子的右孩子的左分支上 1 0 1 2 1 0 LR型二叉树的平衡 调整过程 1 将CB向左旋转90度 把CL变为B的右子树 把B变为C的左孩子 2 1 1 2 2 LR型二叉树的平衡 调整过程 2 将BCA向右旋转90度 把C的右孩子变为A的左孩子 A变为C的右孩子 C带替A的位置 1 2 2 1 1 0 LR型二叉树的平衡 新结点X插在右重结点A A是离新结点插入位置最近的右重结点 的右孩子的右分支上 1 h 1 h 1 h 0 1 2 RR型二叉树的平衡 调整过程 将BA向左旋转90度 把B的左孩子变为A的右孩子 A变为B的左孩子 B带替A的位置 h 1 h h 1 h 1 2 0 0 RR型二叉树的平衡 新结点X插在右重结点A A是离新结点插入位置最近的右重结点 的右孩子的左孩子的右分支上 1 h 1 h 2 h 1 h 1 0 1 1 RL型二叉树的平衡 调整过程 1 将CB向右旋转90度 把CR变为B的左子树 把B变为C的右孩子 h 1 h 1 h 1 h 1 1 1 0 2 2 RL型二叉树的平衡 调整过程 2 将BCA向左旋转90度 把C的左孩子变为A的右孩子 A变为C的左孩子 最后 C带替A的位置 h 1 h 1 h 1 h 1 0 2 2 0 0 1 RL型二叉树的平衡 平衡二叉树的再平衡 1 首先确定造成节点A不平衡的原因 即怎样波及到节点A 2 使用前面的调整方法调整 调整后 就不会再往A的上层节点波及 例如 依次插入关键字5 4 2 8 6 9 平衡二叉树的构造 继续插入关键字9 平衡二叉树的构造 在平衡二叉树树上进行查找的过程和二叉搜索树相同 因此 查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度 问 含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 性能分析 3 因此 在二叉平衡树上进行查找时 查找过程中和给定值进行比较的关键字的个数和log n 相当 1 由此推得 深度为h的平衡二叉树中所含结点的最小值Nh h 2 5 1 2 反之 含有n个结点的平衡二叉树能达到的最大深度h log 5 n 1 2 O logn 性能分析 按次序输入关键字 1 2 3 4 5 6 7 试画出平衡二叉树的构造和调整过程 课堂练习 作业14 下次课堂提问 1 平衡二叉树又叫AVL树 试解释之 2 按次序输入关键字 7 6 5 4 3 2 1 试画出平衡二叉树的构造和调整过程 B 树 一棵m阶的B 树 或为空树 或为满足下列特性的m叉树 1 若根结点不是叶子结点 则至少有两棵子树 2 除根之外的所有非终端 叶子 结点至少有棵子树 最多有m棵子树 B 树 3 所有非终端结点中包含下列信息数据 n A0 K1 A1 K2 A2 Kn An 4 所有叶子结点都在同一层 叶子结点中只有关键字 无指针 或有指针 但为空指针 a n为关键字的个数 多个关键字自小至大有序排列 即 K1 K2 Kn b 且Ai 1所指子树上所有关键字均小于Ki c Ai所指子树上所有关键字均大于Ki d 关键字的个数比子树的个数小1 B 树 从根结点出发 沿指针搜索结点和在结点内进行顺序 或折半 查找两个过程交叉进行 若查找成功 则返回指向被查关键字所在结点的指针和关键字在结点中的位置 B 树 在查找不成功之后 需进行插入 显然 关键字插入的位置必定在最下层的叶子结点 有下列几种情况 以3 阶为例 1 插入后 该结点的子树个数n m 不需要修改指针 如插入关键字60 B 树插入结点 2 插入后 该结点的子树个数n m 则需进行 结点分裂 令s m 2 a 在原结点中保留 A0 K1 Ks 1 As 1 b 建新结点 As Ks 1 Kn An c 将 Ks p 插入双亲结点 B 树插入结点 再插入关键字90 B 树插入结点 3 若双亲为空 则建新的根结点 再插入关键字30 B 树插入结点 删除操作和插入结点的考虑相反1 首先必须找到待删关键字所在结点 并且要求删除之后 结点中关键字的个数不能小于 m 2 12 否则 要从其左 或右 兄弟结点 借调 关键字3 若其左和右兄弟结点均无关键字可借 结点中只有最少量的关键字 则必须进行结点的 合并 B 树删除结点 1 被删除结点上关键字个数不少于 m 2 1 那么只需从该结点上删除该关键字Ki和相应的指针Ai 例如下图3 阶B树中删除关键字12时 直接将12删除即可 a b c d e f g h B 树删除结点 2 如果被删除结点上关键字个数等于 m 2 1 而与其相邻的右兄弟结点 或左兄弟 结点中关键字的个数大于 m 2 1 上图为删除50前 后的3阶B 树 a b c d e f g h B 树删除结点 3 被删除关键字所在结点和其相邻的右兄弟结点 或左兄弟 结点中关键字的个数均等于 m 2 1 a b c d e f g h 删除关键字53 B 树删除结点 a b c d e g h 练习 从上面的B树中删除关键字37 B 树删除结点 a b c d e g h 37没有右兄弟且其左兄弟也只有一个关键字 把37双亲结点中小于37的关键字24与左兄弟中的3合并成一个结点 此时 发现左右子树高度不同 必须继续处理 e c h g B 树删除结点 e c h g 调整后的B 树 如下所示 B 树删除结点 在B 树中进行查找时 其查找时间主要花费在搜索结点 访问外存 上 即主要取决于B 树的深度 问 1 含N个关键字的m阶B 树可能达到的最大深度H为多少 性能分析 2 深度为H的B 树中 至少含有多少个结点 第2层2个 先推导每一层所含最少结点数 第1层1个 第H 1层2 m 2 H 1个 第4层2 m 2 2个 第3层2 m 2 个 性能分析 假设m阶B 树的深度为H 1 由于第H 1层为叶子结点 而当前树中含有N个关键字 则叶子结点必为N 1个 N 1 2 m 2 H 1H 1 log m 2 N 1 2 H log m 2 N 1 2 1 由此可推得下列结果 性能分析 在含n个关键字的B 树上进行一次查找 需访问的结点个数不超过log m 2 n 1 2 1 结论 性能分析 是B 树的一种变型 1 有n棵子树的结点中含有n个关键字 2 所有的叶子结点中包含了全部关键字的信息 及指向含这些关键字记录的指针 并且 所有叶子结点彼此相链接构成一个有序链表 其头指针指向含最小关键字的结点 3 每个非叶结点中的关键字Ki即为其相应指针Ai所指子树中关键字的最大值 B 树 B 树 1 在B 树上 既可以进行缩小范围的查找 也可以进行顺序查找 2 在进行缩小范围的查找时 不管成功与否 都必须查到叶子结点才能结束 3 若在结点内查找时 给定值 Ki 则应继续在Ai所指子树中进行查找 B 树 类似于B 树进行 即必要时 也需要进行结点的 分裂 或 归并 B 树 表示关键字集合 HAD HAS HAVE HE HER HERE HIGH HIS 键树 键树又称为数字查找树 它是一棵度 2的树 其中的每个结点中不是包含一个或者几个关键字 而是只包含组成关键字的符号 键树 1 关键字中的各个符号分布在从根结点到叶结点的路径上 叶结点内的符号为 结束 的标志符 因此 键树的深度和关键字集合的大小无关 2 键树被约定为