【C++高阶(三)】AVL树深度剖析&模拟实现

💓博主CSDN主页:杭电码农-NEO💓
 
⏩专栏分类:C++从入门到精通⏪
 
🚚代码仓库:NEO的学习日记🚚
 
🌹关注我🫵带你学习C++
  🔝🔝

---

---

1. 前言

如果你不知道什么是二叉搜索树
请一定先阅读这篇文章:

二叉搜索树深度剖析

二叉搜索树如果插入顺序是有序的
那么这棵树的查找效率将会是O(N)
所以说在实际情况下,二叉搜索很少被使用
1
2
3

为了解决二叉搜索树不稳定的问题
于是乎有人提出了AVL树结构,也就是
高度平衡二叉搜索树!

本章重点:

本篇文章着重讲解AVL树的概念以及
定义,并且在模拟实现AVL树前,将AVL
树的插入的情况做系统分析,最后模拟
实现AVL树的插入操作,进一步理解它!

---

2. AVL树的概念以及特性

AVL树通过一个特性来保证二叉
搜索的平衡性问题: 那就是任一
节点两边的子树高度差不超过1!

高度差一般是右子树高度减左子树高度

由于AVL树的这种特殊性质,使得它的
查找效率是百分百的O(logn),可以说
这是天才的发明,当插入或删除节点时,
高度差不符合要求后,可以通过旋转的
方式来重新让这棵树变成AVL树!

下面,我们一般尝试理解AVL树
一边来模拟实现它!

---

3. AVL树模拟实现基本框架

首先我们应该想到一点,当高度差
大一1时我们需要做处理,但是我们
怎么知道哪个节点高度差大于1呢?
因此应该在节点中多定义一个整数
来记录当前节点的左右高度差!

AVL树的节点结构体:

template<class K, class V>
struct AVLTreeNode   //高度平衡二叉搜索树
{
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
	//用三叉链,方便更新祖先的平衡因子
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv; //存储的数据
	int _bf; //balance factor平衡因子
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

有了节点的结构体后,定义一下
AVL树的基本结构吧:

template<class K,class V>
struct AVLTree
{
	typedef AVLTreeNode<K, V> Node;
private:
	Node* _root;//定义一个根节点
};
1
2
3
4
5
6
7

---

4. AVL树插入函数深度剖析

AVL数的插入有三个步骤:

1. 按照二叉搜索树规则插入节点
2. 插入完成后更新平衡因子
3. 若平衡因子不正确需要采取措施

所以当前目标就是把这三步搞清楚

更新平衡因子规则:

1. 新增在右,父亲的bf加一
   新增在左,父亲的bf减一

2. 更新完成后,父亲的bf==1/-1,说明
   父亲插入前的bf一定是0,并且插入后
   一边高一边低,需要继续向上更新

3. 更新完成后,父亲的bf==0,说明父亲
   在插入前的bf是1/-1,并且插入后两边高度
   一致,就不需要继续往上更新了!

4. 更新完成后,父亲的bf==2/-2,打破
   了平衡,父亲所在的子树要旋转处理

由于旋转处理的过程比较复杂
所以先将除了旋转的所有代码写出来
后再去讨论旋转的话题!

---

5. AVL树插入代码剖析(无旋转)

话不多说,直接上手!

bool insert(const pair<K, V>& kv)//第一步:按照二叉搜索树的方式插入值,第二步:调整平衡因子后旋转
	{
		if (_root == nullptr)//插入第一个节点时
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		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;
		//此时new出来的节点的parent还指向空
		cur->_parent = parent;

		//插入完成后,此时需要查看平衡因子来控制平衡
		//沿着插入的位置往上更新平衡因子 
		while (parent)//由于parent需要不断向上更新,所以要使用循环!
		{
			if (cur == parent->_right)
				parent->_bf++;
			else
				parent->_bf--;
			if (parent->_bf == 0)//不用向上更新了
				break;
			else if (parent->_bf == 1 || parent->_bf == -1)//若高度出现变化,需要往上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)//说明parent所在的子树不平衡了,需要旋转处理
			{
				//后面再处理这个过程......
			}
		}
}
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

关于代码的解释都在注释中,请耐心查看!

---

6. AVL树的旋转操作深度剖析(一)

首先,旋转一共由四种情况,不管是
哪一种情况,我们的目的都是将原本
不平衡的树变成符合规则的AVL树!

先看两个最简单的例子:

左单选和右单旋:

大概了解了它的规则后,再来看泛型的:

1. 右单旋
   
2. 左单旋:
   

---

7. AVL树的旋转操作深度剖析(二)

当你了解了前两种最简单的情况后
就可以来看看"双旋"操作了!

还是先看看最简单的例子:

先左旋再右旋
先右旋再左旋

了解了最简单了例子后,直接上手!

---

8. AVL树旋转的代码实现

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	Node* ppNode = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
			ppNode->_left = subR;
		else
			ppNode->_right = subR;
		subR->_parent = ppNode;
	}

	subR->_bf = parent->_bf = 0;
}
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	Node* ppNode = parent->_parent;
	subL->_right = parent;
	parent->_parent = subL;
	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
			ppNode->_left = subL;
		else
			ppNode->_right = subL;
		subL->_parent = ppNode;
	}
	subL->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;
	RotateL(parent->_left);
	RotateR(parent);
	subLR->_bf = 0;
	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
	}
	else assert(false);
}
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	RotateR(parent->_right);
	RotateL(parent);
	subRL->_bf = 0;
	if (bf == 1)
	{
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subR->_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
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

你问我我怎么写出代码的?
那是一段痛苦的回忆,代码的验证就交给你们了
代码中对于平衡因子的更新有细节!

---

9. 总结以及所有代码

AVL树的模拟实现属于了解的内容
并不需要完全掌握,所以同学了只需
理解了AVL树的旋转即可,不要求手撕代码!
(当然前几年有学长面试时被要求手撕了doge)

AVL树模拟实现全部代码:

我的gitee仓库

---

🔎 下期预告:红黑树树深度剖析 🔍