1. AVL树介绍

1.1 什么是AVL树

在介绍AVL树之前，来谈谈为什么要引入AVL树。

AVL树本质上是一棵二叉搜索树，但是普通的二叉搜索树无法控制平衡，在某些特殊的插入情况下，搜素的时间复杂度会从O(log(n))级别退化为O(n)级别，这显然不是我们所希望的。

为了解决普通二叉搜索树的失衡问题，AVL树，即平衡二叉搜素树产生了。

AVL树使用平衡因子来控制整棵二叉搜索树的平衡。对于一个结点而言，平衡因子是其右子树的高度减去左子树的高度（反过来亦可），由于要控制平衡，因此，平衡因子的绝对值不能超过1，如果超过1，在AVL树的体系下，整棵树就失衡了。对于一棵空树，我们也认为它是AVL树。

值得一提的是，AVL树是通过平衡因子来控制平衡，但是平衡因子这个成员并不一定要实际存在于AVL树结点的结构中，但在结构中，添入这个平衡因子，会使得判断和调节平衡更加方便，否则每次都需要计算某个结点的左右子树高度之差，才能判断是否平衡，这就显得有些麻烦了。

通过AVL树较为严格地控制平衡，使得整棵树左右结点分布较为均匀，接近于完全二叉树，因此总能将搜素的时间复杂度控制在log(n)级别。

下图是一棵AVL树：

下图不是一棵AVL树：

1.2 AVL树结构代码展示

2. AVL树插入的平衡调节

AVL树在不断插入结点的过程中，肯定会出现失衡，即平衡因子的绝对值大于1的情况，此时就需要进行平衡调节，接下来的内容将详细阐述在插入过程中，平衡调节的过程。

在插入一个结点之前，需要找到这个结点插入的位置，这个按照普通二叉搜素树插入的规则，正常找到相应位置即可。真正要重点关注的，是插入之后的平衡调节。

在一个结点插入后，如果其父节点不为空(即非根结点插入的情况)，那么其父结点的平衡因子会有三种情况：0，1或-1，2或-2。我们讨论时，便是分为这三种情况进行讨论。对于空树的插入，直接将插入结点置为根结点，无需额外处理。

2.1 插入后节点的平衡因子为0

插入后节点的平衡因子为0，说明插入前该节点的平衡因子为1或-1。插入后，对于以该节点为根的子树而言，平衡未被破坏；对于该结点的父节点而言，由于子树的高度是按子树的最大高度进行计算的，因此其平衡因子不会改变。因此，这种插入情况未破坏AVL树的平衡，不需要进行平衡调节。

2.2 插入后节点的平衡因子为1或-1

插入后节点的平衡因子为1或-1，说明插入前该节点的平衡因子为0。

此时对于该节点，平衡没有破坏，但是对于该节点以上的结点而言，由于该节点所在的子树高度发生改变，因此它们的平衡因子可能遭到破坏。因此，在这种情况下，我们需要不断更新父子结点，迭代向上检验。如果途中遇到某个节点的平衡因子为0，那便是第一种情况，可以不再迭代；如果遇到平衡因子为2或-2，那就是第三种情况，进行相应旋转处理后，也可不再迭代。否则，需要不断迭代，直到根结点为止，以确保没有一个结点的平衡因子失常。

2.2 插入后节点的平衡因子为2或-2

插入后节点的平衡因子为2或-2，说明插入前该节点的平衡因子为1或-1。

此时该节点的平衡因子失常，需要以该节点为根结点的树进行旋转以控制平衡。

2.2.1 左单旋

下图是进行左单旋的情况：

我们需要将1左旋下来，即让2结点的_left指针指向1，1结点的_right指针指向2结点的左子树，需要注意与更上层结点的连接关系（如果有的话）。旋转后，结果如下：

2.2.2 右单旋

旋转后的情况如下图所示：

具体的调节过程：让结点1的_right指针指向2，结点2的_left指针指向结点1的右子树，同时需要注意与更上层结点的连接关系（如果有的话）。

2.2.3 左右双旋

左右双旋，即先进行左旋，再进行右旋，下图所示情况需进行左右双旋：

但上图情况又可分为两类，即n == 1时和n > 1时。

当n==1时，情况如下图所示：

当n > 1的情况，如下图所示：

注意，这种情况又分为两种情况：

上述左右双旋的具体过程为：先对以1为根结点的子树进行左旋，左旋后，再对以3为根结点的树进行右旋，注意旋转后与更上层结点的连接关系（如果有的话）。

2.2.4 右左双旋

右左双旋，先进行右旋转，再进行左旋转。
右左双旋的情况与左右双旋的情况刚好是反过来的。

下图是需要进行右左双旋的情况：

第一种情况：

第二种情况：

3. AVL树插入的具体代码

3.1 插入接口的代码

3.2 各种旋转的代码

3.2.1 右单旋

3.2.2 左单旋

3.2.3 右左双旋

3.2.4 左右双旋

如果要获取更详尽的代码，可至博主的gitee仓库获取具体代码：AVLTree

4. AVLTree的删除

AVLTree的删除较之于插入，平衡因子的调节会更为复杂，在本篇博客中，暂不做介绍。值得一提的是，对于AVLTree的插入，最多会进行两次旋转；但对于AVLTree的删除，最多会进行log(n)级别的旋转。