前言

今天，我们继续踏入追寻C++的冒险历程。上一章我们了解两类关联式容器——set和map，那么本章将为大家讲解一种特殊的二叉搜索树——AVL树。下面让我们一起来进入AVL树的学习。

1. AVL树的概念

在前面我们介绍了二叉搜索树，这棵树我们可以用来进行查找操作，其查找的时间复杂度取决于该树的高度，最好的情况是该树接近于为满二叉树，查找的时间复杂度为O(log₂N)。但是由于其特定的插入方式导致我们无法去控制树的高度，使得每一个结点两边子树的高度差距过大，导致它的高度会接近于N，使得查找的时间复杂度变为O(N)，那么有没有一种方法可以使得我们的二叉搜索树的查找效率恒为O(log₂N)呢？答案当然是有的，也就是我们本章要为大家介绍的AVL树，也就是平衡二叉搜索树。

从名字我们可以看到，平衡二叉搜索树与二叉搜索树间的区别就在于平衡二字！对于平衡二叉搜索树叫做AVL树是得益于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，因此采用他们名字的缩写来命名这棵特殊的二叉搜索树。

那么究竟什么是AVL树呢？我们来看一下它的定义：

AVL树是⼀颗空树或者具备下列性质的⼆叉搜索树：

• 它的左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。
• AVL树是⼀颗⾼度平衡搜索⼆叉树，通过控制⾼度差去控制平衡。

由此我们可以得知平衡二字指的是每一个结点的左右子树的高度要保持平衡，高度差不能超过1。

AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在log₂N，那么增删查改的效率也可以控制在log₂N，相⽐⼆叉搜索树有了本质的提升。

2. 平衡因子

了解了平衡之后我们知道对于AVL树来说最重要的就是控制平衡。那么我们该怎么去判断一棵二叉搜索树是否平衡呢？这里引入了一个新的概念：平衡因子(balance factor) 。在AVL树中每一个结点都有一个平衡因子，它的值等于该结点的右子树高度减去左子树高度，也就是说在AVL树中每一个结点的平衡因子的值都只能为1、-1、0，否则该树就不是一棵AVL树。但是AVL树并不是必须要平衡因⼦，只是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样。

AVL树的结构

那么有了平衡因子后AVL树的结构是怎样的呢？观察下面的代码：

	template<class K, class V>
    struct AVLTreeNode
    {
        // 需要parent指针，后续更新平衡因⼦可以看到
        pair<K, V> _kv;
        AVLTreeNode<K, V>* _left;
        AVLTreeNode<K, V>* _right;
        AVLTreeNode<K, V>* _parent;
        int _bf; // 平衡因子
        
        AVLTreeNode(const pair<K, V>& kv)
            :_kv(kv)
            , _left(nullptr)
            , _right(nullptr)
            , _parent(nullptr)
            ,_bf(0)
            {}
    };

	template<class K, class V>
	class AVLTree
    {
        typedef AVLTreeNode<K, V> Node;
        public:
        //...
        private:
        Node* _root = nullptr;
    }

• 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

因为之前我们学习set和map时了解了pair类，因此这里我们直接采用**key_value**的模式。把上面的代码与我们之前二叉搜索树的代码做比较，可以发现，AVL树只比二叉搜索树多了两个成员变量，分别是父节点的指针和平衡因子。新增父节点的指针是为了在AVL树中插入数据时可以更好的更新平衡因子。

3. AVL树的插入

3.1 插入的大致过程

对于AVL树的插入我们仍按照正常二叉搜索树的插入方式去进行插入，不过再插入过后需要对相应的平衡因子进行更新，因为插入一个数据可能会导致树的高度变化。

新增结点后，如果高度增加，那么只会影响该结点的祖先结点的高度，也就是会影响到祖先结点的平衡因子，入下图所示：

当我们插入了结点9之后，它的祖先结点的平衡因子可能会被影响，也就是8和6，插入完成之后，我们需要对可能被影响的结点的平衡因子进行更新：

所以更新从新增结点->根结点路径上的平衡因⼦，最坏情况下要更新到根结点，有些情况更新到中间就可以停⽌了，具体情况我们下⾯再详细分析。

在平衡因子更新的途中，如果某个结点的平衡因子的变为**-2或2**，则说明插入数据之后导致该树变得不平衡了，因此需要对不平衡的子树进行旋转操作，使这棵树从不平衡变为平衡，还是一棵AVL树。至于什么是旋转我们下面再详细介绍。

当更新平衡因子的途中没有出现问题，那么插入操作就结束了。下面让我们来看一看平衡因子到底该怎么更新。

3.2 平衡因子的更新

更新原则：

• 平衡因⼦ = 右⼦树⾼度-左⼦树⾼度
• 只有⼦树⾼度变化才会影响当前结点平衡因⼦。
• 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦–。
• parent所在⼦树的⾼度是否变化决定了是否会继续往上更新。
• 插入的结点的平衡因子为0。

更新之后：

• 更新后parent的平衡因子等于0，说明在更新前parent的平衡因子为1或者-1，更新前parent的⼦树⼀边⾼⼀边低（差值为1），新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，插入结束。
• 更新后parent的平衡因⼦等于1 或 -1，说明在更新前parent的平衡因⼦为0，更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低（高度差为1），parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响parent的⽗亲结点的平衡因⼦，所以要继续向上更新。
• 更新后parent的平衡因⼦等于2 或 -2，说明在更新前parent的平衡因⼦为1或者-1，更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，通过旋转操作使子树变得平衡且高度降低1，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。
• 不断更新，更新到根结点，根结点的平衡因⼦不为2或-2，插入结束。

总的来说，更新平衡因子我们需要去遍历插入结点的所有祖先结点，在更新这些祖先结点的途中，如果更新完平衡因子为0，那么就停止循环，插入结束；如果更新完平衡因子为2或-2，那么通过旋转操作后停止循环，插入结束；如果更新后为1或-1，那么继续向上循环更新，直到根结点。下面我们来看一下代码实现：

bool Insert(const pair<K, V>& kv)
{
    //正常的插入操作
    if (_root == nullptr)
    {
        _root = new Node(kv);
        return true;
    } 
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        } 
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        } 
        else
        {
            return false;
        }
    }
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    } 
    else
    {
        parent->_left = cur;
    } 
    cur->_parent = parent;
  	
    // 插入完成后更新平衡因⼦
    while (parent)
    {
        // 更新平衡因⼦
        if (cur == parent->_left)
            parent->_bf--;
        else
            parent->_bf++;
        //更新后进行判断，选择接下来的操作
        if (parent->_bf == 0)
        {
            // 更新结束
            break;
        } 
        else if (parent->_bf == 1 || parent->_bf == -1)
        {
            // 继续往上更新
            cur = parent;
            parent = parent->_parent;
        } 
        else if (parent->_bf == 2 || parent->_bf == -2)
        {
            // 不平衡了，旋转处理
            break;
        } 
        else
        {
            //如果平衡因子有其他情况，说明这棵树在插入之前就存在问题，加入断言可以在程序出错后快速定位
            assert(false);
        }
    } 
    return true;
}

• 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
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71

4. 旋转

上面在更新平衡因子时，当我们的树不平衡时需要通过旋转操作来使我们的树重新变为平衡，由此可见旋转是AVL树的重中之重，也是AVL树的根基，是AVL树之所以能够平衡的原因。

4.1 旋转的目标：

• 把parent⼦树旋转平衡。
• 降低parent⼦树的⾼度

同时旋转后也需要保持搜索树的规则。

针对不同的情况，我们的旋转一共分为四种：右单旋、左单旋、右左双旋，左右双旋。下面让我们看分别看一下这些旋转操作的原理以及如何实现。

下面我们先来看一棵AVL树：

在上图中，a、b、c为是三棵子树且均为AVL树，我们把它们抽象为一个个整体式为了方便旋转的进行，这是因为在进行右单旋时我们只需要用到这三棵子树的第一个结点，其他的结点不会影响我们的右单旋操作。这里可以看到a、b、c这三颗子树的高度都是相同的，都为h，可能大家会对此感到疑惑，如果不都为h呢？上图只是AVL树的一种情况，随着我们的讲解相信可以解答你的疑惑。

4.2 右单旋

对于上图的AVL树，我们新插入一个结点，如果这个结点大于10，往右边走，那么b子树的高度可能不变也可能加一，如下图所示：

我们假设b子树是箭头所指的那棵树，高度为3，那么当我们插入数据时这个结点可能存在的位置有七种情况，我们可以看到在这七种情况中有六种情况b子树的高度加一，一种情况b子树的高度不变，不论高度是否加一通过更新平衡因子后我们都可以发现并不会出现不平衡的情况，也就是说如果插入的结点在b子树下，那么就不需要进行旋转，因为它已经是平衡的了。

那么当插入的数据在a子树并且a子树的高度加一，那么就会导致10这个结点的平衡因子更新为-2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树左边太⾼了，需要往右边旋转，也就是进行右单旋，控制两棵树的平衡，如下图所示：

从上图我们也能看出，当parent的平衡因子为-2，parent->left的平衡因子为-1时，我们需要进行右单旋。右单旋的具体操作步骤如下（以上图为例）：

• 1、把b变为10的左子树
• 2、10变成5的右子树
• 3、5成为这棵树新的根
• 4、旋转完成后的平衡因子只需要把5和10的改为0即可

旋转后的结果如下图所示：

因为5 < b⼦树的值 < 10，将b变成10的左⼦树，10变成5的右⼦树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前这棵树是⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。

下面我们来看一下右单旋的代码实现：

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	//当旋转的为子树时方便旋转进行链接
	Node* Pparent = parent->_parent;

	parent->_left = subLR;
	//subLR也有可能是一个空树
	if(subLR)
		subLR->_parent = parent;

	subL->_right = parent;
	parent->_parent = subL;

	// parent有可能是整棵树的根，也可能是局部的⼦树
	// 如果是整棵树的根，要修改_root
	// 如果是局部的指针要跟上⼀层链接
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (parent = Pparent->_left)
		{
			Pparent->_left = subL;
		}
		else
		{
			Pparent->_right = subL;
		}
		subL->_parent = Pparent;
	}

	//更新平衡因子
	parent->_bf = 0;
	subL->_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
• 39
• 40

4.3 左单旋

左单旋的使用场景与右单旋刚好相反，当最右子树的高度高于左边时，我们要进行左单旋。

也就是a子树的高度加一时，我们要进行左单旋，这时a子树是右子树从上图我们也能看出，当parent的平衡因子为2，parent->right的平衡因子为1时，我们需要进行左单旋。左单旋的具体操作步骤如下（以上图为例）：

• 1、把b变为10的右子树
• 2、10变成15的左子树
• 3、15成为这棵树新的根
• 4、旋转完成后的平衡因子只需要把10和15的改为0即可

旋转后的结果如下图所示：

因为10 < b⼦树的值 < 15，将b变成10的右⼦树，10变成15的左⼦树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。

下面我们来看一下左单旋的代码实现：

void RoteteL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subL->_left;
	//当旋转的为子树时方便旋转进行链接
	Node* Pparent = parent->_parent;

	parent->_right = subRL;
	//subRL也有可能是一个空树
	if (subRL)
		subRL->_parent = parent;

	subL->_left = parent;
	parent->_parent = subR;

	// parent有可能是整棵树的根，也可能是局部的⼦树
	// 如果是整棵树的根，要修改_root
	// 如果是局部的指针要跟上⼀层链接
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parent = Pparent->_left)
		{
			Pparent->_left = subR;
		}
		else
		{
			Pparent->_right = subR;
		}
		subR->_parent = Pparent;
	}

	//更新平衡因子
	parent->_bf = 0;
	subR->_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
• 39
• 40

左单旋和右单旋的思路是一致的，我们可以把它们看作互为镜像，一个用于最左子树高于右子树的情况，一个用于最右子树高于左子树的情况。

4.4 左右双旋

在下图中，如果a子树的高度加一，我们要进行右单旋，那么如果是b子树的高度的高度加一呢？

下面让我们来看一看如果是b子树的高度加一通过右单旋还能否解决我们的问题：

通过上图我们可以看到再对其进行右单旋后5的平衡因子变为了2，还是处于不平衡状态，右单旋并不能解决我们的问题，那么对于parent的平衡因子为-2，parent->left的平衡因子为1时，我们需要通过左右双旋去解决。

左右双旋，顾名思义，进行两次旋转，先进行左单旋，再进行右单旋。

右单旋解决的纯粹的左边⾼，但是插⼊在b⼦树中，10为跟的⼦树不再是单纯的左边⾼，对于10是左边⾼，但是对于5是右边⾼，需要⽤两次旋转才能解决，以5为旋转点进⾏⼀个左单旋，以10为旋转点进⾏⼀个右单旋，这就叫做左右双旋，这样这棵树就平衡了。

对于这种情况，我们需要先以5为旋转点进行左单旋，然后再以10为旋转点进行右单旋。这时我们需要再将b子树近一步进行拆解，以便进行左单旋，如下图所示：

我们将b子树分为一个结点以及这个结点的左右子树e、f，我们假设这个结点的值为8。8的左右子树的高度都为h-1.当我们插入一个结点到b子树中时，它有可能在e子树下，使e子树的高度加一，也有可能在f子树下，使f子树的高度加一，我们需要分类讨论这是因为不同的位置会导致旋转完成之后更新的平衡因子不同。

从上图我们可以看到，新增的结点在e子树下和在f子树下会导致最后5和10结点的平衡因子不同，因此我们在进行左右双旋之前要先记录8位置的平衡因子，方便旋转完后正确的更新平衡因子。

下面我们来将上图中第一中情况的旋转步骤详细地给大家画出来，方便大家理解：

除此之外还有一种特殊情况，也就是a、b、c三棵子树的高度为0，也就是都为空树时：

这种情况也是先对5进行左旋，然后对10进行右旋，步骤是一样的，不同的地方在于平衡后5和10结点的平衡因子都变为0。总的来说要进行左右旋转的情况是parent的平衡因子为-2，parent->left的平衡因子为-1，此外我们还需要记录parent->left->right的平衡因子，以便更新对应结点平衡后的平衡因子。

下面让我们来看一下代码演示，双旋的思路虽然不太好想，但是代码很好写，只需要复用我们之前写过的左单旋和右单旋即可：

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	//记录旋转之前的平衡因子
	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	//旋转之前平衡因子为0说明a、b、c子树为空树
	if (bf == 0)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	//为-1说明f子树增高
	else if (bf == -1)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 1;
	} 
	//为1说明e子树增高
	else if (bf == 1)
	{
		subL->_bf = -1;
		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
• 32
• 33
• 34
• 35
• 36
• 37

4.5 右左双旋

与左右双旋相同，右左双旋是用于解决左单旋无法解决问题的时候，也就是说新插入的元素使b子树的高度加一，观察下图：

至于为什么要进行右左双旋与上面进行左右双旋的原因是一样的，这里就不再赘述。与左右双旋刚好相反，右左双旋的操作是先以15（以上图为例）为旋转点进行右单旋，然后以10为旋转点进行左单旋即可。

和左右双旋一样，我们要先将b子树进行进一步拆解，以便进行右单旋。对于旋转后相应结点的平衡因子更新我们也需要提前记录b子树根节点的平衡因子。下面来让我们直接看其中一种情况的具体旋转过程：

下面我们来看一下具体的代码实现：

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	//记录旋转之前的平衡因子方便后续更新
	int bf = subRL->_bf;

	//进行旋转
	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 0)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		subRL->_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
• 32
• 33
• 34

4.6 旋转小结

上面四种旋转情况便能解决我们在AVL树中遇到不平衡的问题，下面我们来做一个总结，看一看在什么情况下用哪种旋转：

• 右单旋：parent的平衡因子为-2，parent->left的平衡因子为-1
• 左单旋：parent的平衡因子为2，parent->right的平衡因子为1
• 左右单旋：parent的平衡因子为-2，parent->left的平衡因子为1
• 右左单旋：parent的平衡因子为2，parent->right的平衡因子为-1

5 . AVL的其他功能

其实对于AVL树来说，最重要的功能就是旋转，只要我们掌握了旋转，那么就可以说我们掌握了AVL树。AVL树的查找操作与普通的二叉搜索树基本上一模一样，它的插入和删除操作与普通的二叉搜索树相比都是只多了更新平衡因子的操作，在平衡因子更新后不合法时对其进行旋转。具体的代码这里都不再一一进行详细介绍，大家可以自己去尝试写出来。

那么我们该如何检查一棵AVL树是否合格呢？相信大家可能会说可以通过判断平衡因子来检测，但如果平衡因子也出现异常了呢？因此我们需要通过检查左右⼦树⾼度差的的程序进⾏反向验证，同时检查⼀下结点的平衡因⼦更新是否出现了问题。

int _Height(Node* root)
{
    if (root == nullptr)
        return 0;
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

bool _IsBalanceTree(Node* root)
{
    // 空树也是AVL树
    if (nullptr == root)
        return true;
    // 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;
    // 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者
    // pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树
    if (abs(diff) >= 2)
    {
        cout << root->_kv.first << "⾼度差异常" << endl;
        return false;
    } 
    if (root->_bf != diff)
    {
        cout << root->_kv.first << "平衡因⼦异常" << endl;
        return false;
    } 
    // pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

• 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

大家如果感兴趣可以自己去尝试写一下AVL树的插入和删除操作的代码。那么本章到此就结束了，希望大家能够领悟旋转的奥妙。

尾声

若有纰漏或不足之处欢迎大家在评论区留言或者私信，同时也欢迎各位一起探讨学习。感谢您的观看！