首页 > 基础资料博客日记

【C++笔记】AVL树的深度剖析

2024-12-30 12:00:07基础资料围观62次

文章【C++笔记】AVL树的深度剖析分享给大家，欢迎收藏Java资料网，专注分享技术知识

【C++笔记】AVL树的深度剖析

🔥个人主页：大白的编程日记

🔥专栏：C++笔记

文章目录

【C++笔记】AVL树的深度剖析

前言

哈喽，各位小伙伴大家好!上期我们讲了map和set的深度剖析。今天我们来讲一下AVL树的深度剖析。话不多说，我们进入正题！向大厂冲锋

一. AVL树的概念

定义
AVL树是最先发明的自平衡⼆叉查找树，AVL是一颗空树，或者具备下列性质的⼆叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树，通过控制高度差去控制平衡。
注意是所有的子树都满足高度差绝对值不超过1。
发明者
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
平衡因子
AVL树实现这里我们引入⼀个平衡因子(balance factor)的概念，每个结点都有⼀个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像⼀个风向标⼀样。

高度差
思考⼀下为什么AVL树是高度平衡搜索⼆叉树，要求⾼度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如⼀棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0
对比二叉搜索树
AVL树整体结点数量和分布和完全⼆叉树类似，高度可以控制在，那么增删查改的效率也可以控制在，相比⼆叉搜索树有了本质的提升。

二.AVL树的实现

2.1 AVL树的结构

这里我们为了旋转时需要用到父亲节点，所以我们就是一个三叉链的结构。
同时我们引入了平衡因子，方便我们控制高度差。

template<class k, class v>
struct AVLNode
{
	using node = AVLNode<k, v>;
	k _key;
	v _value;
	node* left;//左节点
	node* right;//右节点
	node* parent;//父亲节点
	int bf;//平衡因子
	AVLNode(const k& key, const v& value)
		:_key(key)
		, _value(value)
		, left(nullptr)
		, right(nullptr)
		,parent(nullptr)
		,bf(0)
	{}
};
template<class k, class v>
class AVLTree
{
	using node = AVLNode<k, v>;
	private:
	node* _root = nullptr;
};

2.2 AVL树的插入

二叉搜索树还是按照二叉搜索树的规则插入。
但是插入后要更新平衡因子，如果高度差超过1那么就旋转。

插入
插入一个值按二叉搜索树规则进行插入。
插入的节点，左右为空所以平衡因子为0.
更新平衡因子
新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
结束
更新平衡因子过程中没有出现问题，则插入结束。
旋转
更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，保持原来的高度，不会再影响上一层，所以插入结束。

2.3 平衡因子更新

更新原则：

平衡因子 = 右子树高度-左子树高度
只有子树高度变化才会影响当前结点平衡因子。
插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子–。
parent所在子树的高度是否变化决定了是否会继续往上更新
如果当前子树高度没有变化，那当前子树往上的祖先节点的平衡因子也不会变化
更新结束。

更新停止条件：

更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树⼀边高⼀边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的⽗亲结点的平衡因子，更新结束。
更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说明更新前parent子树两边⼀样高，新增的插入结点后，parent所在的子树⼀边高⼀边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的⽗亲结点的平衡因子，所以要继续向上更新。
更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树⼀边高⼀边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
不断更新，更新到根，跟的平衡因子是1或-1也停停止了。

三.旋转

3.1旋转的原则

旋转的原则如下：

保持搜索树的规则
让旋转的树从不满足变平衡，其次降低旋转树的高度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
说明：下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什么值都可以，只要大小关系符合搜索树的性质即可。

3.2右单旋

旋转时我们需要注意保持二叉搜索树的性质。
同时注意父亲节点和平衡因子的更新。
注意旋转后子树的高度不变，平衡因子向上更新停止。

	void RoRateR( node* parent)//右单旋
	{
		node* subL = parent->left;
		node* subLR = subL->right;
		node* pparnet = parent->parent;
		parent->left = subLR;
		if (subLR)
		{
			subLR->parent = parent;//修改父节点
		}
		subL->right = parent;
		parent->parent = subL;
		if (pparnet == nullptr)//parent就是根节点
		{
			_root = subL;
			subL->parent = nullptr;
		}
		else
		{
			if (pparnet->left == parent)//确定parent节点是左还是右
			{
				pparnet->left = subL;
			}
			else 
			{
				pparnet->right = subL;
			}
			subL->parent = pparnet;//修改父节点
		}
		subL->bf = parent->bf = 0;//更新平衡因子
	}

3.3左单旋

左单旋和右单旋类似。

void RoRateL( node* parent)//左单旋
{
	node* subR = parent->right;
	node* subRL = subR->left;
	node* pparnet = parent->parent;
	parent->right = subRL;
	if (subRL)//防止subRL为空
	{
		subRL->parent = parent;//修改父节点
	}
	subR->left = parent;
	parent->parent = subR;
	if (pparnet==nullptr)//parent就是根节点
	{
		_root = subR;
		subR->parent = nullptr;
	}
	else
	{
		if (pparnet->left == parent)//确定parent节点是左还是右
		{
			pparnet->left = subR;
		}
		else 
		{
			pparnet->right = subR;
		}
		subR->parent = pparnet;//修改父节点
	}
	subR->bf = parent->bf = 0;//更新平衡因子
}

3.4左右双旋

左右双旋的就是先左单旋再右单旋。
同时注意平衡因子的更新即可。

更新条件：parent->bf == -2 && cur->bf == 1

void RoRateLR( node* parent)//左右双旋
{
	node* subL = parent->left;
	node* subLR = subL->right;
	int bf = subLR->bf;//先记录插入后的平衡因子
	RoRateL(subL);
	RoRateR(parent);
	if (bf == 0)//分情况讨论
	{
		parent->bf = 0;
		subL->bf = 0;
		subLR->bf = 0;
	}
	else if (bf == 1)
	{
		parent->bf = 0;
		subL->bf = -1;
		subLR->bf = 0;
	}
	else if (bf == -1)
	{
		parent->bf = 1;
		subL->bf = 0;
		subLR->bf = 0;
	}
	else
	{
		assert(false);
	}
}

3.5右左双旋

右左双旋情况和左右双旋类似，这里就不过多赘述了。

更新条件：parent->bf == 2 && cur->bf == -1

3.6AVL树的插入

结合前面的知识我们就可以写出二叉搜索树的插入了。

void RoRateR( node* parent)//右单旋
{
	node* subL = parent->left;
	node* subLR = subL->right;
	node* pparnet = parent->parent;
	parent->left = subLR;
	if (subLR)
	{
		subLR->parent = parent;//修改父节点
	}
	subL->right = parent;
	parent->parent = subL;
	if (pparnet == nullptr)//parent就是根节点
	{
		_root = subL;
		subL->parent = nullptr;
	}
	else
	{
		if (pparnet->left == parent)//确定parent节点是左还是右
		{
			pparnet->left = subL;
		}
		else 
		{
			pparnet->right = subL;
		}
		subL->parent = pparnet;//修改父节点
	}
	subL->bf = parent->bf = 0;//更新平衡因子
}
void RoRateL( node* parent)//左单旋
{
	node* subR = parent->right;
	node* subRL = subR->left;
	node* pparnet = parent->parent;
	parent->right = subRL;
	if (subRL)//防止subRL为空
	{
		subRL->parent = parent;//修改父节点
	}
	subR->left = parent;
	parent->parent = subR;
	if (pparnet==nullptr)//parent就是根节点
	{
		_root = subR;
		subR->parent = nullptr;
	}
	else
	{
		if (pparnet->left == parent)//确定parent节点是左还是右
		{
			pparnet->left = subR;
		}
		else 
		{
			pparnet->right = subR;
		}
		subR->parent = pparnet;//修改父节点
	}
	subR->bf = parent->bf = 0;//更新平衡因子
}
void RoRateLR( node* parent)//左右双旋
{
	node* subL = parent->left;
	node* subLR = subL->right;
	int bf = subLR->bf;//先记录插入后的平衡因子
	RoRateL(subL);
	RoRateR(parent);
	if (bf == 0)//分情况讨论
	{
		parent->bf = 0;
		subL->bf = 0;
		subLR->bf = 0;
	}
	else if (bf == 1)
	{
		parent->bf = 0;
		subL->bf = -1;
		subLR->bf = 0;
	}
	else if (bf == -1)
	{
		parent->bf = 1;
		subL->bf = 0;
		subLR->bf = 0;
	}
	else
	{
		assert(false);
	}
}
void RoRateRL( node* parent)//右左双旋
{
	node* subR = parent->right;
	node* subRL = subR->left;
	int bf = subRL->bf;//先记录插入后的平衡因子
	RoRateR(subR);
	RoRateL(parent);
	if (bf == 0)//分情况讨论
	{
		parent->bf = 0;
		subR->bf = 0;
		subRL->bf = 0;
	}
	else if (bf == 1)
	{
		parent->bf = -1;
		subR->bf = 0;
		subRL->bf = 0;
	}
	else if (bf == -1)
	{
		parent->bf = 0;
		subR->bf = 1;
		subRL->bf = 0;
	}
	else
	{
		assert(false);
	}
}
bool Insert(const k& x, const v& v)
{
	if (_root == nullptr)//插入根节点
	{
		_root = new node(x, v);
		return true;
	}
	node* cur = _root;
	node* parent = nullptr;//保留父亲节点
	while (cur)
	{
		/*介质不冗余*/
		if (x < cur->_key)
		{
			parent = cur;
			cur = cur->left;
		}
		else if (x > cur->_key)
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			return false;
		}
		//介质冗余
		//if (x <= cur->_key)//相等插入到左子树
		//{
		//	parent = cur;
		//	cur = cur->left;
		//}
		//else if (x > cur->_key)
		//{
		//	parent = cur;
		//	cur = cur->right;
		//}
	}
	cur = new node(x, v);
	if (x > parent->_key)
	{
		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)//旋转
		{
			if (parent->bf == -2 && cur->bf == -1)
			{
				RoRateR(parent);
			}
			else if (parent->bf == 2 && cur->bf == 1)
			{
				RoRateL(parent);
			}
			else if (parent->bf == -2 && cur->bf == 1)
			{
				RoRateLR(parent);
			}
			else if (parent->bf == 2 && cur->bf == -1)
			{
				RoRateRL(parent);
			}
			else
			{
				assert(false);
			}

			break;
		}
		else
		{
			assert(false);
		}
	}
	return true;
}

3.7AVL树的查找

在避免了二叉搜索树退化为单叉树的情况。
AVL树的查找效率为O(logN).

四.AVL树的检测

4.1AVL树检测

AVL树我们可以递归检测每颗子树的左右高度差是否不差过1即可。

void Inorder()
{
	_Inorder(_root);
	cout << endl;
}
bool IsBalanceTree()
{
	return _IsBalanceTree(_root);
}
bool _IsBalanceTree(const node* root)
{
	// 空树也是AVL树
	if (nullptr == root)
		return true;
	// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差
	int leftHeight = _Height(root->left);
	int rightHeight = _Height(root->right);
	int diff = rightHeight - leftHeight;
	// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者
    // pRoot平衡因子的绝对值超过1，则⼀定不是AVL树
	if (abs(diff) >= 2)
	{
		cout << root->_value << "高度差异常" << endl;
		return false;
	}
	if (root->bf != diff)
	{
		cout << root->_key << "平衡因子异常" << endl;
		return false;
	}
	// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
	return _IsBalanceTree(root->left) && _IsBalanceTree(root->right);
}
void _Inorder(const node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_Inorder(root->left);
	cout << root->_key << ":" << root->_value<<endl;
	_Inorder(root->right);
}
size_t Size()
{
	return _Size(_root);
}
size_t _Size(const node* parent)
{
	if (parent)
	{
		return 1 + _Size(parent->left)+ _Size(parent->right);
	}
	else
	{
		return 0;
	}
}
size_t Height()
{
	return _Height(_root);
}
size_t _Height(const node* parent)
{
	if (parent)
	{
		return 1 + max(_Height(parent->left), _Height(parent->right));
	}
	else
	{
		return 0;
	}
}

4.2 AVL树的验证

检测一

void TestAVLTree1()
{
	AVL::AVLTree<int, int>t;
	// 常规的测试⽤例
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert(e, e);
	}
	t.Inorder();
	cout << t.IsBalanceTree() << endl;
}

检测二

void TestAVLTree2()
{
	const int N = 100000;
	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();
	AVL::AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(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;
	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;
}

后言

这就是AVL树的深度剖析。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~

文章来源:https://blog.csdn.net/2301_81670477/article/details/144308070
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！

标签：

上一篇：SpringBoot中如何使用事务, 有哪些失效的情况
下一篇：华为OD机试E卷 --最大值--24年OD统一考试（Java & JS & Python & C & C++）

首页 > 基础资料博客日记

【C++笔记】AVL树的深度剖析