在上一篇C++博客中，讲述了关于搜索二叉树以及KVL树的实现。也提到了搜索二叉树的最坏情况：插入的数据已经有序。

而本篇博客涉及到的AVL树，又称平衡搜索二叉树。就是为了解决搜索二叉树的最坏情况而生的。

[TOC]

1. 什么是AVL树

二叉搜索树虽然缩短了查找的效率，但是数据有序的时候，就会出现一边非常长的情况，导致原本的O(logN)时间复杂度被迫变成了O(N)

平衡树也是搜索二叉树，其引入了一个平衡因子的概念，用于控制搜索二叉树的平衡。它会保证左右子树的高度之差（绝对值）不超过1。当新插入节点导致高度之差超过1时，便会触发旋转，使得树的高度降低。

简单说来：AVL树能保证两边高度的相对平衡，这样就稳定了二叉搜索树的效率

1.1 二叉搜索树的性质

一颗AVL树或空树，其有以下性质

  • 它的左右子树是AVL树
  • 左右子树的高度之差的绝对值不超过1

这里引入平衡因子来方便我们控制二叉树的高度。每一个节点都会有一个平衡因子，它的值是1/0/-1。如果平衡因子的值超过了1，那么说明这个节点的子树已经不平衡，需要进行旋转。

实际上，AVL树不一定非要用平衡因子。我们可以用计算树的高度的方式来确认平衡因子，但是这样需要遍历左右子树，时间复杂度较高

2. 实现一颗AVL树

2.1 AVL树的节点

基本的概念理解之后，我们需要设计出一个节点的结构来。关于各个值的含义，可以参考下方的注释

平衡搜索二叉树是一个“三叉链”。这代表每一个节点都有左右孩子，还有一个prev指针指向它的父节点。
为了标识树是否平衡，准确来说是某个节点的左右子树是否平衡。我们需要引入一个“平衡因子”来进行判断，方便我们控制平衡

  • 左右子树高度相同 0
  • 左子树高于右子树 -1
  • 右子树高于左子树 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class K,class V>
struct AVLTreeNode
{
	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)
	{}
};

关于键值对的内容，在上篇博客的KVL树中有提到过 【传送门】

2.2 AVL树的插入（重要）

因为AVL需要控制树的高度，其插入的时候就没有KVL树那么方便了。我们每次插入之后，都需要向上更新并判断树的平衡因子是否正常

先来理清一下思路:

  • 如果是空树，new一个新节点交给root，无需进行后续操作
  • 插入新节点的时候，利用搜索二叉树的规则（在这里我采用了左小右大的规则）来找到新节点应该插入的位置，直接进行插入
  • 插入之后，需要向上更新平衡因子（利用父节点parent）
    • 如果该插入节点在父节点的右边，平衡因子+1
    • 如果在该节点的左边，平衡因子-1。
  • 更新了平衡因子之后，需要及时进行判断。如果平衡因子等于0，则不需要继续往上更新。如果平衡因子的绝对值大于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
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
bool Insert(const pair<K, V>& kv)
{
	//判断root为空，即空树
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	//kv树的操作
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
           //利用key来判断，寻找待插入的位置
		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--;//左-1
		}
		else{
			parent->_bf++;//右+1
		}

		//更新了之后，需要判断是否继续更新，还是需要旋转
		if (parent->_bf == 0) {
			break;//为0代表高度没有变化，不需要继续更新
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = cur->_parent;//向上更新
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//旋转
		}
		else
		{
			//插入之前AVL就存在不平衡子树
			assert(false);
		}
	}
	return true;
}

其中最复杂的部分：旋转，需要拿出来单独讲解一番

下面是一个最简单的二叉树进行插入之后，平衡因子的变化。

image-20220902084054319

因为搜索二叉树需要保证两边的高度之差不大于1，所以此时我们的树还没有违背AVL树的规则。

可如果我们继续往右子树插入节点呢？

image-20220902084701660

可以看到，最后一颗子树的根节点的平衡因子为2，超过了1。此时两边子树的高度差为2，需要我们进行旋转操作

2.2.1 左/右单旋

为了简化，我们把上图的插入情况直接简化为下面的样子

image-20220902091330994

当我们在这棵树高度较高的那一侧的边缘插入的时候，就需要进行单旋。

比如右边高，就是在最右边的叶子处插入时需要进行单旋

单旋的思路很好理解，下面以左单旋为例（蓝色代表新增节点）

image-20220902092039209

这里我们设置了3个不同的节点，分别是prev起始节点（即平衡因子大于1的节点）以及它的右子树subR、右子树的左子树subRL（即图中的b子树）

  • 需要做的操作，就是把subRL链接给prev的右，再将prev链接到subR的左
  • 因为subRL在prev的右侧，其的值肯定大于prev，所以这样链接是不会破坏搜索二叉树的结构的。

旋转完成之后，我们需要把prev和subR的平衡因子都更新为0

image-20220902092439301

右单旋的操作和左单旋的思路完全相同，只不过方向相反

image-20220902092819728

思路搞定了，下面就来写一个代码吧！

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
void RotateL(Node* parent)//左单旋
{
    Node* prev = parent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    //用来记录当前parent的父亲，最后的链接需要
    Node* ppNode = parent->_parent;

    prev->_right = subRL;
    if (subRL != nullptr)
    {//不为空才能进行parent操作
        subRL->_parent = prev;
    }

    subR->_left = prev;
    prev->_parent = subR;

    if (prev == _root)
    {//单独操作为根节点的情况
        //subR->_parent = nullptr;
        _root = subR;
        _root->_parent = nullptr;
    }
    else
    {
        if (prev == ppNode->_left) {
            ppNode->_left = subR;
        }
        else {
            ppNode->_right = subR;
        }
        subR->_parent = ppNode;
    }
    //默认全都改成0
    subR->_bf = parent->_bf = 0;
}

右单旋的代码和这个类似，这里就不贴出来了

完整代码可以到我的代码仓库里面看哦！【Gitee】

旋转的代码写好了，我们现在还需要了解的是，什么时候需要进行单旋？

看图可以得知，当prev的平衡因子为-2，subL的平衡因子为-1的时候，需要进行一次右单旋

image-20220902093150517

同理，我们可以推断出一个结论，那就是当父节点的平衡因子的绝对值超过1，其左/右边节点的平衡因子为1且和父节点平衡因子的正负相同时，需要向另外一个方向进行单旋。

左单旋就是父节点为2，其右子树为1，需要向另外一个方向左进行单旋

image-20220902093230892

需要注意的是，虽然图里面画出来的prev是根节点，但实际上进行单旋的时候，prev可能是另外一棵树的子树。在单旋的处理过程中，我们必须要保存prev的父节点，并重新链接至subR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//插入函数的旋转部分
else if (parent->_bf == 2 || parent->_bf == -2)
{
    if (parent->_bf == 2 && cur->_bf == 1)
    {
        RotateL(parent);
    }
    else if (parent->_bf == -2 && cur->_bf == -1)
    {
        RotateR(parent);
    }
    else
    {
        //……
    }
    break;
}

我们用下面的代码进行测试

1
2
3
4
5
6
7
8
9
10
11
void TestAVLTree1()
{
	int a[] = {9,8,7,6,5,4,3,2,1 };
	AVLTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder();
	cout << endl;
}

进行中序打印，可以获取道下面的结果。可以看到数据已经有序

image-20220902094425851

在VS2019的调试窗口中可以看到，我们厂家的这棵树是符合平衡搜索二叉树的性质的

image-20220902100112708

2.2.2 左右/右左双旋

上面的情况还算容易，一次单旋就能解决。那如果我们插入不有序的数据呢？

image-20220902101420472

可以看到中序打印的结果已经有序，可它符合平衡二叉树的规则吗？

再插入一个25，会发现触发了断言，说明AVL树的规则被破坏了

image-20220902101613552

就好比下面的这种情况，我们是以15 6 7这种非有序方式插入的，就会出现单旋完全处理不了的情况

image-20220902102026424

如果进行单旋会发生什么呢？

image-20220902102310629

可以看到，毫无变化。旋转了之后的节点依旧是违反AVL树的规则

这时候我们就需要进行两次循环了！

24-03-27备注：下图中的节点应该有问题，左下角的图中30和10的位置应该更换，右下角的图中，30应该是根，10是右子树，20是左子树。

image-20220902103954597

概念理解了之后，我们就可以直接来写代码了。

因为本质上就是两次单旋，所以我们可以直接复用之前写好的单旋代码

1
2
3
4
5
void RotateLR(Node* parent)//左右
{
    RotateL(parent->_left);
    RotateR(parent);
}

但事情远没有这么简单！

在2.2.1单旋的操作中，我们旋转完毕后会把prev和subL的平衡因子都改成了0。在这种双旋的情况下，全改成0显然不符合要求。

下面的情况，我们就需要在旋转之后，把10的平衡因子改成-1，20和30的平衡因子改成0

image-20220902111921478

双旋的情况分为下面3种，我们可以直接用紫色框中所指的这个节点来判断属于哪一种情况，再针对性的处理！

image-20220902112541439

处理之后的结果如下

image-20220902123920234

其代码逻辑如下

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
//这种双旋转的情况，基本如下
//   9
// 7
//   8
//必须要双旋转才能解决问题
void RotateLR(Node* parent)//左右
{
    Node* prev = parent;
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

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

    if (bf == 0)
    {
        prev->_bf = 0;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == 1)
    {
        subL->_bf = -1;
        prev->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == -1)
    {
        subL->_bf = 0;
        prev->_bf = 1;
        subLR->_bf = 0;
    }
    else {
        assert(false);
    }
}
void RotateRL(Node* parent)//右左
{
    Node* prev = parent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

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

    if (bf == 0)
    {
        prev->_bf = 0;
        subR->_bf = 0;
        subRL->_bf = 0;
    }
    else if (bf == -1)
    {
        subR->_bf = 1;
        prev->_bf = 0;
        subRL->_bf = 0;
    }
    else if (bf == 1)
    {
        subRL->_bf = 0;
        subR->_bf = 0;
        prev->_bf = -1;
    }
    else {
        assert(false);
    }

}

到这里我们就可以把插入函数给补全了！

完整代码可以到我的代码仓库里面看哦！【Gitee】

还是刚刚的测试用例，这一次我们可以看到，它已经没有报错了！

image-20220902124116488

2.3 AVL树的搜索

本质上AVL树还是一个平衡二叉树，所以搜索肯定是少不了的！

它的搜索和KVL树完全一致，利用key来进行搜索，定位value。

所以，我们可以直接搬过来用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//因为kvl树我们需要修改value，所以返回节点的指针
Node* _FindR(Node* root, const K& key)
{
	if (root == nullptr)
		return nullptr;

	if (root->_kv.first < key)
	{
		return _FindR(root->_right, key);
	}
	else if (root->_kv.first > key)
	{
		return _FindR(root->_left, key);
	}
	else
	{
		return root;//返回节点的指针
	}
}

上面的这个函数我们定义为私有，在公有里面定义一个下面的函数

1
2
3
4
5
//查找是通过key来进行的
Node* FindR(const K& key)
{
	return _FindR(_root, key);
}

测试一下可以看到，打印了全0的地址值，即nullptr，说明没有找到34

image-20220902100707399

2.4 如何判断是否符合AVL树的性质

如果每一次我们都要用调试去看当前的代码是否符合二叉树的性质，未免有些太麻烦了

下面我们有两种办法来简洁地判断！

2.4.1 层序遍历（OJ题）

下面的代码是一道OJ题的答案，其要求是让我们把树每一层的节点都插入一个vector，最后返回的是一个嵌套的vector<vector<int>>

来自 https://leetcode.cn/problems/binary-tree-level-order-traversal/

因为我们当前测试的用例都是int类型，所以这里就没有用模板参数。实际上我们应该改成key的类型

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
vector<vector<int>> levelOrder() 
{
	vector<vector<int>> vv;
	if (_root == nullptr)
		return vv;

	queue<Node*> q;
	int levelSize = 1;
	q.push(_root);

	while (!q.empty())
	{
		// levelSize控制一层一层出
		vector<int> levelV;
		while (levelSize--)
		{
			Node* front = q.front();
			q.pop();
			levelV.push_back(front->_kv.first);
			if (front->_left)
				q.push(front->_left);

			if (front->_right)
				q.push(front->_right);
		}
		vv.push_back(levelV);
		for (auto e : levelV)
		{
			cout << e << " ";
		}
		cout << endl;

		// 上一层出完，下一层就都进队列
		levelSize = q.size();
	}

	return vv;
}

测试一下，可以看到每一层的结果，符合我们AVL树的性质

2.4.2 检查平衡因子

这里我们用两个递归函数，通过计算子树的高度，来判断是否满足AVL树的性质。

只要两个子树的高度差大于1，就说明不是AVL树

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
//计算高度
int _Height(Node* root)
{
    if (root == nullptr)
        return 0;

    int lh = _Height(root->_left);
    int rh = _Height(root->_right);
    //如果左子树高于右子树，就返回左子树+1（根）
    return lh > rh ? lh + 1 : rh + 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 (diff != root->_bf)
    {
        cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
        return false;
    }

    // pRoot的左和右如果都是AVL树，则该树一定是AVL树
    return _IsBalanceTree(root->_left)
        && _IsBalanceTree(root->_right);
}

image-20220902125132955

2.5 利用随机值和顺序值进行测试

下面我们分别利用随机值和顺序值测试AVL树的正确性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void TestAVLTree2()
{
	const size_t N = 1024*1024;
	vector<int> v;
	v.reserve(N);
	srand(time(0));//使用随机数
	for (size_t i = 0; i < N; ++i)
	{
		v.push_back(rand());
		//v.push_back(i);
	}

	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}

	cout << "是否平衡?" << t.IsBalanceTree() << endl;
	cout << "高度:" << t.Height() << endl;
}

利用随机数测试的结果如下

image-20220902125239411

顺序插入的结果如下

image-20220902125303975

没有问题辣！

2.6 AVL树的删除

AVL树的删除和KVL树是基本相同的，但是我们需要更新平衡因子。

  • 如果删除的是左节点，平衡因子+1
  • 如果删除的是右节点，平衡因子-1

当我们遇到平衡因子错误（绝对值大于1）就需要进行旋转

因为搜索树中一般不会进行删除，效率很低，所以这里就不写了！（懒）

2.7 二叉树性能

在一些时候，搜索二叉树的性能并不会很高

  • 比如当我们插入的元素已经有序，或者基本有序的时候，二叉树的性能就和普通的容器差距不大了
  • AVL树更适合于插入的元素不会被改变的情况。如果插入的元素需要经常被修改，那么也不太适合。（比如删除的时候，AVL树的平衡因子可能需要一直向上到根，时间复杂度不亚于二次插入）

结语

那么本篇关于AVL树的博客到这里就结束拉！

有什么问题欢迎在评论区提出哦！

QQ截图20220421112054