高度平衡的二叉树精编版

《高度平衡的二叉树精编版》由会员分享，可在线阅读，更多相关《高度平衡的二叉树精编版（79页珍藏版）》请在金锄头文库上搜索。

1、高度平衡的二叉搜索树 AVL Addison VelskiandLandis 树伸展树红黑树 二叉搜索树性能分析 对于有n个关键码的集合 其关键码有n 种不同排列 可构成不同二叉搜索树有 棵 2 1 3 1 2 3 1 3 2 2 3 1 3 1 2 3 2 1 同样3个数据 1 2 3 输入顺序不同 建立起来的二叉搜索树的形态也不同 这直接影响到二叉搜索树的搜索性能 如果输入序列选得不好 会建立起一棵单支树 使得二叉搜索树的高度达到最大 用树的搜索效率来评价这些二叉搜索树 为此 在二叉搜索树中加入外结点 形成判定树 外结点表示失败结点 内结点表示搜索树中已有的数据 这样的判定树即为扩充的二叉

2、搜索树 举例说明 已知关键码集合 a1 a2 a3 do if to 对应搜索概率p1 p2 p3 在各搜索不成功间隔内搜索概率分别为q0 q1 q2 q3 可能的二叉搜索树如下所示 判定树 在判定树中 表示内部结点 包含了关键码集合中的某一个关键码 表示外部结点 代表各关键码间隔中的不在关键码集合中的关键码 在每两个外部结点间必存在一个内部结点 一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率p i 与搜索该结点时所需的关键码比较次数c i l i 即结点所在层次 乘积之和 设各关键码的搜索概率相等 p i 1 n搜索不成功的平均搜索长度ASLunsu

3、cc为树中所有外部结点上搜索概率q j 与到达外部结点所需关键码比较次数c j l j 乘积之和 设外部结点搜索概率相等 q j 1 n 1 设树中所有内 外部结点的搜索概率都相等 p i 1 3 1 i 3 q j 1 4 0 j 3图 a ASLsucc 1 3 3 1 3 2 1 3 1 6 3 ASLunsucc 1 4 3 2 1 4 2 1 4 1 9 4 图 b ASLsucc 1 3 2 2 1 3 1 5 3 ASLunsucc 1 4 2 4 8 4 图 c ASLsucc 1 3 1 1 3 2 1 3 3 6 3 ASLunsucc 1 4 1 1 4 2 1 4 3

4、2 9 4 图 d ASLsucc 1 3 2 1 3 3 1 3 1 6 3 ASLunsucc 1 4 2 1 4 3 2 1 4 1 9 4 1 相等搜索概率的情形 图 e ASLsucc 1 3 1 1 3 3 1 3 2 6 3 ASLunsucc 1 4 1 1 4 3 2 1 4 2 9 4 图 b 的情形所得的平均搜索长度最小 设二叉搜索树中所有内 外部结点的搜索概率互不相等 p 1 0 5 p 2 0 1 p 3 0 05q 0 0 15 q 1 0 1 q 2 0 05 q 3 0 05分别计算各个可能的扩充二叉搜索树的搜索性能 判断哪些扩充二叉搜索树的平均搜索长度最小 2

5、 不相等搜索概率的情形 图 a ASLsucc 0 5 3 0 1 2 0 05 1 1 75 ASLunsucc 0 15 3 0 1 3 0 05 2 0 05 1 0 9 图 b ASLsucc 0 5 2 0 1 1 0 05 2 1 2 ASLunsucc 0 15 0 1 0 05 0 05 2 0 7 图 c ASLsucc 0 5 1 0 1 2 0 05 3 0 85 ASLunsucc 0 15 1 0 1 2 0 05 3 0 05 3 0 75 图 d ASLsucc 0 5 2 0 1 3 0 05 1 1 35 ASLunsucc 0 15 2 0 1 3 0 05

6、 3 0 05 1 0 8 由此可知 图 c 和图 e 的情形下树的平均搜索长度达到最小 因此 图 c 和图 e 的情形是最优二叉搜索树 图 e ASLsucc 0 5 1 0 1 3 0 05 2 0 9 ASLunsucc 0 15 1 0 1 3 0 05 3 0 05 2 0 7 一般把平均搜索长度达到最小的扩充的二叉搜索树称作最优二叉搜索树 等概率条件下 最优二叉搜索树的最短内部路径长度与最短外部路径长度 课本383页 一 什么是平衡二叉树二 失衡二叉排序树的分析与调整 平衡二叉树 平衡二叉树又称为AVL树 一棵平衡二叉树或者是空树 或者是具有下列性质的二叉排序树 左子树与右子树的高

7、度之差的绝对值小于等于1 左子树和右子树也是平衡二叉排序树 例 平衡二叉树 引入平衡二叉树的目的是为了提高查找效率 使其平均查找长度为O log2n 根据平衡二叉树的定义 平衡二叉树上所有结点的平衡因子只能是 1 0 或1 当我们在一个平衡二叉排序树上插入一个结点时 有可能导致失衡 即出现绝对值大于1的平衡因子 如2 2 为了方便起见 给每个结点附加一个数字 给出该结点左子树与右子树的高度差 这个数字称为结点的平衡因子 例 下图对平衡二叉树和失去平衡的二叉排序树分别标注了平衡因子 一 什么是平衡二叉树 二 失衡二叉排序树的分析与调整 平衡二叉树 如果在一棵AVL树中插入一个新结点 就有可能造成

8、失衡 此时必须重新调整树的结构 使之恢复平衡 我们称调整平衡过程为平衡旋转 现分别介绍这四种平衡旋转 平衡旋转可以归纳为四类 LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转 若在A的左子树的左子树上插入结点 使A的平衡因子从1增加至2 需要进行一次顺时针旋转 以B为旋转轴 1 LL平衡旋转 右单旋转 RotateRight h h h A C E B D a b c h h 1 B A C E D h h h 1 C E A B D 在左子树D上插入新结点使其高度增1 导致结点A的平衡因子增到 2 造成了不平衡 为使树恢复平衡 从A沿插入路径连续取3个结点A B和D 它们处于一条方向为 的直

9、线上 需要做右单旋转 以结点B为旋转轴 将结点A顺时针旋转 h 0 0 0 1 1 2 左改组 新插入结点出现在危机结点的左子树上进行的调整 的情况分析 1 LL情况 LL 表示新插入结点在危机结点的左子树的左子树上 A B 1 h 1 0 2 1 h h 1 h 1 LL改组 BL BR AR B A 0 h 0 h 1 h 1 BL BR AR 危机结点 改组前 高度为h 1中序序列 A B BL BR AR 改组后 高度为h 1中序序列 A B BL BR AR 注意 改组后平衡度为0 A B 若在A的右子树的右子树上插入结点 使A的平衡因子从 1增加至 2 需要进行一次逆时针旋转 以B

10、为旋转轴 2 RR平衡旋转 左单旋转 RotateLeft h h h A C E B D a b c h h h 1 B A C E D h h h 1 C E A B D 如果在子树E中插入一个新结点 该子树高度增1导致结点A的平衡因子变成 2 出现不平衡 沿插入路径检查三个结点A C和E 它们处于一条方向为 的直线上 需要做左单旋转 以结点C为旋转轴 让结点A反时针旋转 1 2 0 1 0 0 若在A的左子树的右子树上插入结点 使A的平衡因子从1增加至2 需要先进行逆时针旋转 再顺时针旋转 以插入的结点C为旋转轴 3 LR平衡旋转 2 LR情况 LR 表示新插入结点在危机结点的左子树的右

11、子树上 情况A A B 1 h 1 0 2 1 h 1 LR改组 BL AR 危机结点 改组前 高度为h 1中序序列 注意 改组后平衡度为0 0 1 C B C CL CR h 2 h 2 h 1 0 1 C B 0 h 1 h 1 BL AR A CR h 2 CL h 1 1 0 A B BL AR C CL CR 改组后 高度为h 1中序序列 A B BL AR C CL CR A DoubleRotations Fig 28 7 a TheAVLtreeinFig 28 5afteradditionsthatmaintainitsbalance b afteranadditiontha

12、tdestroysthebalance continued DoubleRotations Fig 28 7 ctd c afteraleftrotation d afterarightrotation 若在A的右子树的左子树上插入结点 使A的平衡因子从 1增加至 2 需要先进行顺时针旋转 再逆时针旋转 以插入的结点C为旋转轴 4 RL平衡旋转 这种调整规则可以保证二叉排序树的次序不变 综上所述 在一个平衡二叉排序树上插入一个新结点S时 主要包括以下三步 1 查找应插位置 同时记录离插入位置最近的可能失衡结点A A的平衡因子不等于0 2 插入新结点S 并修改从A到S路径上各结点的平衡因子 3

13、根据A B的平衡因子 判断是否失衡以及失衡类型 并做相应处理 DoubleRotations Fig 28 5 a Adding70tothetreeinFig 28 2cdestroysitsbalance torestorethebalance performboth b arightrotationand c aleftrotation 例 请将下面序列构成一棵平衡二叉排序树 13 24 37 90 53 013 113 124 213 需要RR平衡旋转 绕B逆转 B为根 124 137 190 237 需要RL平衡旋转 绕C先顺后逆 例如 输入关键码序列为 16 3 7 11 9 26

14、 18 14 15 插入和调整过程如下 左右双旋 右单旋 15 18 2 3 18 16 2 左右双旋 7 3 0 0 0 11 7 14 9 1 16 15 0 1 11 26 26 14 1 2 9 从空树开始的建树过程 各种搜索结构的比较 课本397页图10 14 作业 1 设有关键码序列 55 31 11 37 46 73 63 02 07 从空树开始构造平衡二叉搜索树 画出每加入一个新结点时二叉树的形态 伸展树 SplayingTree 伸展树 AVL树 并查集的用双亲表示的树 都属于自调整数据结构 self adjustingdatastructure AVL树使得搜索树保持高度平

15、衡 让叶结点只出现在最低的一层或两层上 从而提高其搜索效率 伸展树是另一种提高搜索效率的方法 其思路是 单一旋转 将经常访问的结点最终上移到靠近根的地方 使以后的访问更快 移动到根部 假设正访问的结点将以很高的概率再次被访问 对它反复进行子女 父结点旋转 直到被访问的结点位于根部为止 伸展树提出了一组改进二叉搜索树性能的一组规则 每当执行搜索 插入 删除等操作时 就要依据这些规则调整二叉搜索树 从而保证操作的时间代价 每当访问 搜索 插入或删除 一个结点s时 伸展树就执行一次叫做 展开 splaying 的过程 将结点s移到二叉搜索树的根部 就像AVL树 一次 展开 由一组旋转组成 旋转有三种

16、类型 单旋转 一字形旋转和之字形旋转 一次旋转的目的是通过调整结点s与它的父结点p和祖父结点g之间位置 把它上移到树的更高层 被访问结点s的父结点p是根结点 此时执行单旋转 在保持二叉搜索树特性的情况下 结点s成为新的根 原来的根p成为它的子女结点 同构形状 homogeneousconfiguration 结点s是其父结点p的左子女 结点p又是其父结点g的左子女 或者结点s是其父结点p的右子女 结点p又是其父结点g的右子女 此时执行一字形旋转 zigzigrotation 右单旋转 异构的形状 heterogeneousconfiguration 结点s是其父结点p的左子女 结点p又是其父结点g的右子女 或结点s是其父结点p的右子女 结点p又是其父结点g的左子女 此时执行之字形旋转 zigzagrotation 右单旋转 右单旋转 因为刚访问的结点s与其父结点p和祖父结点g形成折线 需要做与AVL树一样的双旋转 首先围绕s旋转p 再围绕s旋转g 把结点s上升到祖父结点的位置 并保持二叉搜索树的特性 左单旋转 右单旋转 将刚访问的结点s上移到树根部的算法 splaying g p s