1、概念

平衡二叉树又称AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。一句话表述为：以树中所有结点为根的左右子树的高度之差的绝对值不超过1。为了判断一棵二叉排序树是否是平衡二叉树，引进了平衡因子的概念。平衡隐私是针对树中的结点来说的，一个结点的平衡因子为其左子树的高度减去右子树高度的差，对于平衡二叉树，树中的所有结点的平衡因子的取值只能是-1，0，1三个值。

2、平衡二叉树的建立

建立平衡二叉树的过程和建立二叉排序树的过程基本一样，都是将关键字逐个插入空树中的过程。所不同的是，在建立平衡二叉树的过程中，每插入一个新的关键字都要进行检查，看是否新关键字的插入会使得原平衡二叉树失去平衡，即树中出现平衡因子绝对值大于1的结点。如果失去平衡则需要进行平衡调整。

3、平衡调整

假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，首先要找出插入新结点后失去平衡的最小子树，然后再调整这个子树，使之成为平衡子树。值得注意的是，当失去平衡的最小子树碑调整为平衡子树后，无需调整原有其他所有不平衡子树，整个二叉排序树就会成为一棵平衡二叉树。所谓失去平衡的最小子树是以距离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。平衡调整有4种情况，分别为LL型，RR型，LR型和RL型。

4、一个例子

以关键字序列{16，3，7，11，9，26，18，14，15}构造一棵AVL树。
（1）先插入16，再插入3，再插入7，至此得到下图：

（2）可以看到此时这棵树已经不平衡了，所以需要对此调整。此时失去平衡的最小子树根结点为16，进行平衡调整，将7作为根结点，3和16分别作为其左右孩子，这样仍能保持跟大于左小于右的特性，这里进行的是LR调整。

（3）再插入下一个结点11，插入结点9，得到下图：

（4）可以看到此时这棵树已经不平衡了，所以需要对此调整。此处失去平衡的最小子树根结点为16，这里进行LL调整，结果如下：

（5）继续插入26，得到：

（6）可以看到此时这棵树已经不平衡了，所以需要对此调整。此时失去平衡的最小子树根结点为7，调整如下，这里进行的是RR调整。

（7）然后插入18，同样得到一颗不平衡的树：

（8）因此需要对其进行调整，此时进行的是RL调整

（9）然后插入14、15，得到图如下：

（10）分析上图的不平衡，再进行LR调整，得到下图。

（11）至此，得到了本文最开始的高度平衡的二叉树，也即AVL树。