当前课程知识点：数据结构 > 第7章 查找 > 7.4 平衡二叉树 > 讲解
本节，我们来学习平衡二叉树
简称AVL树
AVL是指平衡二叉树的两位发明者
平衡二叉树，有时候也称为高度平衡的二叉树
先来看定义
第一个定义
平衡因子，Balance Factor
简称BF
平衡因子
是指结点的左右子树高度之差
换句话说
一个结点的左子树高度，减去这个结点的右子树高度，就是这个结点的平衡因子
比如，我们看这样一棵二叉树
我们给出了每一个结点的
平衡因子，比如，3这个结点
它的左子树高度为0
右子树高度为4
所以，它的平衡因子就是0减4，-4
平衡二叉树
是在我们前面介绍的二叉排序树的基础之上，加了一个限定
所有结点的平衡因子绝对值，要小于2
换句话说
BST当中
如果所有结点的平衡因子取三个值之一，0、1、-1
那么，这时候的BST就是AVL
也就是平衡二叉树
比如，这棵树
所有结点的平衡因子绝对值，都是小于2的
比如，11它的左子树高度为2，右子树高度为3
所以，它的平衡因子是-1，叶子结点的平衡因子肯定是0，像这样的非叶结点
7，左右子树高度一样
它的平衡因子也是0，18的左子树高度比右子树高度要多1
所以，它的平衡因子是1
我们引入平衡二叉树，它的意义
就如同上节课的最后讲的
尽可能地降低二叉排序树的平均查找长度
现在，我们来看平衡二叉树的插入
它的插入规则
跟我们前面介绍的二叉排序树插入规则，是一样
需要注意
在插入之后
我们要检查一下
二叉排序树当中
所有结点，它们的平衡因子绝对值是否小于2
也就是，是否满足AVL树的限定
如果不满足
我们必须找出二叉排序树当中的最小不平衡子树
然后调整它，这里的最小不平衡子树是什么意思呢
它是指，离插入位置最近
并且，BF绝对值大于1的结点
以这个结点为根的子树
说起来比较复杂
我们引入一个例子，就明白了
比如，现在BST树，是1、3、6、7组成的这样一棵二叉排序树
它也是一棵AVL树
因为，每一个结点，它的平衡因子绝对值
都没有超过1
现在，我们在这棵BST树上，或者说AVL树上，插入一个结点10
根据我们前面介绍的BST树的插入规则
(插入)10，应该先去找10，依次找到3、6、7，10大于7，应该插到7的右子树
变成这样
现在，树变成这样
那么，有一些结点，它们的平衡因子绝对值
就超过了1
比如，这个6
它的平衡因子变成了-2
(虚线框内的)其他结点的平衡因子绝对值，都没有超过1
这时候，这棵非平衡二叉树
它的最小不平衡子树，就是虚线框框住的
这一部分
换句话说
整个二叉树的不平衡，是由虚线框框住的
这棵子树的不平衡引起的
所以，6、7、10这样一棵子树就是指
最小不平衡子树
那我们要对最小不平衡子树进行调整
比如，我们现在将7，作为这棵子树的根
调整成这样
现在
每一个结点的平衡因子绝对值，都是小于等于1的
它就是一棵AVL树
现在，我们来讲调整规则
我们分为四种形态
就是最小非平衡子树
它的形态
我们可以分成四种
前两种是左左型，以及右右型
实际上
左左型和右右型
它们是互相对称的
可以认为是一种形态，后两种形态
是左右型和右左型
它们也是互为对称的结构
也可以认为是一种形态
那我们实际上就介绍两种形态
就涵盖了这四种形态
我们先来看左左型
什么叫左左型呢
我们看3个结点的相对位置，就可以了
比如，在插入之前，平衡二叉树是这样的
大家看到，这里的
A、B、D以及C、E
这些结点以及子树
它们的平衡因子绝对值，都没有超过1
它们是平衡二叉树
现在，假设我们的插入位置，是在D这棵子树上
比如，我们在这个位置去插入，那么D
原来的高度是h，变成了h+1
它会导致
A这个结点的平衡因子，由1变成2
绝对值超过了1
所以现在，最小不平衡子树就是
A、B、D这两个结点以及这棵子树
它们的相对位置，B是A的左孩子
D是B的左子树
所以，我们把这种形态称为左左型
那左左型，我们怎么来调整呢
我们观察一下
平衡二叉树
它必须满足BST树的性质
也就是说
D是小于B的
E作为B的右子树
它是大于B的
D、B、E作为A的左子树，是小于A的
我们看这三个结点(及子树)
A、B、D
A，它的平衡因子变成了2
影响了平衡二叉树的性质
那我们只需要将A降低
那谁提高呢
很明显，将中间位置的这个结点B提高
就相当于，我们拿一根绳子拴住B
然后往上提
这样，A会往下降，B往上升
现在，我们将B作为整棵树的根结点
D跟B的相对位置不变
依然是作为B的左子树
A现在作为B的右子树，因为，A是大于B的
它一定作为B的右子树，那B原来的右子树E怎么放呢
我们知道，E是小于A的，那E就可以作为A的左子树
也就是
将E由原来的B的右子树，把它调整成A的左子树
这样，B的平衡因子，A的平衡因子，都变成了0
它甚至比原来(插入之前)更加地平衡
这是左左型，右右型是与之对称的
我们就不介绍了
我们再来看后两种形态，左右型和右左型
我们依然是只介绍左右型
在插入之前
平衡二叉树是这样的
A结点的平衡因子是1
可以，假设，我们插入的位置
是在F这棵树上
我们知道，在BST当中插入结点
新插入的结点，肯定是作为叶子结点的
假设，我们插入的叶子结点，是在F这棵树上
那么，F这棵树它的高度，会由h-1变成h
从而影响A结点
它的平衡因子，变成2，破坏了AVL树的性质
现在，我们观察几个结点的相对位置
B是A的左孩子
而E是B的右孩子
现在，插入的结点，就位于A的左子树的右子树上
所以，我们把这种形态称为左右型
现在，如何来调整呢
还是采取我们前面的左左型的思想
比如，我们现在写出几个结点(子树)的大小关系
比如D
它是小于B的
而B是小于E的
E是小于A的
我们观察这几个结点
A、B、E
因为，A结点它的左子树太高了
我们想办法，让它降低一点
我们依然是把中间位置的这个结点，作为新的树的根，把它提起来，让A降下来
现在，我们把E作为新树的根
因为，E是大于B的，B小于E
所以
B作为E的左子树
而A是大于E的
那么，A就要作为E的右子树
原来，这三个结点的相对位置，是这样的(左、右)
现在，我们把它们调整成，以中间的E(作为根)
因为，E是介于A和B之间的
我们把它调整成根
那么，E是大于B的，B作为E的左孩子，A是大于E的
A作为E的右孩子，调整成这样
现在，E有了左右孩子
但是，E原来的左右子树(F、G)怎么办呢
E它已经有了左右孩子
那原来的左右子树(如何处理呢)
我们再观察一下，F它是小于E的
E是小于G的
G是小于A的
F是大于B的
既然F大于B，G小于A
那么，F就可以作为B的右子树
G就可以作为A的左子树
我们根据这两个大小关系
就能让F作为B的右子树
G作为A的左子树
这样，我们就将这棵不平衡的二叉树，调整成了平衡的二叉树
这是左右型，那与之对称的右左型
我们就不再详细讲了
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
