本文共 2486 字，大约阅读时间需要 8 分钟。
1. 二叉排序树的问题
在上一篇学习二叉排序树时可知，二叉排序树的查找性能通常取决于二叉排序树的形状。一般来说，二叉排序树的查找也不会超过树的高度，但是个别情况除外，例如一棵只有右子树的二叉树，它的查找性能是非常差的，那么需要把它转换为平衡的二叉树。
也就是把一棵有很多节点的二叉树转换为接近于完全二叉树，这棵树的高度可以是最小的，而左，右子树高度也不会相差太多，这棵二叉树我们通常叫做平衡二叉树。
2. 什么是平衡二叉树
若一棵二叉树中每个节点的左，右子树的高度至多相差1，则称此二叉树为平衡二叉树（简称：AVL树）。
怎么去判断一棵二叉树是不是平衡二叉树？我们可以通过每个节点的平衡因子（balancd factor）来判断，即每个节点的平衡因子是该节点左子树的高度减去右子树的高度。
图1-平衡二叉树 如图1中的这棵二叉树，根节点5的平衡因子等于左子树高度 - 右子树高度，即1 = 3 - 2。对于节点2来说，左子树高度为1，右子树高度为2，那么节点2的平衡因子就是1 - 2 = -1 。对于所有叶子节点来说，由于没有左子树和右子树，那么叶子节点的平衡因子都是0，换句话说，平衡二叉树中每个节点的平衡因子取值只有0，-1和1。
最后，我们发现这棵二叉树的每个节点的平衡因子都不超过1或者-1，因此这棵二叉树符合平衡二叉树的定义，（另外需要注意的是：平衡二叉树一般来说，它是一棵二叉排序树）。
图2-非平衡二叉树 对于图2中的这棵二叉树来说，因为节点3，节点4，节点5的平衡因子超过1或-1了，而前面我们说过对于平衡二叉树中每个节点的平衡因子是不超过1和-1的，因此所以这不是一棵平衡二叉树。
//平衡二叉树节点的数据类型typedef struct node //记录类型{ KeyType key; //关键字项 int bf; //平衡因子 InfoType data; //其他数据域 struct node *lchild,*rchild; //左右孩子指针} BSTNode; 3. 平衡二叉树的调整
在平衡二叉树中插入节点的操作和二叉排序树是相似的，但是插入新节点可能会破坏平衡二叉树的平衡性，因此在插入新节点后，需要对平衡二叉树进行调整，一般有这几种情况需要调整：LL型调整，RR型调整，LR型调整，RL型调整。
3.1 LL型调整
LL型调整 —— 在左孩子的左子树上插入引起的不平衡。
图3-LL型调整 当在A节点的左孩子（B）的左子树插入新节点后（新节点为图中阴影部分），使A节点的平衡因子从1增加到2，破坏了原来二叉树的平衡，变成了非平衡二叉树，我们要做的就是调整为平衡二叉树，LL型调整策略如下：
1.将左孩子B右上旋作为新根节点2.原根节点A右下旋做为新根节点B的右孩子
3.原来B节点中的右子树作为A节点的左子树
图4-LL调整示例 上图是关于LL调整的一个示例，在插入节点5后，破坏了原本的平衡二叉树，那么根据节点的大小，有序的关系，节点10应该作为根节点，节点5应该作为节点10的左子树，而节点27应该作为节点10的右子树，这样才能调整为一棵平衡二叉树，而这个调整过程就是上面我们所说的LL调整原理。
4.2 RR型调整
RR型调整 —— 在右孩子的右子树上插入引起的不平衡
图5-RR型调整 当在A节点的右孩子（B）的右子树中插入新节点后（图中阴影部分），使二叉树的根节点的平衡因子从-1增到-2了，导致原来的平衡二叉树变得不平衡了，RR调整策略如下：
1.右孩子B左上旋作为根节点2.原根节点A左下旋做为B的左子树
3.原来节点B的左子树作为A的右子树
图6-RR调整示例 上图是关于RR调整的一个示例，红色虚线内的三个节点之间正好构成了RR这样的关系， 那么根据节点的大小，有序这样的关系，把中间的节点B左上旋作为根节点，把其他两个节点（27和73）分别作为左，右孩子节点才能平衡，这个调整过程就是上面所说的RR调整原理。
4.3 LR型调整
LR型调整 —— 在左孩子的右子树上插入引起的不平衡
图7-LR型调整 当在左孩子的右子树上插入新节点后（图中阴影部分），使二叉树的根节点的平衡因子增到2，导致不平衡，那么LR型调整策略：
1.C节点穿过A，B节点往上升2.B节点成为C节点的左孩子，A节点成为C节点的右孩子
3.原来C节点的左子树作为B节点的右子树，原来C节点的右子树作为A节点的左子树。
图8-LR调整示例 这是关于LR调整的一个示例，红色虚线内的三个节点之间正好构成了LR这样的关系， 那么根据节点的大小，有序这样的关系，把C节点穿过A和B两个节点，作为根节点，把其他两个节点（10和27）分别作为左，右孩子节点，再把原先C节点的右子树作为A节点的左子树，这样才能平衡，这个调整过程就是上面所说的LR调整原理。
4.4 RL型调整
RL型调整——针对右孩子的左子树上插入引起的不平衡
图9-RL型调整 当在右孩子的左子树上插入新节点后（图中阴影部分），使二叉树的根节点的平衡因子增到-2，导致不平衡，那么RL型调整策略为：
1.C节点穿过A，B节点往上升2.B节点成为C节点的右孩子，A节点成为C节点的左孩子
3.原来C节点的右子树作为B节点的左子树，原来C节点的左子树作为A节点的右子树。
图10-RL调整示例 这是关于RL调整的一个示例，红色虚线内的三个节点之间正好构成了RL这样的关系， 那么根据节点的大小，有序这样的关系，把C节点穿过A和B两个节点，作为根节点，把其他两个节点（27和51）分别作为左，右孩子节点，再把原先C节点的右子树作为B节点的左子树，这样才能平衡，这个调整过程就是上面所说的RL调整原理。