二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成 O(N)，因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现

AVL树的概念

在这里插入图片描述

我们已经从多种树型结构走到现在，每一次变化都是为了提高搜索的效率，即时间复杂度

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下，因此发明了 AVL 树

那么什么是AVL树呢？

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1 (需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

在这里插入图片描述

一棵 AVL 树或者是空树，应该是具有以下性质的二叉搜索树：

  • 它的左右子树都是 AVL 树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过 1(-1/0/1)

二叉搜索树在理想情况下时间复杂度与二叉平衡搜索树相同，均为 $O(log_2 n)$，但在极端情况下二叉平衡搜索树优于二叉搜索树，因为二叉平衡搜索树会自己调整平衡（后面会详细解释）

为什么是严格的绝对值为 1，不是 0 或者更大的数字？

若要求高度差为 0，即严格平衡，树的结构会过于 rigid（僵化）。每次插入或删除节点都可能需要大量调整操作，导致性能下降。允许高度差为 1，在保持较好平衡性的同时，减少了不必要的调整
若允许高度差为 2，树的平衡性会明显下降，可能出现一侧子树比另一侧高很多的情况，导致查找等操作的时间复杂度增加
所以平衡因子为 1 是最合适的

AVL树的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)
	{ }
};
  • pair<K, V> _kv：用于存储键值对，pair 是 C++ 标准库中的一个模板类，可将两个不同类型的值组合在一起
  • AVLTreeNode<K, V>* _left：指向左子节点的指针
  • AVLTreeNode<K, V>* _right：指向右子节点的指针
  • AVLTreeNode<K, V>* _parent：指向父节点的指针，这在调整树的平衡时很有用
  • int _bf：平衡因子（Balance Factor），用来记录该节点左右子树的高度差。平衡因子为 0 时表示左右子树高度相等；为 1 时表示右子树比左子树高 1；为 -1 时表示左子树比右子树高 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
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
	typedef AVLTreeNode<K, V> Node;
public:
	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;
			}
		}

			//链接插入节点与AVL树
			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)
				{
					//旋转调整（...）
				}
				else
				{
					assert(false);
				}
			}
			return true;
	}

AVL 树的插入和二叉搜索树是很像的，先根据左大右小的原则，寻找插入节点的位置，然后判断父母节点与插入节点的关系，连接新节点，唯一不同的地方是平衡因子调节的部分，高度差是由右子树减去左子树得出的，可以总结出以下方法：

🚩 (1)新增在左，parent平衡因子减减
在这里插入图片描述

🚩 (2)新增在右，parent平衡因子加加

在这里插入图片描述

🚩 (3)更新后parent平衡因子 == 0

说明 parent 所在的子树的高度不变，不会影响祖先，不用再继续沿着到 root 的路径往上更新，然后循环结束

🚩 (4)更新后parent平衡因子 == 1 or -1

说明 parent 所在的子树的高度变化，会影响祖先，需要继续沿着到 root 的路径往上更新，循环继续

🚩 (5)更新后parent平衡因子 == 2 or -2

说明 parent 所在的子树的高度变化且不平衡，需要对parent所在子树进行旋转，让他平衡，然后循环结束

🔥值得注意的是： 如果平衡因子出现比 2 还大，比 -2 还小的数，说明之前的插入就已经出问题了

4.AVL树的旋转

4.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
void RotateL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;

	parent->_right = curleft;
	if (curleft)
	{
		curleft->_parent = parent;
	}

	cur->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = cur;

	if (parent == _root)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}

		cur->_parent = ppnode;
	}

	parent->_bf = cur->_bf = 0;
}

以下将根据一个图例来解释如何进行的左单旋：

在这里插入图片描述

左单旋顾名思义就是右子树太长，需要向左旋转形成平衡，平衡因子为 2 的节点定为 parent，其右节点为 cur，cur 的左节点为 curleft

  1. 调整 parent 的右子节点： 把 parent 的右子节点设置成 curleft，若 curleft 不为空，就把 curleft 的父节点设置成 parent
  2. 调整 cur 的左子节点： 把 cur 的左子节点设置成 parent，ppnode 为 parent 的父节点，把 parent 的父节点设置成 cur
  3. 调整根节点或者 ppnode 的子节点： 若 parent 是根节点，那就把 cur 设为新的根节点，并且将 cur 的父节点设为 nullptr。若 parent 不是根节点，就依据 parent 是 ppnode 的左子节点还是右子节点，来更新 ppnode 的相应子节点为 cur，同时把 cur 的父节点设为 ppnode

4.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
32
33
34
35
36
void RotateR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;

	parent->_left = curright;
	if (curright)
	{
		curright->_parent = parent;
	}

	Node* ppnode = parent->_parent;
	cur->_right = parent;
	parent->_parent = cur;

	if (ppnode == nullptr)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}

		cur->_parent = ppnode;
	}

	parent->_bf = cur->_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
void RotateRL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	int bf = curleft->_bf;

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

	if (bf == 0)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		cur->_bf = 1;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

右左双旋适用于新节点插入较高右子树的左侧的情况

在这里插入图片描述
30 为 parent 节点，90 为 cur 节点，60 为 curleft 节点

先以 90 进行右单旋，再以 30 进行左单旋

双旋的重点是平衡节点的调整，根据多个例子可以知道，主要是看 curleft 节点的平衡因子

在这里插入图片描述

如果原来 curleft 平衡因子为 0 ，即 curleft 为新增节点导致的双旋，那么 curleft、cur、parent 平衡因子都为 0

在这里插入图片描述

如果原来 curleft 平衡因子为 1 ，即在 curleft 右边新增，那么 cur 和 curleft 平衡因子都为 0，parent 的平衡因子为 1

在这里插入图片描述

如果原来 curleft 平衡因子为 -1 ，即在 curleft 左边新增，那么 parent 和 curleft 平衡因子都为 0，cur 的平衡因子为 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
void RotateLR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	int bf = curright->_bf;

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

	if (bf == 0)
	{
		parent->_bf = 0;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		cur->_bf = -1;
		curright->_bf = 0;
	}
}

和右左双旋类似，这里就不详细解释了

在这里插入图片描述

AVL树的删除

在实际开发中，虽然 AVL 树是一种自平衡的二叉搜索树，但其删除操作通常不被优先实现

AVL 树的核心特性是通过旋转操作（左旋、右旋、左右旋、右左旋）来保证树的高度平衡。在插入操作中，仅需从插入节点向上回溯至根节点，检查并调整路径上节点的平衡因子，最多进行两次旋转操作就能恢复树的平衡。然而，删除操作后，平衡的破坏可能会沿着从删除节点到根节点的路径向上传播，导致需要多次旋转操作来恢复平衡。这使得删除操作的实现逻辑变得异常复杂，需要仔细处理各种可能的情况

而且实现插入删除一般会使用 红黑树、B树 等更优的数据结构

AVL树的高度

1
2
3
4
5
6
7
8
9
10
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;
}

比较左子树和右子树的高度，取较大值并加 1（加上当前根节点），得到当前子树的高度

AVL树的平衡判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool IsBalance(Node* root)
{
	if (root == nullptr)
		return true;

	int leftHight = Height(root->_left);
	int rightHight = Height(root->_right);

	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
		return false;
	}

	return abs(rightHight - leftHight) < 2
		&& IsBalance(root->_left)
		&& IsBalance(root->_right);
}

每遍历一个节点就对其左右子树的高度进行计算，然后判断是否绝对值小于 2

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

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述