数据结构第20次课 查找B.pptVIP

二 平衡二叉树( AVL树） 什么是平衡二叉树(Balanced Binary Tree) ? 平衡二叉树是空树,或者是具有以下性质的二叉树: 它的左子树和右子树也都是平衡二叉树并且 左子树和右子树的深度之差的绝对值不超过1 结点的平衡因子BF (Balance Factor)是 左子树的深度减去右子树的深度,它只可能是 -1, 0, 1 平衡二叉树(也称AVL树)的深度为O(log2N) (其中N为结点个数) 它的平均查找长度也是O(log2N) 平衡二叉树及平衡因子举例 不平衡二叉树及平衡因子举例 二叉排序树转成平衡树失去平衡后需要进行调整的四种情况 (1) 单向右旋平衡处理LL 当在左子树上插入左结点,使平衡因子由1增至2时 (2) 单向左旋平衡处理RR 当在右子树上插入右结点,使平衡因子由-1增至-2时 (3) 双向旋转(先左后右)平衡处理LR 当在左子树上插入右结点,使平衡因子由1增至2时 (4) 双向旋转(先右后左)平衡处理RL 当在右子树上插入左结点,使平衡因子由-1增至-2时 二叉排序树转成平衡树示例设关键字序列为(13,24,37,90,53) * 数据结构 计算机与信息学院 刘勇 * 数据结构 有七个人曾经住在一起，每天分一大桶粥。要命的是，粥每天都是不够的。一开始，他们抓阄决定谁来分粥，每天轮一个。于是乎每周下来，他们只有一天是饱的，就是自己分粥的那一天。后来他们开始推选出一个道德高尚的人出来分粥。强权就会产生腐败，大家开始挖空心思去讨好他，贿赂他，搞得整个小团体乌烟瘴气。然后大家开始组成三人的分粥委员会及四人的评选委员会，互相攻击扯皮下来，粥吃到嘴里全是凉的。最后想出来一个方法：轮流分粥，但分粥的人要等其它人都挑完后拿剩下的最后一碗。为了不让自己吃到最少的，每人都尽量分得平均，就算不平，也只能认了。大家快快乐乐，和和气气，日子越过越好。同样是七个人，不同的分配制度，就会有不同的风气。所以一个单位如果有不好的工作习气，一定是机制问题，一定是没有完全公平公正公开，没有严格的奖勤罚懒。如何制订这样一个制度，是每个领导需要考虑的问题。 每课一贴 -1 1 0 0 -1 1 0 平衡的二叉树 1 1 0 0 不平衡的二叉树 -1 0 0 0 -2 1 0 2 -1 0 1 0 0 危急 结点 危急 结点 二叉排序树在结点添加过成中失衡 的几种情况 二叉排序树在结点添加平衡化方法总结 遇见不“平”，拔锤相击 0 13 -1 13 0 24 0 37 0 13 -2 13 -1 24 0 24 0 37 0 53 0 13 0 13 0 37 0 90 0 53 -1 24 1 90 -2 37 -2 24 (a) (b) (c) (d) (e) (f) (g) (h) 24 13 37 53 90 (h) 24 13 37 53 90 2 A 1 B 0 A 0 B BL BR AR h h-1 h-1 AR BR LL BL 1、 LL型平衡旋转 A的左子树的左子树上插入结点，作顺时针旋转。 2、 RR型： A的右子树的右子树上插入结点，作逆时针旋转。 -2 A -1 B 0 A 0 B BR BL AL h-1 BL AL RR BR h-1 h 2 A -1 B -1 A 0 C CL BL AR h-2 h-1 h-1 LR 1 C h-1 CR 0 B BL AR CL CR 3、 LR型： A的左子树的右子树上插入结点，作两次（逆、顺）旋转。 4 RL型： 在A的右子树的左子树上插入结点，作两次（顺、逆）旋转。 h-1 -2 A 1 B -1 B 0 C CL AL h-2 h-1 RL 1 C h-1 CR 0 A AL BR CL CR BR 练习：下列情况属于哪种失衡状况？应该操作哪些结点？ LR 12,7,9 RR 12,19 二叉排序树在结点添加平衡化实例 例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。 15，12，7，19，24，9，8，5，6 例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。 15，12，7，19，24，9，8，5，6 例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。 15，12，7，19，24，9，8，5，6 失衡二叉排序树平衡化过程特性 h-1 -2 A 1 B -1 B 0 C CL AL h-2 h-1 RL 1 C h-1 CR 0 A AL BR CL CR BR 1、 树的高度不会增加；h＋1