【C++】AVL树(平衡搜索二叉树)
慕雪年华

在上一篇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

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

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

image

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

2.2.1 左/右单旋

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

image

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

比如右边高,就是在最右边的叶子处插入

单旋的思路很好理解,下面以左单旋为例(蓝色代表新增节点)

image

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

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

旋转完成之后,我们需要把prevsubR的平衡因子都更新为0

image

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

image


思路搞定了,下面就来写一个代码吧!

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

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

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

image

需要注意的是,虽然图里面画出来的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

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

image


2.2.2 左右/右左双旋

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

image

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

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

image

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

image

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

image

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

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

image

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

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

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

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

image

处理之后的结果如下

image

其代码逻辑如下

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


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

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树的性质

image

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


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

顺序插入的结果如下

image

没有问题辣!

2.6 AVL树的删除

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

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

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

因为搜索树中一般不会进行删除,效率很低,所以这里就不写了!(懒)

2.7 二叉树性能

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

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

结语

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

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

image