[TOC]

AVL 树的介绍和模拟实现

1. AVL树的简介

AVL树也是二叉搜索树的一种，但是是经过优化的，AVL树的效率比一般的二叉搜索树高很多，但是略逊红黑树一点点。至于什么是二叉搜索树呢？我忘了写了，后期补上，嘻嘻。简单来说二叉搜索树看名字就知道是一颗树，是用来搜索的。它有自己的特殊规则，就是，每个节点都要满足左子树 < 根 < 右子树。满足这个条件就可以说这颗树是一个二叉搜索树，当然如果反过来的话，也可以叫二叉搜索树。

二叉搜索树的查找、插入和删除效率取决于树高，时间复杂度可以写成 O(h)。当树比较平衡时，树高 h 约为 logN，操作效率就是 O(logN)；但是二叉搜索树也是有缺陷的，就是在原始数据有序时容易退化成链表，树高变成 O(N)，搜索效率也会变回 O(N)。

为了解决这个问题呢？AVL树和红黑树其实都是来解决这个问题的，只不过两个树的规则不同。顺带一提，AVL 是两位苏联科学家的名字，他们发明了 AVL 树，这比红黑树要早一些。话说回来，AVL树的规则就是在二叉搜索树的基础上，再加一个条件：任意节点的左右子树高度差绝对值最大为 1。如果左右高度相差大于 1 了，就要经过旋转来修改。

2. AVL树的模拟实现

1.平衡因子的引入

刚才提到，我们要如何来维护左右高度相差为 1 呢？这里我们引入了一个平衡因子。本文约定平衡因子为 右子树高度减去左子树高度，这样就可以更好地去维护左右子树的高度差。平衡因子也不是必须要使用的，也有的AVL树实现会直接维护节点高度；接下来描述的AVL树实现使用平衡因子。

当插入一个新节点的时候，不止影响它父亲的平衡因子，还会影响这条路径上祖先节点的平衡因子，需要分情况来调整。

2.插入新节点

一个AVL树，在插入一个新节点的时候，需要根据这个节点父亲的平衡因子来调整树的结构。

按照本文“右高减左高”的约定：节点插入在左边，平衡因子就 --；节点插入在右边，平衡因子就 ++。

如果插入后父亲的平衡因子是 0，也就是说插入之前父亲的平衡因子是 1 或者 -1。说明这次插入让这个子树更平衡了，子树高度不再增加，也就不用继续向上判断和修改。
如果插入后父亲的平衡因子是 1 或 -1，也就是说插入之前父亲的平衡因子是 0。说明这个子树高度增加了，所以需要沿着这条路径继续向上调整祖先节点的平衡因子。
如果父亲节点平衡因子已经变成了 2 或 -2，那么就需要通过旋转来调整。

3. 旋转

之前我们提到过的，调整AVL树的办法就是旋转。旋转分为四种：右单旋、左单旋、左右双旋和右左双旋。下面平衡因子的结论主要针对插入新节点导致的失衡；删除场景的平衡因子调整会更复杂，不能直接套用。

右旋

考虑旋转的时候就体现出画图的重要性了，但是，单单画图还不够，这里画细节图的话会很头大，所以这里最好是画抽象图。什么意思呢？如下图：

我们看到这个数，就是画的一个抽象图，把子树 a , b , c 的高度抽象为 h 。这样的话 10 这个节点的平衡因子就是 -1 ，左子树上再插入一个节点就要旋转。假设插入再 a 这个子树上，那么 a 这个树的高度就变成 h + 1 ,如下图：

这样的话， 10 节点的平衡因子就变成 -2 了，这个时候就需要调整了。但是，我们看到，这个 h 是可以取很多值的。

当 h = 1 的时候，这里其实 b 子树有一种情况， c 子树有一种情况， a 子树（插入后）有 2 种情况；

这样看是不是还好，那么当 h = 2 呢？

当 h = 2 的时候， a, b ,c 树就是大约这样的形状， b 子树有 3 种情况， c 子树也有 3 种情况，所以在 a 的插入点就有 4 * 3 种情况。所以，整个就有 108 情况。

看起来是不是还好。

那么当 n = 3 呢？

这就是 a b c 子树的大体情况就是这样。所以， b 子树和 c 子树就有 C(4 ,4) + C(4,3) + C(4,2) + C(4,1) 种情况。 a 子树也有很多种情况。总之就是，这样如果考虑细节的话，要考虑的情况是列举不完的。所以，我们在这里画了抽象图,换句话说，这些情况的处理方式都是差不多的。

好了好了，我们话再说回来，右旋是怎么回事呢？

我们看到，10 的平衡因子变为了 -2 ，所以，10 就是旋转点。旋转本质上就是一种降高度嘛，

我们可以，把 10 变成 5 的右子树，把 5 的右子树变成 10 的左子树。

也就是变成这样：

原谅我画的图丑爆了，但是我感觉还是听清晰的，嘻嘻。我们可以看到这个树经过右旋以后，所有的节点的平衡因子都变成了 0 。

左旋

左旋的情况和右旋正好是反过来的。插入前是这样的，

还是插入在 a 子树上，变成这样：

然后左旋：把 10 变成 5 的左子树， 5 的左子树变成 10 的右子树，

可以看到， 5 变成了根，所有节点的平衡因子都变成了 0 。这就是左旋。

左右双旋

之前提到了左旋和右旋，那么什么是左右双旋呢？其实就是插入的地方不同。仔细看一下刚才的两个情况，我们插入之后，还没有旋转的时候， 10 的平衡因子分别是 -2 和 2 ， 5 这个节点的平衡因子分别是 -1 和 1；

换句话说，右旋的情况，是左边高的左边高，因为 10 和 5 的平衡因子都是负数，也就代表着左边高嘛。

左旋的情况是，是右边高的右边高，因为 10 和 5 的平衡因子都是正数。

如果，我们改变一下插入的位置，不插入在 a 子树，插入在 b 子树的话，右旋的情况就变成了左边高的右边高，对应平衡因子 10 是 -2 ， 5 是 1 ，如图：

因为要用到 5 的右子树的下一个节点，我就又具体画了一个，出来，插入在 8 这个子树上， 5 的平衡因子就变成了 1 。如果是这样的话，单靠右旋是解决不了问题的。可以话话试试看，还是以 10 为旋转点，右旋一次，变成这样：

可发现，如果只右旋一次的话，就变成这样，依然没有解决问题，说实话再转转也转不出来，有兴趣可以试试。

那么这时候怎么办呢？就需要左右双旋了：先以 5 为旋转点左旋一次，然后在以 10 为旋转点，右旋一次，总共旋转两次。如图：

看到左旋 5 一次后的结果，是不是就很清晰了，这是不是又变成了左边高的左边高情况，再来一次右旋就好了，完成之后，就变成了这样，说实话这个就三个节点的看着有点抽象啊，我也是偷个懒，我只画的关键的几个节点。

那么平衡因子呢？我们来画一个稍微聚体一些的：

这是左旋一次后的具体的结果，然后再右旋，

可以看到，左右双旋之后，整个树就变成了这样，也就是说，把 8 变成了整棵树的根，注意啊，这整个树也可以是子树。来看平衡因子， 8 的平衡因子是 0 ， 10 的平衡因子也是 0 ， 5 的平衡因子是 -1 。

明白过程以后，就可以直接看看结论了，结论就是， 8 这个节点变成根， 8 的左子树给了 5 ， 8 的右子树给了 10； 8 的左子树高度是 h - 1, 所以 5 的平衡因子是 -1 。 8 的右子树是 h ，所以 10 的平衡因子是 0； 8 最后转完了以后平衡因子也是 0 。

右左双旋

左右双旋看明白了，那么右左双旋也就完全没有问题了，反过来就可以。

当插入后，出现右边高的左边高的情况，如图：

然后，先以 5 为旋转点右旋，再以 10 为旋转点左旋，

这里我就直接用结论了，

然后，可以看到， 8 的平衡因子是 0 ， 10 的平衡因子是 0， 5 的平衡因子是 1。

4.AVL树的实现

AVL树也是一种二叉搜索树，是一个三叉链的结构，再加一个平衡因子就好了,这里实现的是一个 Key Value 的结构

template<class K, class V>
struct AVLTreeNode
{
    std::pair<K, V> _kv;

    AVLTreeNode* _parent;
    AVLTreeNode* _left;
    AVLTreeNode* _right;

    // 本文约定：右子树高度 - 左子树高度
    int _bf;

    AVLTreeNode(const std::pair<K, V>& kv)
        : _kv(kv)
        , _parent(nullptr)
        , _left(nullptr)
        , _right(nullptr)
        , _bf(0)
    {}
};