当前课程知识点：数据结构 > 第8章 查找 > 8.4 平衡二叉树 > 8.4 平衡二叉树
同学们，大家好
我是云南大学信息学院教师孔兵
这节课我们介绍平衡二叉树
平衡二叉树，又称为AVL树
它或者是一棵空树，或者是具有下列性质的二叉树
它的左子树和右子树都是平衡二叉树
且它的左子树和右子树的深度之差的绝对值不超过1
为了鉴别平衡二叉树
给树中每个结点定义平衡因子
平衡因子可以看做树中每个结点的一个属性
结点的平衡因子是以该结点为根的左右子树的深度之差
称为该结点的平衡因子
如果是平衡二叉树
那么树中所有结点的平衡因子，只能是（-1,0,1）
观察图1和图2
这两棵就是平衡二叉树
树中所有结点的平衡因子都是-1，0或者1
图3中，整棵树的根的平衡因子是2
它左右子树都是平衡二叉树
但是，整棵树不是平衡二叉树
图4的二叉树中，树根的右子树不是平衡二叉树
所以整棵树也不是平衡二叉树
前面分析过二叉排序树的查找效率
查找效率高的二叉排序树
整棵树的深度应该尽可能小
n个结点的二叉树最好深度同完全二叉树
这是绝对平衡的
那么退一步，如果二叉排序树是平衡二叉树
查找效率非常接近折半查找的效率
二叉排序的建立，初始的时候
它是一棵空树，空树是一棵平衡的二叉排序树
那么，伴随着记录的逐渐插入
二叉排序树可能失去平衡
这个时候需要对二叉排序树进行调整，使之重新平衡
如图所示，图1是空树，图2插入了一个结点
结点上方标注该结点的平衡因子，下方标注关键字
图3插入第2个结点
到此时，二叉排序树仍然是平衡的
图4又插入了一个结点37之后
整棵排序树就不平衡了
这里要明确一个概念
就是因插入结点而失去平衡的最小子树的根
这个概念很重要
后面调整的操作都是围绕这个结点进行的
图4当中，结点13是因插入结点而失去平衡的最小子树的根结点
结点13的子树是平衡的
出现失衡以后，可以进行调整
这里围绕结点13进行一次左旋
把结点13的右孩子结点24向上提一层作为树根
13作为24的左孩子，调整后如图5所示
经过调整，整棵树重新变得平衡了
随后又插入两个结点，插入90后
仍然是平衡的，插入53以后失衡了
图6中，37是因插入结点而失去平衡的最小子树的根结点
作为37的子树，以90为根的子树是平衡的
作为37的双亲结点24，以24为根的子树也是失衡的
但是，24为根的子树不是失去平衡的最小子树
因为24的右子树是失衡的，而且比它小
这种情况的调整稍微麻烦一点，我们随后介绍
因插入结点而失去平衡的最小子树的根结点这个概念
同学们一定要搞清楚
首先设a为指向因插入结点而失去平衡的最小子树的根结点
这是后续旋转调整的中心
为了针对性的调整，我们把失衡的情况分为4种
第1种失衡的情况称为LL型
LL型失衡的原因是
因为在*a的左子树根结点的左子树上插入结点导致的失衡
简单的说就是左子树的左子树插入结点，所以被称为LL型的
针对这个类型的失衡
采用的办法是围绕结点*a做一次右旋平衡处理
具体的做法是
把*a的左孩子向上提一层
作为*a双亲的新子树的根，而*a作为新根的右孩子
与这两个结点相关的子树
按照二叉排序树的性质进行适当的调整
看具体的例子，观察图1
图1中目前为是一棵平衡的二叉排序树
假设插入一个关键字为4的记录
那么插入以后，4作为7的左孩子
如图2所示。这时二叉排序树失衡
失衡最小子树的根是13，围绕13做一次右旋平衡处理
把13的左做孩子7向上提一层
作为13双亲24的新子树的根
而13作为新根7的右孩子，这里比较简单
没有其它子树的调整，结果如图3所示
下面讨论一般情况下LL型的调整
图1中，给出了一棵二叉排序树的局部
因在A的左子树B的左子树中插入一个结点
导致B的左子树BL深度增加了1层
就是红色网格这块，二叉排序树失衡
B子树是平衡的，A是因插入失衡的最小子树的根
那么需要围绕A做单向右旋平衡处理
把A的左做孩子B向上提一层，作为新子树的根
A作为B的右孩子，按二叉排序树的性质
B原来的右子树BR调整为A的左子树，结果如图2所示
虽然只是局部调整，只要原来的二叉排序树是平衡的
局部调整后整棵二叉排序树也是平衡的
调整不牵扯树的其它部分
调整的代价比较低
这是二叉排序树最好的性质
第2种称为RR型
RR型失衡的原因是在*a的右子树根结点的右子树插入结点导致的失衡
图1中是平衡的二叉排序树
图2中插入了关键字为99的记录之后失衡
37是失衡的最小子树的根
对于RR型的失衡，做一次单向左旋平衡处理
左旋平衡处理和右旋平衡处理是对称的
就是把37的右孩子90向上提一层
作为新子树的根
90作为新子树的根
37作为新根的左孩子
旋转处理以后的结果如图3所示
第3种是LR型
这种失衡的原因是
因为在*a的左子树根结点的右子树插入结点而导致的失衡
图1是平衡的二叉排序树
插入关键字为11的记录
插入以后是7的右孩子
13是因插入而失衡的最小子树的根
对于13来说
失衡的原因是在它左子树根结点的右子树上
插入而导致的失衡
这是一个LR型的失衡
LR型的失衡的调整需要两次旋转
一次做左旋，一次做右旋
同学们要注意，两次旋转的方法和前面讨论的一样
但是两次旋转围绕的结点是不一样的
观察图2，第一次左旋是围绕结点7
用绿色标识，第2次右旋是围绕*a
就是结点13，用红色标识
第1次左旋后，结果如图3所示
第2次右旋后，结果如图4所示
下面讨论一般情况下LR型的调整
观察图1，因在A的左子树根结点B的右子树C中插入结点
导致CL的深度增加1层，就是红色网格这一块
A是因插入而失衡的最小子树的根
第1次先围绕A的左子树根B做一次左旋
结果如图2所示
随后围绕A做一次右旋
把A的左子树的根C提上来作为新树的根
A作为C的右孩子
C的右子树调整为A的左子树
结果如图3所示
把最后一种失衡RL型
失衡的原因是在*a的右子树根结点的左子树插入结点而导致的失衡
RL型的调整也需要2次旋转，一次右旋一次左旋
图1中是一棵RL型失衡的二叉排序树
37是失衡的最小子树的根，先围绕90做一次右旋
结果如图2所示，再围绕37做一次左旋，结果如图3所示
我们讨论了二叉排序树失衡的4种可能的情况
那么，在创建二叉排序树的过程当中，一旦出现失衡
就根据失衡的原因进行调整，使之重新平衡
那么最终可以获得一棵平衡的二叉排序树
如果二叉排序树是平衡的
它的查找性能可以达到对数阶，效果非常理想
好，同学们这节课
我们就讲到这儿，下次课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
