AVL树（动图详解）

AVL树的概念

二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的。

因此，两位俄罗斯的数学家G.M.A delson-Velskii和E.M.Landis在1962年发明了解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。

AVL树可以是一棵空树，也可以是具有以下性质的一棵二叉搜索树：

1. 树的左右子树都是AVL树。
2. 树的左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/01）。

如果一棵二叉搜索树的高度是平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(logN)$，搜索时间复杂度也是$O(logN)$。

注意： 这里所说的二叉搜索树的高度是平衡的是指，树中每个结点左右子树高度之差的绝对值不超过1，因为只有满二叉树才能做到每个结点左右子树高度之差均为0。

AVL树结点的定义

我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。

template<class K, class V>
struct AVLTreeNode
{
	//三叉链
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	//存储的键值对
	pair<K, V> _kv;

	//平衡因子(balance factor)
	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
21
22
23

注意： 给每个结点增加平衡因子并不是必须的，只是实现AVL树的一种方式，不引入平衡因子也可以实现AVL树，只不过会麻烦一点。

AVL树的插入

AVL树插入结点时有以下三个步骤：

1. 按照二叉搜索树的插入方法，找到待插入位置。
2. 找到待插入位置后，将待插入结点插入到树中。
3. 更新平衡因子，如果出现不平衡，则需要进行旋转。

因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：

1. 待插入结点的key值比当前结点小就插入到该结点的左子树。
2. 待插入结点的key值比当前结点大就插入到该结点的右子树。
3. 待插入结点的key值与当前结点的key值相等就插入失败。

如此进行下去，直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入。

与二叉搜索树插入结点不同的是，AVL树插入结点后需要更新树中结点的平衡因子，因为插入新结点后可能会影响树中某些结点的平衡因子。

由于一个结点的平衡因子是否需要更新，是取决于该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的祖先结点的平衡因子可能需要更新。

所以我们插入结点后需要倒着往上更新平衡因子，更新规则如下：

1. 新增结点在parent的右边，parent的平衡因子$++$。
2. 新增结点在parent的左边，parent的平衡因子$--$。

每更新完一个结点的平衡因子后，都需要进行以下判断：

• 如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子。
• 如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了。
• 如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理。

判断理由说明：

而在最坏情况下，我们更新平衡因子时会一路更新到根结点。例如下面这种情况：

说明一下： 由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新。当然，我们也可以不用三叉链结构，可以在插入结点时将路径上的结点存储到一个栈当中，当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子，但是相对较麻烦。

若是在更新平衡因子的过程当中，出现了平衡因子为-2/2的结点，这时我们需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行以下分析：

我们将插入结点称为cur，将其父结点称为parent，那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，那么我们必定要执行以下逻辑：

cur = parent;
parent = parent->_parent;
1
2

这里我想说明的是：当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。

理由如下：
若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。
而cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：

1. 其父结点是一个左右子树均为空的叶子结点，其平衡因子是0，新增结点插入后其平衡因子更新为-1/1。
2. 其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。

综上所述，当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。

根据此结论，我们可以将旋转处理分为以下四类：

1. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
2. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
3. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。
4. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。

并且，在进行旋转处理后就无需继续往上更新平衡因子了，因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了。具体原因请看后面的旋转讲解。

代码如下：

//插入函数
bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) //若AVL树为空树，则插入结点直接作为根结点
	{
		_root = new Node(kv);
		return true;
	}
	//1、按照二叉搜索树的插入方法，找到待插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
		{
			//往该结点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
		{
			//往该结点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else //待插入结点的key值等于当前结点的key值
		{
			//插入失败（不允许key值冗余）
			return false;
		}
	}

	//2、将待插入结点插入到树中
	cur = new Node(kv); //根据所给值构造一个新结点
	if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
	{
		//插入到parent的左边
		parent->_left = cur;
		cur->_parent = parent;
	}
	else //新结点的key值大于parent的key值
	{
		//插入到parent的右边
		parent->_right = cur;
		cur->_parent = parent;
	}

	//3、更新平衡因子，如果出现不平衡，则需要进行旋转
	while (cur != _root) //最坏一路更新到根结点
	{
		if (cur == parent->_left) //parent的左子树增高
		{
			parent->_bf--; //parent的平衡因子--
		}
		else if (cur == parent->_right) //parent的右子树增高
		{
			parent->_bf++; //parent的平衡因子++
		}
		//判断是否更新结束或需要进行旋转
		if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
		{
			break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
		}
		else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子
		{
			//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了）
		{
			if (parent->_bf == -2)
			{
				if (cur->_bf == -1)
				{
					RotateR(parent); //右单旋
				}
				else //cur->_bf == 1
				{
					RotateLR(parent); //左右双旋
				}
			}
			else //parent->_bf == 2
			{
				if (cur->_bf == -1)
				{
					RotateRL(parent); //右左双旋
				}
				else //cur->_bf == 1
				{
					RotateL(parent); //左单旋
				}
			}
			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
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
102
103

AVL树的旋转

左单旋

动图演示：

动图演示说明：
由于插入新结点后，可能并不会立即进行旋转操作，而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作，因此用长方形表示下面的子树。

旋转示意图如下：

左单旋的步骤如下：

1. 让subR的左子树作为parent的右子树。
2. 让parent作为subR的左子树。
3. 让subR作为整个子树的根。
4. 更新平衡因子。

左单旋后满足二叉搜索树的性质：

1. subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。
2. parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。

平衡因子更新如下：

可以看到，经过左单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左单旋后无需继续往上更新平衡因子。

代码如下：

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* parentParent = parent->_parent;

	//1、建立subR和parent之间的关系
	parent->_parent = subR;
	subR->_left = parent;

	//2、建立parent和subRL之间的关系
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	//3、建立parentParent和subR之间的关系
	if (parentParent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr; //subR的_parent指向需改变
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subR;
		}
		else //parent == parentParent->_right
		{
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}

	//4、更新平衡因子
	subR->_bf = 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

注意： 结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向。

右单旋

动图演示：

动图演示说明：
由于插入新结点后，可能并不会立即进行旋转操作，而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作，因此用长方形表示下面的子树。

旋转示意图如下：

右单旋的步骤如下：

1. 让subL的右子树作为parent的左子树。
2. 让parent作为subL的右子树。
3. 让subL作为整个子树的根。
4. 更新平衡因子。

右单旋后满足二叉搜索树的性质：

1. subL的右子树当中结点的值本身就比parent的值小，因此可以作为parent的左子树。
2. parent及其右子树当中结点的值本身就比subL的值大，因此可以作为subL的右子树。

平衡因子更新如下：

可以看到，经过右单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以右单旋后无需继续往上更新平衡因子。

代码如下：

//右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* parentParent = parent->_parent;

	//1、建立subL和parent之间的关系
	subL->_right = parent;
	parent->_parent = subL;

	//2、建立parent和subLR之间的关系
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;

	//3、建立parentParent和subL之间的关系
	if (parentParent == nullptr)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subL;
		}
		else //parent == parentParent->_right
		{
			parentParent->_right = subL;
		}
		subL->_parent = parentParent;
	}

	//4、更新平衡因子
	subL->_bf = 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

注意： 结点是三叉链结构，改变结点关系时需要跟着改变父指针的指向。

左右双旋

动图演示：

动图演示说明：

1. 由于插入新结点后，可能并不会立即进行旋转操作，而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作，因此用长方形表示下面的子树。
2. 动图中，在b子树当中新增结点，或是在c子树当中新增结点，均会引发左右双旋，动图中以在b子树当中新增结点为例。

动图当中的旋转示意图如下：
1、插入新结点。

2、以30为旋转点进行左单旋。

3、以90为旋转点进行右单旋。

左右双旋的步骤如下：

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

左右双旋后满足二叉搜索树的性质：
左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根（结合图理解）。

1. subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
2. subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
3. 经过步骤1/2后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树。

左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
1、当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。

2、当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。

1、当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。

可以看到，经过左右双旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左右双旋后无需继续往上更新平衡因子。

代码如下：

//左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1

	//1、以subL为旋转点进行左单旋
	RotateL(subL);

	//2、以parent为旋转点进行右单旋
	RotateR(parent);

	//3、更新平衡因子
	if (bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_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

右左双旋

动图演示：

动图演示说明：

1. 由于插入新结点后，可能并不会立即进行旋转操作，而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作，因此用长方形表示下面的子树。
2. 动图中，在b子树当中新增结点，或是在c子树当中新增结点，均会引发右左双旋，动图中以在c子树当中新增结点为例。

动图当中的旋转示意图如下：
1、插入新结点。

2、以90为旋转点进行右单旋。

3、以30为旋转点进行左单旋。

右左双旋的步骤如下：

1. 以subR为旋转点进行右单旋。
2. 以parent为旋转点进行左单旋。
3. 更新平衡因子。

右左双旋后满足二叉搜索树的性质：
右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根（结合图理解）。

1. subRL的左子树当中的结点本身就比parent的值大，因此可以作为parent的右子树。
2. subRL的右子树当中的结点本身就比subR的值小，因此可以作为subR的左子树。
3. 经过步骤1/2后，parent及其子树当中结点的值都就比subRL的值小，而subR及其子树当中结点的值都就比subRL的值大，因此它们可以分别作为subRL的左右子树。

右左双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
1、当subRL原始平衡因子是1时，左右双旋后parent、subR、subRL的平衡因子分别更新为-1、0、0。

2、当subRL原始平衡因子是-1时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、1、0。

3、当subRL原始平衡因子是0时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、0、0。

可以看到，经过右左双旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以右左双旋后无需继续往上更新平衡因子。

代码如下：

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

	//1、以subR为轴进行右单旋
	RotateR(subR);

	//2、以parent为轴进行左单旋
	RotateL(parent);

	//3、更新平衡因子
	if (bf == 1)
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 0)
	{
		subRL->_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

AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，也就是说AVL树也是二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断二叉树是否为二叉搜索树。

代码如下：

//中序遍历
void Inorder()
{
	_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{
	if (root == nullptr)
		return;
	_Inorder(root->_left);
	cout << root->_kv.first << " ";
	_Inorder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但中序有序只能证明是二叉搜索树，要证明二叉树是AVL树还需验证二叉树的平衡性，在该过程中我们可以顺便检查每个结点当中平衡因子是否正确。

采用后序遍历，变量步骤如下：

1. 从叶子结点处开始计算每课子树的高度。（每棵子树的高度 = 左右子树中高度的较大值 + 1）
2. 先判断左子树是否是平衡二叉树。
3. 再判断右子树是否是平衡二叉树。
4. 若左右子树均为平衡二叉树，则返回当前子树的高度给上一层，继续判断上一层的子树是否是平衡二叉树，直到判断到根为止。（若判断过程中，某一棵子树不是平衡二叉树，则该树也就不是平衡二叉树了）

代码如下：

//判断是否为AVL树
bool IsAVLTree()
{
	int hight = 0; //输出型参数
	return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int& hight)
{
	if (root == nullptr) //空树是平衡二叉树
	{
		hight = 0; //空树的高度为0
		return true;
	}
	//先判断左子树
	int leftHight = 0;
	if (_IsBalanced(root->_left, leftHight) == false)
		return false;
	//再判断右子树
	int rightHight = 0;
	if (_IsBalanced(root->_right, rightHight) == false)
		return false;
	//检查该结点的平衡因子
	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子设置异常：" << root->_kv.first << endl;
	}
	//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
	hight = max(leftHight, rightHight) + 1;
	return abs(rightHight - leftHight) < 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
26
27
28
29
30
31

AVL树的查找

AVL树的查找函数与二叉搜索树的查找方式一模一样，逻辑如下：

1. 若树为空树，则查找失败，返回nullptr。
2. 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
3. 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
4. 若key值等于当前结点的值，则查找成功，返回对应结点。

代码如下：

//查找函数
Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (key < cur->_kv.first) //key值小于该结点的值
		{
			cur = cur->_left; //在该结点的左子树当中查找
		}
		else if (key > cur->_kv.first) //key值大于该结点的值
		{
			cur = cur->_right; //在该结点的右子树当中查找
		}
		else //找到了目标结点
		{
			return cur; //返回该结点
		}
	}
	return nullptr; //查找失败
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

AVL树的修改

方法一

实现修改AVL树当中指定key值结点的value，我们可以实现一个Modify函数，该函数当中的逻辑如下：

1. 调用查找函数获取指定key值的结点。
2. 对该结点的value进行修改。

代码如下：

//修改函数
bool Modify(const K& key, const V& value)
{
	Node* ret = Find(key);
	if (ret == nullptr) //未找到指定key值的结点
	{
		return false;
	}
	ret->_kv.second = value; //修改结点的value
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

方法二

还有一种方法就是模仿C++STL库当中map的实现方式，将插入函数的返回值设置为pair类型的，插入函数的返回值逻辑如下：

• 若待插入结点的键值key在map当中不存在，则结点插入成功，并返回插入后结点的指针和true。
• 若待插入结点的键值key在map当中已经存在，则结点插入失败，并返回map当中键值为key的结点的指针和false。

我们只需要对插入函数的返回值做一点点修改即可，代码如下：

//插入函数
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) //若AVL树为空树，则插入结点直接作为根结点
	{
		_root = new Node(kv);
		return make_pair(_root, true); //插入成功，返回新插入结点和true
	}
	//1、按照二叉搜索树的插入方法，找到待插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
		{
			//往该结点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
		{
			//往该结点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else //待插入结点的key值等于当前结点的key值
		{
			//插入失败（不允许key值冗余）
			return make_pair(cur, false); //插入失败，返回已经存在的结点和false
		}
	}

	//2、将待插入结点插入到树中
	cur = new Node(kv); //根据所给值构造一个新结点
	Node* newnode = cur; //记录新插入的结点
	if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
	{
		//插入到parent的左边
		parent->_left = cur;
		cur->_parent = parent;
	}
	else //新结点的key值大于parent的key值
	{
		//插入到parent的右边
		parent->_right = cur;
		cur->_parent = parent;
	}

	//3、更新平衡因子，如果出现不平衡，则需要进行旋转
	while (cur != _root) //最坏一路更新到根结点
	{
		if (cur == parent->_left) //parent的左子树增高
		{
			parent->_bf--; //parent的平衡因子--
		}
		else if (cur == parent->_right) //parent的右子树增高
		{
			parent->_bf++; //parent的平衡因子++
		}
		//判断是否更新结束或需要进行旋转
		if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
		{
			break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
		}
		else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子
		{
			//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了）
		{
			if (parent->_bf == -2)
			{
				if (cur->_bf == -1)
				{
					RotateR(parent); //右单旋
				}
				else //cur->_bf == 1
				{
					RotateLR(parent); //左右双旋
				}
			}
			else //parent->_bf == 2
			{
				if (cur->_bf == -1)
				{
					RotateRL(parent); //右左双旋
				}
				else //cur->_bf == 1
				{
					RotateL(parent); //左单旋
				}
			}
			break; //旋转后就一定平衡了，无需继续往上更新平衡因子(旋转后树高度变为插入之前了)
		}
		else
		{
			assert(false); //在插入前树的平衡因子就有问题
		}
	}

	return make_pair(newnode, true); //插入成功，返回新插入结点和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
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
102
103
104

然后我们再对运算符[ ]进行重载，[ ]的重载逻辑如下：

1. 调用插入函数插入键值对。
2. 拿出从插入函数获取到的结点。
3. 返回该结点value的引用。

这样一来，当我们使用[key]时，其返回值逻辑如下：

• 如果key不在树中，则先插入键值对<key, V()>，然后返回该键值对中value的引用。
• 如果key已经在树中，则返回键值为key结点value的引用。

如此一来，我们既可以用[ ]来进行指定key值结点value的修改，又可以用[ ]进行数据的插入了，并且插入时更方便。

代码如下：

//operator[]重载
V& operator[](const K& key)
{
	//调用插入函数插入键值对
	pair<Node*, bool> ret = Insert(make_pair(key, V()));
	//拿出从插入函数获取到的结点
	Node* node = ret.first;
	//返回该结点value的引用
	return node->_kv.second;
}
1
2
3
4
5
6
7
8
9
10

AVL树的删除

要进行结点的删除，首先需要在树中找到对应key值的结点，寻找待删除结点的方法和二叉搜索树相同：

1. 先找到待删除的结点。
2. 若找到的待删除结点的左右子树均不为空，则需要使用替换法进行删除。

替换法删除指的是：让待删除结点左子树当中key值最大的结点，或待删除结点右子树当中值最小的结点代替待删除结点被删除（代码中以后者为例），然后再将待删除结点的key值以及value值都改为代替其被删除的结点的值即可。

也就是说，我们最终找到的实际被删除的结点的左右子树当中至少有一个为空树。

在找到实际需要被删除的结点后，我们先不进行实际的删除，而是先进行平衡因子的更新，不然后续更新平衡因子时特别麻烦（已经尝试过），而更新平衡因子时的规则与插入结点时的规则是相反的，更新规则如下：

1. 删除的结点在parent的右边，parent的平衡因子$--$。
2. 删除的结点在parent的左边，parent的平衡因子$++$。

并且每更新完一个结点的平衡因子后，都需要进行以下判断：

• 如果parent的平衡因子等于-1或者1，表明无需继续往上更新平衡因子了。
• 如果parent的平衡因子等于0，表明还需要继续往上更新平衡因子。
• 如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理。

判断理由说明：

而在最坏情况下，删除结点后更新平衡因子时也会一路更新到根结点。例如下面这种情况：

在更新完平衡因子后，我们再进行实际删除结点的操作，因为实际删除结点的左右子树当中至少有一个为空树，因此我们实际删除结点时的逻辑如下：

1. 若实际删除结点的左子树为空，则让其parent链接到实际删除结点的右子树，最后再删除结点即可。
2. 若实际删除结点的右子树为空，则让其parent链接到实际删除结点的左子树，最后再删除结点即可。

但是要注意，因为结点是三叉链结构，因此在链接结点的过程中需要建立两个结点之间的双向关系。

在进行旋转处理时，我们将其分为以下六种情况：

1. 当parent的平衡因子为-2，parent的左孩子的平衡因子为-1时，进行右单旋。
2. 当parent的平衡因子为-2，parent的左孩子的平衡因子为1时，进行左右双旋。
3. 当parent的平衡因子为-2，parent的左孩子的平衡因子为0时，也进行右单旋，但此时平衡因子调整与之前有所不同，具体看代码。
4. 当parent的平衡因子为2，parent的右孩子的平衡因子为-1时，进行右左双旋。
5. 当parent的平衡因子为2，parent的右孩子的平衡因子为1时，进行左单旋。
6. 当parent的平衡因子为2，parent的右孩子的平衡因子为0时，也进行左单旋，但此时平衡因子调整与之前有所不同，具体看代码。

与插入结点不同的是，删除结点时若是进行了旋转处理，那么在进行旋转处理后我们必须继续往上更新平衡因子，因为旋转的本质就是降低树的高度，旋转后树的高度降低了，就会影响其父结点的平衡因子，因此我们还需要继续往上更新平衡因子。

更正： 上述旋转处理的六种情况当中，若属于情况三或情况六，那么在旋转后无需继续往上更新平衡因子，因为这两种情况旋转后树的高度并没有发生变化。（感谢可乐不解渴的指正，代码已更正）

代码如下：

//删除函数
bool Erase(const K& key)
{
	//用于遍历二叉树
	Node* parent = nullptr;
	Node* cur = _root;
	//用于标记实际的删除结点及其父结点
	Node* delParentPos = nullptr;
	Node* delPos = nullptr;
	while (cur)
	{
		if (key < cur->_kv.first) //所给key值小于当前结点的key值
		{
			//往该结点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_kv.first) //所给key值大于当前结点的key值
		{
			//往该结点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else //找到了待删除结点
		{
			if (cur->_left == nullptr) //待删除结点的左子树为空
			{
				if (cur == _root) //待删除结点是根结点
				{
					_root = _root->_right; //让根结点的右子树作为新的根结点
					if (_root)
						_root->_parent = nullptr;
					delete cur; //删除原根结点
					return true; //根结点无祖先结点，无需进行平衡因子的更新操作
				}
				else
				{
					delParentPos = parent; //标记实际删除结点的父结点
					delPos = cur; //标记实际删除的结点
				}
				break; //删除结点有祖先结点，需更新平衡因子
			}
			else if (cur->_right == nullptr) //待删除结点的右子树为空
			{
				if (cur == _root) //待删除结点是根结点
				{
					_root = _root->_left; //让根结点的左子树作为新的根结点
					if (_root)
						_root->_parent = nullptr;
					delete cur; //删除原根结点
					return true; //根结点无祖先结点，无需进行平衡因子的更新操作
				}
				else
				{
					delParentPos = parent; //标记实际删除结点的父结点
					delPos = cur; //标记实际删除的结点
				}
				break; //删除结点有祖先结点，需更新平衡因子
			}
			else //待删除结点的左右子树均不为空
			{
				//替换法删除
				//寻找待删除结点右子树当中key值最小的结点作为实际删除结点
				Node* minParent = cur;
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
					minParent = minRight;
					minRight = minRight->_left;
				}
				cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key
				cur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value
				delParentPos = minParent; //标记实际删除结点的父结点
				delPos = minRight; //标记实际删除的结点
				break; //删除结点有祖先结点，需更新平衡因子
			}
		}
	}
	if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点
	{
		return false;
	}

	//记录待删除结点及其父结点（用于后续实际删除）
	Node* del = delPos;
	Node* delP = delParentPos;

	//更新平衡因子
	while (delPos != _root) //最坏一路更新到根结点
	{
		if (delPos == delParentPos->_left) //delParentPos的左子树高度降低
		{
			delParentPos->_bf++; //delParentPos的平衡因子++
		}
		else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低
		{
			delParentPos->_bf--; //delParentPos的平衡因子--
		}
		//判断是否更新结束或需要进行旋转
		if (delParentPos->_bf == 0)//需要继续往上更新平衡因子
		{
			//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
			delPos = delParentPos;
			delParentPos = delParentPos->_parent;
		}
		else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束
		{
			break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
		}
		else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转（此时delParentPos树已经不平衡了）
		{
			if (delParentPos->_bf == -2)
			{
				if (delParentPos->_left->_bf == -1)
				{
					Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
					RotateR(delParentPos); //右单旋
					delParentPos = tmp; //更新根结点
				}
				else if(delParentPos->_left->_bf == 1)
				{
					Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点
					RotateLR(delParentPos); //左右双旋
					delParentPos = tmp; //更新根结点
				}
				else //delParentPos->_left->_bf == 0
				{
					Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
					RotateR(delParentPos); //右单旋
					delParentPos = tmp; //更新根结点
					//平衡因子调整
					delParentPos->_bf = 1;
					delParentPos->_right->_bf = -1;
					break; //更正
				}
			}
			else //delParentPos->_bf == 2
			{
				if (delParentPos->_right->_bf == -1)
				{
					Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点
					RotateRL(delParentPos); //右左双旋
					delParentPos = tmp; //更新根结点
				}
				else if(delParentPos->_right->_bf == 1)
				{
					Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
					RotateL(delParentPos); //左单旋
					delParentPos = tmp; //更新根结点
				}
				else //delParentPos->_right->_bf == 0
				{
					Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
					RotateL(delParentPos); //左单旋
					delParentPos = tmp; //更新根结点
					//平衡因子调整
					delParentPos->_bf = -1;
					delParentPos->_left->_bf = 1;
					break; //更正
				}
			}
			//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
			delPos = delParentPos;
			delParentPos = delParentPos->_parent;
			//break; //error
		}
		else
		{
			assert(false); //在删除前树的平衡因子就有问题
		}
	}
	//进行实际删除
	if (del->_left == nullptr) //实际删除结点的左子树为空
	{
		if (del == delP->_left) //实际删除结点是其父结点的左孩子
		{
			delP->_left = del->_right;
			if (del->_right)
				del->_right->_parent = delP;
		}
		else //实际删除结点是其父结点的右孩子
		{
			delP->_right = del->_right;
			if (del->_right)
				del->_right->_parent = delP;
		}
	}
	else //实际删除结点的右子树为空
	{
		if (del == delP->_left) //实际删除结点是其父结点的左孩子
		{
			delP->_left = del->_left;
			if (del->_left)
				del->_left->_parent = delP;
		}
		else //实际删除结点是其父结点的右孩子
		{
			delP->_right = del->_left;
			if (del->_left)
				del->_left->_parent = delP;
		}
	}
	delete del; //实际删除结点
	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
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个结点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$logN$。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但当一个结构经常需要被修改时，AVL树就不太适合了。