【C++】——探索自平衡的艺术：实现AVL树

如果结果不如你所愿，那就在尘埃落定前奋力一搏。

—— 夏目友人帐

---

目录

1、 解密AVL树：平衡与效率的双重奏

2、搭建AVL树：从零到自平衡的实现之路

2.1 树基打底：设计与框架构建

2.2 插入有道：平衡与插入并存

2.3 旋转为王：平衡的秘密武器

2.4 查找制胜：高效查询之道

3、性能透析：AVL树的效率与边界

---

1、解密AVL树：平衡与效率的双重奏

前面我们已经学习了 二叉搜索树

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为： O(log2 N)

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为： O(N/2)

这样如果是单链情况，那么大大降低了效率

所以出现了改进的搜索树->AVL树（平衡二叉搜索树）

在1962年，俄罗斯数学家G.M. Adelson-Velskii和E.M. Landis提出了一种革命性的解决方案：他们发明了AVL树。通过在二叉搜索树插入新节点后，确保每个节点的左右子树高度差的绝对值不超过1（即进行必要的树结构调整），这种方法能够有效控制树的高度，从而大幅度降低平均搜索长度。这个创新不仅解决了二叉搜索树在高频插入和删除操作中的性能瓶颈，也为平衡二叉树的发展奠定了基础，成为了数据结构领域的一个经典突破。

map 与 set 的底层实现也是AVL树或红黑树！

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

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log N)

搜索复杂度O(log N)

通过每次插入删除的调整(旋转)保证二叉树始终保持一个近乎完美的完全二叉树，规避了极端情况下二叉搜索树退化为单枝树的情况

2、搭建AVL树：从零到自平衡的实现之路

2.1 树基打底：设计与框架构建

首先AVL树是在二叉搜索树的基础上进行改进，AVL树节点中加入了：

• 平衡因子_bf：左右子树的高度差 right子树高度 - left子树高度 ，即左子树插入节点时_bf--，右子树插入节点时_bf++
• 父指针_parent：指向父节点的指针，为了可以回溯更新父节点的平衡因子

template<class K,class V>
struct AVLTreeNode
{
	//键值对
	pair<K, V> _kv;
	//三叉链
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	// 需要父亲指针 更新平衡因子
	AVLTreeNode* _parent;
	//平衡因子 右子树高度-左子树高度
	int _bf; 

	AVLTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};
	
template<class K, class V>
class AVLTree
{
	//typedef AVLTreeNode<K,V> Node;
	using Node = AVLTreeNode<K, V>;

private:
	Node* _root = nullptr;
};

2.2 插入有道：平衡与插入并存

实现插入操作，确保新节点的加入不会破坏树的平衡。

bool insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return 1;
	}
	Node* cur = _root;
	Node* prev = nullptr;
	//查找逻辑 cur 到对应的位置去
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			prev = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			prev = cur;
			cur = cur->_left;
		}
		else
		{
			return 0;
		}
	}
	cur = new Node(kv);
	// 连接 prev 与 cur
	if (prev->_kv.first > kv.first)
		prev->_left = cur;
	else
		prev->_right = cur;
	cur->_parent = prev;
    //更新平衡因子

}

结下来就是处理平衡因子：左子树插入节点时_bf--，右子树插入节点时_bf++

这里思考一下，平衡因子的处理要到什么情况才停下来？？？

当我们插入一个新节点时，有两种情况：

1. 插入parent的左子树，parent的平衡因子减一！
2. 插入parent的右子树，parent的平衡因子加一！

父节点的平衡因子经过更新后可以得到三种情况：

• parent的平衡因子是 0 ：得到0 说明之前之前parent的左右两边不平衡，插入后平衡了，高度没有改变，不需要处理爷爷节点！！！

• parent的平衡因子是 ∓1 ：得到正负一说明之前parent的平衡因子是0，插入后以parent为根节点的子树的高度增加了！那么就要继续处理爷爷节点！

• parent的平衡因子是 ∓2 ：得到这种情况说明在本来就高的一边继续插入了一个新节点！以parent为根节点的子树已经不满足AVL树的结构，需要特殊处理！

首先可能要向上一直处理，所以干脆写一个while循环，在内部在进行分类：如果需要继续处理爷爷节点，就继续循环，不需要处理就跳出循环！

// ...
//更新平衡因子
while (prev != nullptr)
{
	if (cur == prev->_left)
	{
		//左子树增加 父节点平衡因子--
		prev->_bf--;
	}
	else
	{
		//右子树增加 父节点平衡因子++
		prev->_bf++;
	}

	//为零直接退出
	if (prev->_bf == 0)
	{
		break;
	}
	//为 1 或 -1 继续向上进行
	else if (prev->_bf == 1 || prev->_bf == -1)
	{
		cur = prev;
		prev = cur->_parent;
	}
	//旋转来哩！！！
	else if (prev->_bf == 2 || prev->_bf == -2)
	{
		//分类旋转

		//旋转之后二叉树平衡！
		break;
	}
	//特殊情况处理 因为未来不知道会出什么bug ,在这里截断一下
	else
	{
		assert(false);
	}
}

prev(cur的父亲节点) 的平衡因子是 ∓ 2 的情况的特殊处理就是旋转！！！下面我们来看如何进行旋！！！

2.3 旋转为王：平衡的秘密武器

旋转是AVL树的精髓所在！！

首先选择有四种：右单旋 ，左单旋，左右双旋，右左双旋

右单旋

这是最简单的情况，简单的向右旋转，使其满足AVL树的性质！

再来看一般情况，并来具体分析一下：

1. 初始化情况：树的情况如图，parnet的平衡因子是-1，subL的平衡因子是0 ！
2. 当我们在subL的左子树插入一个节点，并使subL的平衡因子变为-1 , parent的平衡因子变为-2（左边一边高，故右单旋）
3. 此时需要对parnet进行右单旋

• parent成为subL的右子树
• subLR成为parent的左子树
• subL代替原本parnet的位置
• 注意处理平衡因子！！！处理_parent 指针

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	//subLR->_parent = parent; //这里有个问题 subLR为空呢？
	if (subLR)
		subLR->_parent = parent;

	Node* pparent = parent->_parent; //先记录再更改指向

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

	//为根
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	//这里个问题如何确定 subL为 parnet->parent的左右呢？
	else  //不为根 还需要连接 parent->parent 和subL
	{
		if (pparent->_left == parent)
			pparent->_left = subL;
		else
			pparent->_right = subL;

		subL->_parent = pparent;
	}
	//更新平衡因子
	subL->_bf = 0;
	parent->_bf = 0;
}

左单旋

左单旋与右单旋类似！！！

1. 初始化情况：树的情况如图，parnet的平衡因子是1，subL的平衡因子是0 ！
2. 当我们在subL的左子树插入一个节点，并使subL的平衡因子变为1 , parent的平衡因子变为2
3. 此时需要对parnet进行左单旋

• parent成为suR的左子树
• subRL成为parent的左子树
• subR代替原本parnet的位置
• 注意处理平衡因子！！！处理_parent 指针

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	Node* pparent = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;

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

		subR->_parent = pparent;
	}
	subR->_bf = 0;
	parent->_bf = 0;
}

左右双旋

这种情况既不能通过右单旋解决，也不能通过左单旋解决！！！
这时候就需要继续左右双旋：先进行一次左单旋，再进行一次右单旋。

Tip：subL的 bf为1，右边高了 所以第一次对 subL左旋 parent的 bf为2左边高了 所以第二次对 parent右旋

具体怎么操作，我们来看图分析

注意，根据图分析，插入的位置会影响subL和 parent的平衡因子，需要根据subLR分类讨论

1. 如果插入到subLR的右子树， 那么该右子树最终会变成parent的左子树，所以相当于parent的左子树插入节点，所以parent的平衡因子应为-1
2. 如果插入到subLR的左子树， 那么该左子树最终会变成subL的左子树，所以相当于subL的右子树插入节点，所以parent的平衡因子应为1
3. 如果subLR自己是新插入的节点，那么平衡因子都为0！

我们可以只观察结果：subLR成为了新根，subL左子树（左单旋 左子树），parent右子树（右单旋 右子树），subLR之前的左子树分给了subL的右子树，subLR之前的右子树分给了parent的左子树

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);
	//  更新平衡因子
	if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

右左双旋

情况与左右双旋类似，不再赘述

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

	RotateR(parent->_right);
	RotateL(parent);
	if (bf == -1) //左0 右1 bf=-1 右边低 低的充当subRL的右树（subR）的左树 所以 subR->bf=1 
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1)
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == 0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

我们完成了旋转，就可以补全插入操作的空缺,按情况分好类即可：

	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return 1;
		}
		Node* cur = _root;
		Node* prev = nullptr;
		//查找逻辑 cur 到对应的位置去
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				prev = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				prev = cur;
				cur = cur->_left;
			}
			else
			{
				return 0;
			}
		}
		cur = new Node(kv);
		// 连接 prev 与 cur
		if (prev->_kv.first > kv.first)
			prev->_left = cur;
		else
			prev->_right = cur;
		cur->_parent = prev;

		// 更新平衡因子  Tip 更新结束条件？ 
		while (prev) //可能一直更新到根 根的 prev即parent 为空 结束更新
		{
			if (cur == prev->_left)
				prev->_bf--;
			else
				prev->_bf++;
			if (prev->_bf == 0) //更新结束
			{
				break;
			}
			else if (prev->_bf == 1 || prev->_bf == -1) //需要向上更新
			{
				cur = prev;
				prev = prev->_parent;
			}
			else if (prev->_bf == 2 || prev->_bf == -2) //结构破坏了 需要旋转处理
			{
				if (prev->_bf == -2 && cur->_bf == -1)
				{
					RotateR(prev);
				}
				else if (prev->_bf == 2 && cur->_bf == 1)
				{
					RotateL(prev);
				}
				// 平衡因子 异号 不是纯粹的一边高
				else if (prev->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(prev);
				}
				else if (prev->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(prev);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return 1;
	}

在这里可以测试一下！！！
一定一定保证插入没有问题了在向下进行其他函数的书写，不然出错了就会让人崩溃的！！！

2.4 查找制胜：高效查询之道

寻找与二叉搜索树一样：

Node* find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)
		{
			cur = cur->_right;
		} 
		else if (cur->_kv.first > key)
		{
			cur = cur->_left;
		} 
		else
		{
		return cur;
		}
	}
	return nullptr;
}

3、性能透析：AVL树的效率与边界

我们写了这么多的代码，现在来测试一下，来看看是否满足AVL树！！！

验证AVL树就要来检查每个节点的平衡因子是否满足条件！平衡因子的本质是左右子树的高度差，所以我们可以通过检查每颗子树的高度差来看看是否满足条件，然后还有个问题就是可能平衡因子更新错误了，这个也是需判断的。

int height()
{
	return _height(_root);
}
bool isBalanceTree()
{
	return _isBalanceTree(_root);
}

private:
int _height(Node* root)
{
	if (root == nullptr)
		return 0;
	int leftHeight = _height(root->_left);
	int rightHeight = _height(root->_right);
	
	return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
}

bool _isBalanceTree(Node* root)
{
	if (root == nullptr)
		return 1;
	// 计算Root结点的平衡因⼦：即Root左右⼦树的⾼度差
	int leftHeight = _height(root->_left);
	int rightHeight = _height(root->_right);
	int diff = rightHeight - leftHeight;
	
	// Root平衡因⼦的绝对值超过1，则⼀定不是AVL树
	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "高度差异常" << endl;
		return 0;
	}
	// 如果计算出的平衡因⼦与Root的平衡因⼦不相等 不是 AVL树
	if(root->_bf != diff)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return 0;
	}
	
	// Root的左和右如果都是AVL树，则该树⼀定是AVL树
	return _isBalanceTree(root->_left) && _isBalanceTree(root->_right);

}

现在：
我们写个测试代码测试一下：

void TestAVLTree2()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	xc::AVLTree<int, int> t;
	for (auto e : v)
	{
		t.insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.isBalanceTree() << endl;
	cout << "Height:" << t.height() << endl;
	cout << "Size:" << t.size() << endl;

}

可以看到我们插入了六百万多节点，仍保持平衡结构！

现在来分析一下性能

我们提供 1亿 的数据量，来看看其插入，查找和删除的效率怎么样：

void AVLTreeTest6()
{
	const int N = 100000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	cout << t.IsBalance() << endl;
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}
	// 随机值
	//for (size_t i = 0; i < N; i++)
	//{
	//	t.Find((rand() + i));
	//}

	size_t end1 = clock();

	cout << "Find:" << end1 - begin1 << endl;
	size_t begin3 = clock();
	for (auto e : v)
	{
		t.Erase(e);
	}
	size_t end3 = clock();
	cout << "Erase:" << end3 - begin3 << endl;
}

看看需要多少时间：

其中一共有六千万的节点，插入共用时 44 s，依次删除所有节点用时 18s，搜索只用了不到1ms！！！

所以AVL树的优缺点很明显：

• 插入删除的效率比较低，毕竟每次插入删除时都有对应更新平衡因子，还要考虑旋转的情况。
• 搜索的效率是真的快！！！1亿数据量的最多就搜索29次（因为最高才29层）。

下面是对AVL树性能的分析：

查找操作

• 最坏情况时间复杂度：O(log n)
• 平均情况时间复杂度：O(log n)
• 由于AVL树总是保持平衡的，因此查找操作的时间复杂度与树的高度成正比，树的高度最小，查找效率就高。

插入操作

• 最坏情况时间复杂度：O(log n)
• 平均情况时间复杂度：O(log n)
• 插入操作后，AVL树可能会失去平衡。为了恢复平衡，可能需要进行一次或多次旋转（单旋转或双旋转）。尽管如此，这些操作的时间复杂度仍然是对数级别的。

删除操作

• 最坏情况时间复杂度：O(log n)
• 平均情况时间复杂度：O(log n)
• 删除操作与插入操作类似，可能会使树失去平衡，需要进行旋转操作来恢复平衡。

空间复杂度

• 空间复杂度：O(n)
• AVL树需要存储额外的信息（例如节点的平衡因子），以及可能需要的额外空间来执行旋转操作。

AVL树在频繁进行插入和删除操作的场景中可能不是最佳选择。在这些情况下，红黑树等其他自平衡二叉搜索树可能是更好的选择，因为它们对平衡的要求不那么严格，从而在插入和删除操作时可能需要更少的旋转操作。

如果数据结构是静态的，即一旦创建就不会频繁修改，AVL树是一个很好的选择，因为它可以提供高效的查询操作。但是，如果数据结构需要频繁地修改，那么可能需要考虑使用其他数据结构，如红黑树、B树或跳表等，这些数据结构在动态操作方面可能更加高效。

AVL 树的应用场景：

• 数据库系统：用于高效地存储和检索数据，保证快速的查找、插入和删除操作。
• 文件系统：帮助管理文件目录结构，快速定位文件。
• 编译器设计：在符号表的实现中，可以快速查找变量、函数等的信息。
• 操作系统：管理内存分配、进程调度等任务时，可利用 AVL 树快速查找合适的资源。​​​​​​​
• 网络路由表：快速查找目标网络地址对应的路由信息，提高路由效率。
• 地图导航软件：存储地图中的地点信息，以便快速查找特定位置或进行路径规划。
•  游戏开发：管理游戏中的对象，如角色、道具等，实现快速的查找和操作。

Thanks谢谢阅读！！！