C++笔记：从零开始一步步手撕高阶数据结构AVL树

高度平衡二叉搜索树

二叉搜索树是一种特殊的树形数据结构，一般情况下，该树能够缩短查找的效率，但是它有个缺陷，在结点的插入或删除顺序较为特殊时结构会退化成链表，导致搜索、插入和删除等操作的时间复杂度从O(log n)退化到O(n)。

【二叉搜索树退化成链表的例子】

高度平衡二叉搜索树是针对二叉搜索树的缺陷所发明出来的一种改良结构。

高度平衡二叉搜索树常被称为 “ AVL树 ”，这主要是为了纪念发明它两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis，AVL是两位数学家的名字的缩写。

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

• 左右子树高度之差（简称为平衡因子）的绝对值不超过1。
• 在这里平衡因子的求法定义为：右子树的高度 - 左子树的高度。
• 结点的左右两棵子树也都是一棵平衡二叉树。

实现一颗AVL树

概念部分讲的差不多了，至于AVL树相较于二叉搜索树是如何保持平衡结构，就在接下来的实现过程中一步步讲解。

结点与树的描述——定义类

namespace ljh
{
	template<class K, class V>
	struct AVLTreeNode
	{
		AVLTreeNode(const pair<K, V> kv) : _kv(kv) {}

		AVLTreeNode<K, V>* _parent = nullptr;	// A pointer to node's father
		AVLTreeNode<K, V>* _left = nullptr;		// A pointer to node's left child
		AVLTreeNode<K, V>* _right = nullptr;	// A pointer to node's right child
		int _bf = 0;		// balance factor
		pair<K, V> _kv;		// key-value
	};

	template<class K, class V>
	class AVLTree
	{
		typedef AVLTreeNode<K, V> Node;

	public:
		// AVL树的操作方法

	protected:
		Node* _root = nullptr;
	};
}
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

【说明】

1. 模板化设计：
   • 使用template<class K, class V>来定义AVLTreeNode和AVLTree，使得该数据结构能够处理任意类型的键（Key）和值（Value），提高了代码的复用性和灵活性。
   • K代表键的类型，V代表值的类型。使用者可以根据自己的需求，在AVL树存储任何类型的键值对。
2. AVLTreeNode类：
   • AVLTreeNode结构体定义了AVL树中每个节点的结构，用struct定义是为了方便在树类访问。
   • _parent指针：指向父节点，用于在旋转等操作中快速定位父节点（记住这里的旋转，这将是后面的重点）。
   • _left和_right指针：分别指向左孩子和右孩子，是二叉树结构的基础。
   • _bf（平衡因子）：存储节点的平衡因子，用于衡量树是否平衡。
   • _kv：存储于结点中的键值对，其中K是键的类型，V是值的类型。
3. 构造函数：
   • AVLTreeNode的构造函数接收一个pair<K, V>对象，并初始化_kv成员变量。这样，当创建新节点时，可以方便地传入键值对。
4. AVLTree类：
   • AVLTree类代表整个AVL树结构。
   • typedef AVLTreeNode<K, V> Node;，在内部使用定义了一个类型别名Node，目的是简化代码书写。
   • _root指针：指向AVL树的根节点，是整棵树的入口点。
5. 保护成员：
   • _root成员变量被设计为protected，意味着它只能在AVLTree类及其派生类中被访问。这种设计是为了将AVL树的内部实现细节隐藏起来，而只暴露必要的公共接口给外部使用。
6. 命名空间：
   • 为了方便使用库函数，使用using namespace std;展开标准库，但这容易引发同名类或函数发生冲突，因而将所有定义放在ljh命名空间中。

AVL树的插入操作

AVL树的插入操作实现起来大致分成以下三个大步骤

步骤1：按照二叉搜索树的方法插入结点

1. 树为空，则构造新结点，让_root 指针指向该结点，返回true。
2. 树不空，按key的大小寻找插入位置，如果已存在，按插入失败处理，返回false。
3. 走到空表示找到合适位置，然后插入构造的新结点，插入时要判断左边插入或者右边插入。

此时插入并未结束，接下来进行步骤二的平衡因子更新操作！

【步骤1的代码如下：】

bool insert(pair<K, V> kv)
{
	// empty tree -> 直接插入
	if(_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	// not empty tree -> 找到合适的位置再插入
	else
	{
		Node* child = _root;
		Node* parent = nullptr;

		while (child)
		{
			// 大，往右走
			if (child->_kv.first < kv.first)
			{
				parent = child;
				child = child->_right;
			}
			// 小，往左走
			else if (child->_kv.first > kv.first)
			{
				parent = child;
				child = child->_left;
			}
			// 相同，插入失败
			else
			{
				return false;
			}
		}

		// child == nullptr, 找到合适的位置
		child = new Node(kv);

		if (child->_kv.first > parent->_kv.first)	parent->_right = child;
		else	parent->_left = child;
		child->_parent = 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

步骤2：自底向上调整平衡因子

我们将新插入结点称为child，新插入结点的双亲结点称为parent。

平衡因子的更新规则如下：

• 如果child是parent的左孩子，parent的平衡因子-1。
• 如果child是parent的右孩子，parent的平衡因子+1。

这是第一次更新，更新完之后要不要继续向上更新取决于以parent为根结点的这棵树的高度是否变化，情况有以下3种：

1. 平衡因子更新后，parent的平衡因子为0：
   这意味着parent->_bf是从-1 -> 0或者 从1 -> 0，以parent为根结点的这棵树的高度没有发生变化，不用再向上更新平衡因子，可以返回true，表示插入成功。

2. 平衡因子更新后，parent的平衡因子为-1或+1：
   这意味着parent->_bf是从0 -> -1或者 从0 -> 1，以parent为根结点的这棵树的高度发生了变化，但还没有达到需要旋转的程度。
   在这种情况下，更新child = child->_parent，更新parent = parent->_parent，继续更新parent 的平衡因子，直到情况1：找到平衡因子为0的节点；或者情况2：到达根节点（parent == nullptr）。

3. 平衡因子更新后，parent的平衡因子为-2或+2：
   这意味着此时以parent为根结点的这棵树已经违反了AVL树的规则，需要进行旋转处理，处理完之后，可以直接返回true。

【步骤2的代码如下：】

// 自底向上更新平衡因子
while (parent)
{
	if (child == parent->_left)
	{
		--parent->_bf;
	}
	else
	{
		++parent->_bf;
	}

	if (parent->_bf == 0)
	{
		return true;
	}
	else if (parent->_bf == 1 || parent->_bf == -1)
	{
		child = child->_parent;
		parent = parent->_parent;
	}
	else if (parent->_bf == 2 || parent->_bf == -2)
	{
		// 违反规则，旋转处理
		// ...
	}
	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

步骤3：触发旋转操作（AVL树平衡的精髓）

根据节点插入位置的不同，AVL树的旋转分为以下4种：

由于具象图的种类繁多，根本不可能画得完，下面AVL树旋转的图解中大多画的是抽象图。

右单旋

这里给出了一棵以结点90作为根节点的AVL树的抽象图，图中 a / b / c 代表三棵高度为 h 的子树。
这颗AVL树的左子树高度高于右子树高度。

---

首先，以90为根结点的这棵树有三种可能：

1. 它是某棵AVL树的左子树；
2. 它是某棵AVL树的右子树；
3. 它就是AVL树的根结点；

---

当新结点插入在了较高左子树的左侧，即 a 子树时，child 和 parent 自底向上更新平衡因子，当出现parent->_bf == -2, child->_bf == -1时，该树违反了AVL树的规则，需要进行右单旋操作。

---

在右单旋中，涉及到改变链接关系的结点主要有以下4个：

---

当 a / b / c 3棵子树高度为零时插入新结点，平衡因子为 -2 的结点向右旋转：

当 a / b / c 3棵子树高度不为零时插入新结点，平衡因子为 -2 的结点向右旋转：

---

【右单旋操作的代码如下】

void R_Rotate(Node* parent)
{
	Node* ppnode = parent->_parent;
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// subL and parent
	subL->_right = parent;
	parent->_parent = subL;

	// parent and subLR
	parent->_left = subLR;
	if (subLR)	subLR->_parent = parent;

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

	parent->_bf = subL->_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

左单旋

这里给出了一棵以结点30作为根节点的AVL树的抽象图，图中 a / b / c 代表三棵高度为 h 的子树。
这颗AVL树的右子树高度高于左子树高度。

---

首先，以30为根结点的这棵树有三种可能：

1. 它是某棵AVL树的左子树；
2. 它是某棵AVL树的右子树；
3. 它就是AVL树的根结点；

---

当新结点插入在了较高右子树的右侧，即 c 子树时，child 和 parent 自底向上更新平衡因子，当出现parent->_bf == 2, child->_bf == 1时，该树违反了AVL树的规则，需要进行左单旋操作。

---

在左单旋中，涉及到改变链接关系的结点同样有4个：

---

当 a / b / c 3棵子树高度为零时插入新结点，平衡因子为 2 的结点向左旋转：

当 a / b / c 3棵子树高度不为零时插入新结点，平衡因子为 2 的结点向左旋转：

---

【左单旋操作的代码如下】

void L_Rotate(Node* parent)
{
	Node* ppnode = parent->_parent;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	// subR and parent
	subR->_left = parent;
	parent->_parent = subR;

	// parent and subRL
	parent->_right = subRL;
	if (subRL)	subRL->_parent = parent;

	//ppnode and subR
	if (ppnode == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		subR->_parent = ppnode;
		if (parent == ppnode->_left)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
	}
	parent->_bf = subR->_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

左右双旋

这里给出了一棵以结点90作为根节点的AVL树的抽象图，图中 a / b / c / d 代表四棵子树。
这颗AVL树的左子树高度高于右子树高度。

---

首先，以90为根结点的这棵树有三种可能：

1. 它是某棵AVL树的左子树；
2. 它是某棵AVL树的右子树；
3. 它就是AVL树的根结点；

---

下面三种情况都有一个共同给特点，就是parent->_bf == -2, child->_bf == 1。
我们不难发现，左右双旋可以视为先左旋再右旋，即结点30先左旋，结点90再右旋。

---

---

单旋中的subLR不管怎么操作，它的平衡因子都是 0，但是在双旋中，subLR有可能是 -1、0、1中任意一种，因此，虽然双旋操作我们可以复用单旋的代码，但是双旋之后的平衡因子调整需要单独处理。

【左右双旋的代码如下】

void LR_Rotate(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// 双旋之后要靠bf来更新平衡因子
	int bf = subLR->_bf;

	L_Rotate(subL);
	R_Rotate(parent);

	if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		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

右左双旋

这里给出了一棵以结点30作为根节点的AVL树的抽象图，图中 a / b / c / d 代表四棵子树。
这颗AVL树的右子树高度高于左子树高度。

---

首先，以30为根结点的这棵树有三种可能：

1. 它是某棵AVL树的左子树；
2. 它是某棵AVL树的右子树；
3. 它就是AVL树的根结点；

---

下面三种情况都有一个共同给特点，就是parent->_bf == 2, child->_bf == -1。
我们不难发现，右左双旋可以视为先右旋再左旋，即结点90先右旋，结点30再左旋。

---

---

单旋中的subRL不管怎么操作，它的平衡因子都是 0，但是在双旋中，subRL有可能是 -1、0、1中任意一种，因此，虽然双旋操作我们可以复用单旋的代码，但是双旋之后的平衡因子调整需要单独处理。

【右左双旋的代码如下】

void RL_Rotate(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	// 双旋之后要靠bf来更新平衡因子
	int bf = subRL->_bf;

	R_Rotate(subR);
	L_Rotate(parent);

	if (bf == 0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_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

验证AVL树是否平衡

虽然目前已经将AVL树的插入操作的代码已经写出来了，但是仅仅是写出来了一定能够保证代码就是正确的吗——肯定不是！

所以，接下来还要再实现一个方法，来验证一棵AVL树是不是平衡的。

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树
   如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。
2. 验证其为平衡树
   每个结点子树高度差的绝对值不超过1（注意节点中如果没有平衡因子）。
   结点的平衡因子是否计算正确。

【写法一代码：简单但是效率低】

// 求AVL树的高度
size_t _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;
}

size_t Height()
{
	return _Height(_root);
}

bool _IsBalance(Node* root)
{
	// 空树也是AVL树
	if (root == nullptr) return true;
	
	// 计算root节点的平衡因子：即root左右子树的高度差
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
	// root平衡因子的绝对值超过1，则一定不是AVL树
	int diff = rightHeight - leftHeight;
	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "不平衡" << endl;
		return false;
	}

	if (diff != root->_bf)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}
	
	// root的左和右如果都是AVL树，则该树一定是AVL树
	return _IsBalance(root->_left) && _IsBalance(root ->_right);
}
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

【写法二代码：效率高但是相较写法一难理解】

// 判断AVL树是否平衡，高效
bool _IsBalance(Node* root, int& height)
{
	// 空树也是AVL树
	if (root == nullptr)
	{
		height = 0;
		return true;
	}

	// 后序递归，leftHeight、rightHeight会分别获取root的左右子树的高度
	int leftHeight = 0, rightHeight = 0;
	if (!_IsBalance(root->_left, leftHeight) 
	 || !_IsBalance(root->_right, rightHeight))
	{
		return false;
	}

	// 如果高度差的绝对值 >= 2，AVL树不平衡
	int diff = rightHeight - leftHeight;
	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "不平衡" << endl;
		return false;
	}

	// 如果高度差 != root->_bf，AVL树插入过程中的平衡因子更新有问题
	if (diff != root->_bf)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}

	// 将root自己的高度通过引用返回给上一层栈帧
	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	// root的左子树平衡、右子树平衡、root自身也平衡，那这棵AVL树就平衡
	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

参考文章

数据结构 —— 图解AVL树(平衡二叉树)
高度平衡二叉搜索树（AVLTree）
【数据结构】AVL树的删除（解析有点东西哦）