平衡二叉树的定义

平衡二叉树（balanced binary tree），又称AVL树(Adelson-Velskii and Landis)。 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：

① 左子树与右子树的高度之差的绝对值小于等于1；

② 左子树和右子树也是平衡二叉排序树。 为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）。

平衡因子 = 结点左子树的高度 - 结点右子树的高度

根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1、0，或1

我们分析一下这个二叉树

对于40，左子树高度是2（看左子树有几层），右子树高度是3，2-3=-1，所以40的平衡因子是-1，平衡

对于24，左子树高度是0，对右子树高度为1，0-1=-1，24的平衡因子是-1，以此类推

我们直接分析一下53，53的左子树高度是0，右子树高度是2，所以0-2=-2，失衡

如果在一棵 AVL 树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

平衡调整的四种类型：

C表示的是插入的结点，怎么插入的分了上边四种类型

调整原则：1）降低高度 2）保持二叉排序树性质

对于LL型的，对根节点进行顺时针旋转，RR型是根节点A逆时针旋转

我们也可以通过平衡后要满足二叉排序树的性质，比如对上图的LL型，C<B<A，所以调整的时候，根据左子树小于根小于右子树的性质，B作为根，C作为左子树，A作为右子树

对上图的LR型，B<C<A，则C作为根节点，B作为左子树，A作为右子树

插入2，2比5小，在左子树，2比4小，是4的左子树，插入顺序是LL型，发现失衡了，于是将根节点5顺时针旋转下来即可

插入9，发现插入的是RR型，失衡了以后，将根节点4逆时针旋转，即6作为根节点，4作为6的左子树，而6的左子树作为4的右子树，也就是下图：

我们发现插入的类型是LR型，那么将叶子节点7升上去，作为根节点，然后3和16比较大小，小的3放入7的左子树，大的16放入7的右子树

我们插入8，发现是RL型，将RL型的叶子节点9升上去，7作为9的左子树，11作为9的右子树，9原本的左子树作为7的右子树