AVL树的插入（C++实现）

1. 概念

AVL树（Adelson-Velsky and Landis Tree）于1962年被提出，是计算机科学中最早被发明的平衡二叉查找树。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis。

在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是$O(logN)$。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

1.1 性质

AVL树有这样的性质：

1. 任意一个结点的左右子树高度之差都不大于1；
2. 任意子树都是AVL树。

高度之差，在这里也叫做平衡因子（balance factor）：
$$平衡因子=右子树高度-左子树高度$$
所以平衡因子的值只有三个：-1/0/1。

为什么要限制左右子树的高度呢？

高度平衡二叉搜索树，控制每个结点的左右子树高度差不超过1。因为偶数个节点如2或4，都无法让左右高度差相等，所以退而求其次，让它接近完全二叉树，控制树的高度在${\log }_{2}N$之内（$N$是结点数）。

所以AVL的高度平衡是相对于每个根结点而言的，也就是平衡因子的绝对值不大于1。

这不是一棵AVL树，其中，值为76的结点左子树比右子树高度多3，即平衡因子是-3。

同一棵高度平衡的AVL树，每个结点的平衡因子都不大于1。

平衡因子是一种实现AVL树的限定方法，它不是必须的，只是一种叫法。

本文GIF动图皆使用ScreentoGif软件在网站https://visualgo.net录制。

2. 定义结点类

AVL树是改良以后的二叉搜索树，由于它有着平衡因子的限制，所以将AVL树的结点用三叉链表示，其中新增的是根结点的父结点的指针，以便稍后进行旋转后的链接操作。除此之外，也需要为每个结点增加一个新的属性：平衡因子。

这里使用了pair，它是储存一个键值对（key和value）的单位，分别用模板参数K和V表示。其中，构造函数分别把指针默认设置为nullptr，平衡因子默认设置为0，由于模板参数在传入时就必须指定类型，所以使用传入的模板参数组合构造pair。

// 定义结点类
template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;

	pair<K, V> _kv;

	int _bf;

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. 插入函数

由于AVL树是优化的二叉搜索树，我们知道，在二叉搜索树中，插入是要按照规则在指定区域插入的，所以二叉搜索树的各种操作都是有查找功能的。

AVL树的查找步骤和二叉搜索树别无二致，只是多了限制条件：平衡因子的绝对值不大于1，所以在每次插入以后都要根据平衡因子的情况对树的形态进行调整，比如旋转。

插入可以分为两种情况：

1. 空树：插入根结点；
2. 非空：插入后根据平衡因子是否符合条件选择是否旋转。

二叉搜索树的插入规则：规则：

• 新结点的值小于根结点的值，将结点插入到左子树当中；
• 新结点的值大于根结点的值，将结点插入到右子树当中；
• 新结点的值等于根结点的值，插入结点失败。

那么如何决策是否要旋转呢？如何旋转？

3.1 更新平衡因子

当我们插入或删除某一个结点时，都会引起这个结点的所有祖先节点的平衡因子发生改变。

什么是祖先节点？

• 结点A->B之间如果存在（唯一）一条路径，那么称A为B的祖先，B称为A的子代。一个结点的祖先不止一个。

从新插入结点的第一个父结点开始往上更新平衡因子，最坏的情况可能要一直更新到根结点。除了root的父结点是nullptr，其他所有结点都有父结点，所以可以用这个条件判断是否遍历完祖先节点。

规则

当前祖先节点，就是新插入结点的祖先节点中的某一个结点。

• 新插入结点在当前祖先节点（parent）的左边，平衡因子-1；
• 新插入结点在当前祖先节点（parent）的右边，平衡因子+1；

每次执行以上操作以后，还要继续判断当前祖先结点（parent）平衡因子的情况，以判断是否还要继续向上调整：

• parent的平衡因子等于-1或1，接近平衡，继续往上更新；
  • 说明未插入结点之前parent是平衡的，插入后改变了parent这棵子树的平衡，它的子树一边比另一边高。而更高的一边虽然让parent这棵子树满足bf的绝对值小于等于1，但是它仍然有可能会影响parent往上的祖先节点。
• parent的平衡因子等于0，平衡，停止往上更新；
  • 说明未插入结点之前parent是不平衡的，插入以后使得parent这棵子树平衡，它的两边子树一样高，不会影响所有祖先结点的平衡因子，停止更新。
• parent的平衡因子等于-2或2，不平衡，无法通过调整平衡因子达到平衡，需要旋转。
  • 说明在未插入之前，parent这棵子树已经是一边高一边低（1层）了，插入以后一边比另一边高2层，通过调整平衡因子已经无法解决平衡问题了，所以需要进行旋转操作。

由于新插入的结点可能会影响所有祖先结点的平衡因子，所以最坏的情况要一直更新到根节点。因为从下到上迭代祖先节点，所以结点类的实现使用了三叉链结构，其中新增的是当前结点指向父结点的指针。

动图中的平衡因子 = 左子树高度 - 右子树高度，是一样的。

3.2 直接插入

AVL树插入新结点，如果最后新结点的所有祖先结点的平衡因子都符合AVL树的要求，就不用旋转。

通过动图可以知道，当插入新结点以后，比二叉搜索树多出的步骤就是检查新增结点的祖先节点的平衡因子是否符合条件。插入后的祖先结点的bf变化情况如下：

由于这部分的代码会被包含在下面的情况，而且插入的操作和二叉搜索树的逻辑并无二致，所以在此只给出插入以后向上检查祖先节点的平衡因子的逻辑：

while (parent)
{
    if (parent->_right == cur)				// 插入在右边，bf+1
    {
        parent->_bf++;
    }
    else									// 插入在左边，bf-1
    {
        parent->_bf--;
    }

    if (parent->_bf == 0)					// 直到符合AVL树的规则停止
    {
        break;
    }
    else if (abs(parent->_bf) == 1)			// 往上调整
    {
        parent = parent->_parent;
        cur = cur->_parent;
    }
    else if (abs(parent->_bf) == 2)			// 不平衡
    {
		// 不平衡，要进行下面的旋转操作
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

抽象图表示了无数种情况的集合，但具体采取哪种旋转方式，只取决于平衡因子不符合条件的那一小部分。

3.3 左单旋

示例

首先看动图中的示例：

下面是新结点的所有被影响的祖先节点的平衡因子的变化情况：

理解

当新结点插入以后，值为86的结点就不平衡了，这时需要对其进行旋转，怎么知道向哪边旋转的呢？

如果86结点就是根结点，那么这样旋转后整棵树就直接平衡了，而实际情况可能是它作为一棵子树旋转的，所以旋转以后还要重新链接到原树上。

上面的图示中是（左）单旋的最简情况，实际上AVL树的结点往往不止这些，所以为了理解上的方便，由于平衡因子是左右子树的高度差，所以以一个固定值h表示高度，把这h高度的结点看作一个整体，相对于它的偏移量就能表示许多情况了。

为了描述和代码上的实现方便，新插入结点叫做cur，子树的根结点叫做parent，根结点的右孩子叫做subR，右孩子的左孩子叫做subRL：

抽象图要从整体感受，上图中插入结点以后parent不平衡，bf=2，说明它的右子树比左子树高2层，可以感性地认为右子树更重。所以以parent结点为轴点（从图形看是从subR为轴点，但是函数中的参数是parent），逆时针旋转，让那个高的一边单独做parent的右子树，然后让subRL“离家出走”，做parent的右孩子（看图）。

步骤

1. 让subR的左子树subRL作为parent的右子树；
2. 让parent作为subR的左子树；
3. 让subR作为子树的整棵子树的根结点；
4. 向上按照规则更新平衡因子。

// 左单旋函数
void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pParent = parent->_parent;				// 保存父结点的父结点

    parent->_right = subRL;							// 重建subRL和parent联系
    if (subRL != nullptr)
    {
        subRL->_parent = parent;
    }

    subR->_left = parent;							// 重建subR和parent联系
    parent->_parent = subR;


    if (parent == _root)							// 父结点为根结点，旋转后的subR作为根结点，无父结点
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (pParent->_left == parent)
        {
            pParent->_left = subR;
        }
        else
        {
            pParent->_right = subR;
        }

        subR->_parent = pParent;
    }
    subR->_bf = 0;									// 更新平衡因子
    parent->_bf = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

注意

更新后的平衡因子是根据旋转以后的抽象图才能知道的，所以写树的代码时（数据结构）一定要画图，否则在脑子里是很乱的。

3.4 右单旋

示例

新插入结点的祖先结点的平衡因子变化情况如下：

理解

同样地，使用新插入结点叫做cur，子树的根结点叫做parent，根结点的左孩子叫做subL，右孩子的左孩子叫做subLR：

右单旋和左单旋是对称的，只是平衡因子的正负有所区别。依然可以形象地用“重量”理解它，就像扁担一样。

步骤

1. 让subL的右子树subLR作为parent的左子树；
2. 让parent作为subL的右子树；
3. 让subL作为整棵子树的根结点；
4. 向上按照规则更新平衡因子。

// 右单旋函数
void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* pParent = parent->_parent;				// 保存父结点的父结点

    parent->_left = subLR;							// 重建subLR和parent联系
    if (subLR != nullptr)
    {
        subLR->_parent = parent;
    }

    subL->_right = parent;							// 重建subL和parent联系
    parent->_parent = subL;


    if (parent == _root)							// 父结点为根结点，旋转后的subL作为根结点，无父结点
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (pParent->_left == parent)
        {
            pParent->_left = subL;
        }
        else
        {
            pParent->_right = subL;
        }

        subL->_parent = pParent;
    }
    subL->_bf = 0;									// 更新平衡因子
    parent->_bf = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

注意

单旋的图示中的树都可能是子树，所以步骤的第三步中只是将旋转后的subR、subL作为子树的根结点。既然是子树，旋转以后的子树就必须链接到原树上，所以这也是AVL树的结点类使用三叉链结构的原因之一，其中新增的是parent指针。

3.5 左右双旋

示例

新插入结点的祖先结点的平衡因子变化情况如下：

理解

当在subLR的右子树中插入结点，会让parent的平衡因子变为-2，不平衡。从旋转之前的二叉树来看（第二个二叉树），对parent而言，它的左子树更“重”，而且就从子树的个数而言，parent的左孩子subL有3个子树，而右孩子只有一个子树。

这样讨论是合理的，因为AVL树严格限制了每个结点子树的高度，所以对于parent而言，这4个子树的高度是接近的。

这里的子树是相对于parent，就parent的左右孩子而言的，所以总共四个子树。

从结果来看，引发双旋的原因是parent某一边的子树有3个子树，而另一边只有1个子树。经过双旋以后将那3个中的一个子树分到另一边，这样就让整棵树满足AVL树的规则。

步骤

1. 以subL为轴点左单旋；
2. 以parent为轴点右单旋；
3. 更新平衡因子。

// 左右双旋函数
void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateL(subL);
    RotateR(parent);

    if(bf == -1)
    {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    }
    else if(bf == 1)
    {
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else if(bf == 0)
    {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else
        assert(false);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

注意

根据插入后未旋转之前subLR的平衡因子的情况（-1/0/1），双旋以后的平衡因子更新情况有三种：

1. 当插入后subLR的平衡因子为-1：

   

   更新后的平衡因子：parent：1；subL：0；subLR：0。

2. 当插入后subLR的平衡因子为0：

   

3. 当插入后subLR的平衡因子为1：

   

3.6 右左双旋

示例

新插入结点的祖先结点的平衡因子变化情况如下：

理解

双旋的过程是对称的。但是思想都是相同的，将子树多的那一部分放到少的那一边。

// 右左双旋函数
void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

    RotateR(subR);
    RotateL(parent);

    if(bf == -1)
    {
        subR->_bf = 1;
        parent->_bf = 0;
        subRL->_bf = 0;
    }
    else if(bf == 1)
    {
        subR->_bf = 0;
        parent->_bf = -1;
        subRL->_bf = 0;
    }
    else if(bf == 0)
    {
        subR->_bf = 0;
        parent->_bf = 0;
        subRL->_bf = 0;
    }
    else
        assert(false);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

4. AVL树的验证

首先AVL树是二叉搜索树，所以首先可以验证它是否符合二叉搜索树的性质：

// 中序遍历子函数
void _InOrder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }

    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12

然而中序遍历只能验证它是一棵二叉搜索树，而AVL树限制条件更严格，所以可以遍历每个结点，让结点中的平衡因子和实际的平衡因子比较。

如何知道实际的平衡因子？

• 使用平衡因子公式：
  $$平衡因子=右子树高度-左子树高度$$

使用递归得到当前结点子树高度时，返回的是左右子树中更高的子树高度再加上自身结点高度（+1）：

// 验证平衡因子 子函数
bool _IsBalance(Node* root)
{
    if(root == nullptr)
    {
        return false;
    }

    int leftH = Height(root->_left);
    int rightH = Height(root->_right);
    int diff = rightH - leftH;

    if(diff != root->_bf)
    {
        cout << root->_kv.first << "平衡因子异常" << endl;
        return false;
    }

    return abs(diff) < 2
        && _IsBalance(root->_left)
        && _IsBalance(root->_right);

}
int Height(Node* root)								// (子)树的高度等于结点高度+高的子树
{
    if(root == nullptr)								// 空树高度为0
        return 0;

    return max(Height(root->_left), Height(root->_right)) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

5. AVL树的性能

AVL树有着严格的高度限制，是高度平衡的二叉搜索树，可以保证二叉树在任何情况都是接近完全二叉树的，这个特性使得在查找时的效率稳定性比普通的二叉搜索树好，因为后者不是所有情况下查找的效率都是$O(lo{g}_{2}N）$。AVL树即使在最坏的情况下，查找的时间复杂度也是$O(lo{g}_{2}N）$。

但是，虽然它查找的效率很高，是严格的$O(lo{g}_{2}N)$，然而删除操作的时间复杂度在$log(2lo{g}_{2}N)$左右。插入操作的时间复杂度在$O(lo{g}_{2}N）$之上，因为AVL树的平衡因子的绝对值只要超过1，就必须旋转，由于频繁插入使得效率变低。

红黑树是AVL树的优化，它解决了AVL树频繁插入导致效率变低的问题。