知识准备
二叉树基础请见：二叉树基础
1 二叉查找树
二叉查找树又称二叉搜索树（Binary Search Tree）或二叉排序树（Binary Sort Tree）。其或者是一棵空树，或者是具有下列性质的二叉树：
1 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
3 左、右子树也分别为二叉排序树；
4 没有键值相等的节点（no duplicate nodes）。
**二叉查找树的平均深度是O(logN)**，所以查询速度是非常快的，实际使用也非常多。但是从定义我们可以知道，二叉查找树可以任意地构造，同样是上图六个数字，也可以按照下图的方式来构造：
这样这棵二叉树的查询效率就变得很低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树。
2 平衡二叉树（AVL树）
平衡二叉树（AVL树）是在符合二叉查找树的条件下，还满足如下性质的二叉树：
任何节点的两个子树的高度最大差为1。
下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差<=1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1。
如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下：
AVL树失去平衡之后，可以通过旋转使其恢复平衡。下面分别介绍四种失去平衡的情况下对应的旋转方法。
LL旋转
LL失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡。步骤如下：
- 将根节点的左孩子作为新根节点。
- 将新根节点的右孩子作为原根节点的左孩子。
- 将原根节点作为新根节点的右孩子。
LL旋转示意图如下：
RR旋转
RR失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡，旋转方法与LL旋转对称。步骤如下：
- 将根节点的右孩子作为新根节点。
- 将新根节点的左孩子作为原根节点的右孩子。
- 将原根节点作为新根节点的左孩子。
RR旋转示意图如下：
LR旋转
LR失去平衡的情况下，需要进行两次旋转。步骤如下：
- 围绕根节点的左孩子进行RR旋转。
- 围绕根节点进行LL旋转。
LR旋转示意图如下：
RL旋转
RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转对称。步骤如下：
- 围绕根节点的右孩子进行LL旋转。
- 围绕根节点进行RR旋转。
RL旋转示意图如下：
从这四种旋转可以看出，首先我们应该判断失去平衡的树是LL、RR、LR、RL，然后针对性的进行旋转，然后就可以重新把树转化成平衡树。
平衡二叉树和avl树的C++示例代码如下：
1 | (待整理)。 |