【C++】AVL树-天翼云

1. 什么是AVL树？

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。 因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)， 即可降低树的高度，从而减少平均搜索长度。

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

他的左右子树都是AVL树

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

通过引入平衡因子来控制AVL树的左右子树高度差，平衡因子 = 右子树高度 - 左子树高度

【C++】AVL树

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

2. AVL树节点的定义

对于AVL树，我们需要增加一个变量bf(平衡因子)来控制树的状态。并新增一个父节点指针，用来指向该节点的父节点。这是为了方便后面插入节点时修改父节点的平衡因子。

template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;   // 左孩子节点
	AVLTreeNode<K, V>* _right;  // 右孩子节点
	AVLTreeNode<K, V>* _parent; // 父节点
	pair<K, V> _kv;
	int _bf;
	//构造函数
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

3. AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

按照二叉搜索树的方式插入新节点

调整节点的平衡因子

pParent平衡因子的调整

pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

如果pCur插入到pParent的左侧，只需给pParent的平衡因子 -1 即可

如果pCur插入到pParent的右侧，只需给pParent的平衡因子 +1 即可

平衡因子的更新和旋转处理

【C++】AVL树

下面我们举一个例子来说明更新完平衡因子后需要调整旋转处理的情况：

【C++】AVL树

bool Insert(const pair<K, V>& kv)
{
	//搜索树的插入过程
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	//链接节点
	cur = new Node(kv);
	if (parent->_kv.first > kv.first)
		parent->_left = cur;
	else
		parent->_right = cur;

	cur->_parent = parent;//链接父节点

	//更新平衡因子
	while (parent)
	{
		if (cur == parent->_right)
			parent->_bf++;
		else
			parent->_bf--;

		if (parent->_bf == 1 || parent->_bf == -1)
		{
			//继续向上更新平衡因子
			parent = parent->_parent;
			cur = cur->_parent;
		}
		else if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//旋转处理
			if (parent->_bf == 2 && cur->_bf == 1)
				RotateL(parent);//左单旋
			else if (parent->_bf == -2 && cur->_bf == -1)
				RotateR(parent);//右单旋
			else if (parent->_bf == -2 && cur->_bf == 1)
				RotateLR(parent);//左右双旋
			else if (parent->_bf == 2 && cur->_bf == -1)
				RotateRL(parent);//右左双旋
			else
				assert(false);
			break;
		}
		else
			assert(false);
	}
	return true;
}

4. AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡（当节点的平衡因子为 2/-2 时），此时必须调整以这个节点为根的子树的结构，对这棵子树进行旋转处理。
旋转的目的是：

让这棵子树的左右高度差不超过1；

旋转时保持其是搜索树的结构；

更新平衡因子；

使子树的高度和插入前保持一致，从而不会继续影响上一层，旋转结束；

根据节点插入位置的不同，AVL树的旋转也有着不同的情况：

左单旋： 新节点插入较高右子树的右侧—右右；

右单旋： 新节点插入较高左子树的左侧—左左；

先左单旋再右单旋： 新节点插入较高左子树的右侧—左右：

先右单旋再左单旋： 新节点插入较高右子树的左侧—右左；

4.1 左单旋

当满足右子树比左子树高1且在右子树的右边插入节点时，右子树会比左子树高度高2，此时需要以parent为父节点进行左单旋。左单旋的抽象图如下：

抽象图：

【C++】AVL树

对于左单旋来说，可以分为三种子情况。任何一棵子树进行左单旋，都会是下面这三种子情况之一：h==0、h==1 和 h==2

具象图：

【C++】AVL树

这里我们需要注意的是当h==2时，对于c来说一定是x形状，但对于a、b来说一定是x、y、z中的一种。这里一共9种情况。

由于c的高度发生变化一定会引发旋转，在1、2、3、4四个位置任意一个位置插入都会引发30的平衡因子变为2，一共有4种情况。所以和上面的9种情况一起组合一下共有36种情况。

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

	parent->_right = subRL;

	//这里我们需要注意一下，subRL有可能为空
	if (subRL)
		subRL->_parent = parent;

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

	//判断父节点是否为_root节点
	if (parent == _root) {
		_root = subR;
		_root->_parent = nullptr;
	}
	else {
		if (parent == ppnode->_left)
			ppnode->_left = subR;
		else
			ppnode->_right = subR;
		subR->_parent = ppnode;
	}

	//调节平衡因子
	parent->_bf = subR->_bf = 0;
}

4.2 右单旋

当满足左子树的高度比右子树高1且在左子树的左边插入节点时，左子树的高度会比右子树高2，此时需要对parent为节点进行右单旋。

抽象图：

【C++】AVL树

具象图：

【C++】AVL树

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

	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	
	//保存parent节点的_parent节点
	Node* ppnode = parent->_parent;

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

	//判断parent节点是否为_root节点
	if (parent == _root)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == ppnode->_left)
			ppnode->_left = subL;
		else
			ppnode->_right = subL;
		subL->_parent = ppnode;
	}
	//调节平衡因子
	subL->_bf = parent->_bf = 0;
}

在这里我们稍微总结一下：左单旋和右单旋都是插入后一边高且为直线的情况，当插入后为折线时，单旋已经解决不了我们的需求了，这时就需要引入双旋来解决了。

4.3 左右双旋

左右双旋的情况如下，当a、d是高度为h的AVL子树时，b、c是高度为h-1的AVL子树，90是这棵树的根，当满足 “左子树比右子树高度高1且在左子树的右侧插入节点时” 我们需要先左单旋，再右单旋。

抽象图：

【C++】AVL树

具象图：

【C++】AVL树

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	
	int bf = subLR->_bf;
	//先以左子树为轴进行左单旋--30
	RotateL(parent->_left);
	//以根节点为轴进行右单旋--90
	RotateR(parent);
	//更新平衡因子
	if (bf == -1)
	{
		parent->_bf = 1;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else
		assert(false);
}

4.4 右左双旋

右左双旋满足的是右子树比左子树高度高1且在右子树的左侧插入节点时，所以我们需要先进行右单旋，在进行左单旋。

具象图如下：

【C++】AVL树

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

	int bf = subRL->_bf;

	RotateR(parent->_right);//以右子树为轴进行右单旋--90
	RotateL(parent);//以根节点为轴进行左单旋--30

	//调整平衡因子
	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 if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else
		assert(false);
}

这里我们来总结一下：

假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2 或者 -2，则分以下情况考虑旋转：

parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 ssubR

当 subR 的平衡因子为 1 时，执行左单旋；

当 subR 的平衡因子为 -1 时，执行右左双旋；

parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent的左子树的根为 subL

当 subL 的平衡因子为 -1 时，执行右单旋；

当 subL 的平衡因子为 1 时，执行左右双旋。

旋转完成后，原 parent 为根的子树的高度降低为未插入时的高度，此时这棵子树已经平衡，不需要再向上更新。

5. AVL树的验证

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

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

验证其为二叉搜索树： 写一个中序遍历，将遍历结果依次打印，如果结果为有序，则说明该AVL树为一棵二叉搜索树。

验证其为平衡树： 求出每个节点的左右子树高度，看他们之差是否为 -1/0/1，同时在验证平衡的过程中将不符合要求的节点的key值打印出来，方便发生错误时进行调试。

//求树的高度
int Height()
{
	return _Height(_root);
}
int _Height(Node* root)
{
	if (root == nullptr)
		return 0;
	int leftHight = _Height(root->_left);
	int rightHight = _Height(root->_right);

	return leftHight > rightHight ? leftHight + 1 
	: rightHight + 1;
}
//判断是否为平衡二叉树
bool IsBalance()
{
	return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
	if (root == nullptr)
		return true;
	//根据平衡因子判断二叉树是否为平衡二叉树
	int leftH = _Height(root->_left);
	int rightH = _Height(root->_right);
	
	if (rightH - leftH != root->_bf) {
		cout << "节点的平衡因子异常" << endl;
		return false;
	}

	//这里需要判断每棵子树的高度差及平衡因子是否符合要求
	return abs(rightH - leftH) < 2
		&& _IsBalance(root->_left)
		&& _IsBalance(root->_right);
}

6. AVL树的性能

由于 AVL 树是一棵平衡二叉搜索树，其每个节点的左右子树的高度差都不超过1，所以 AVL 树是无限接近于满二叉树的，那么 AVL 进行查询的时间复杂度就无限接近于 O(logN)，所以 AVL 进行查询非常高效；

但是如果要对 AVL 树做一些结构修改的操作，其性能就比较低；因为 AVL 树插入时需要调整其达到平衡，那么进行旋转的次数就比较多，更差的是在删除时，有可能要一直让旋转持续到根的位置；因此如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变) 或数据较少进行插入和删除，则可以考虑 AVL 树，但如果一个结构经常进行修改，AVL 则不太适合。

7. AVL树代码实现

template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;   // 左孩子节点
	AVLTreeNode<K, V>* _right;  // 右孩子节点
	AVLTreeNode<K, V>* _parent; // 父节点
	pair<K, V> _kv;
	int _bf;
	//构造函数
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

template <class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	//insert的实现
	bool Insert(const pair<K, V>& kv)
	{
		//搜索树的插入过程
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		//链接节点
		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
			parent->_left = cur;
		else
			parent->_right = cur;

		cur->_parent = parent;//链接父节点

		//更新平衡因子
		while (parent)
		{
			if (cur == parent->_right)
				parent->_bf++;
			else
				parent->_bf--;

			if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续向上更新平衡因子
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转处理
				if (parent->_bf == 2 && cur->_bf == 1)
					RotateL(parent);//左单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
					RotateR(parent);//右单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
					RotateLR(parent);
				else if (parent->_bf == 2 && cur->_bf == -1)
					RotateRL(parent);
				else
					assert(false);
				break;
			}
			else
				assert(false);
		}
		return true;
	}

	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//判断是否为平衡二叉树
	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	//求树的高度
	int Height()
	{
		return _Height(_root);
	}

private:
	// 判断是否为平衡二叉树子函数
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		//根据平衡因子判断二叉树是否为平衡二叉树
		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);
		
		if (rightH - leftH != root->_bf) {
			cout << "节点的平衡因子异常" << endl;
			return false;
		}

		//这里需要判断每棵子树的高度差及平衡因子是否符合要求
		return abs(rightH - leftH) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

	//求树的高度
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHight = _Height(root->_left);
		int rightHight = _Height(root->_right);

		return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
	}

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

		parent->_right = subRL;

		//这里我们需要注意一下，subRL有可能为空
		if (subRL)
			subRL->_parent = parent;

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

		//判断父节点是否为_root节点
		if (parent == _root) {
			_root = subR;
			_root->_parent = nullptr;
		}
		else {
			if (parent == ppnode->_left)
				ppnode->_left = subR;
			else
				ppnode->_right = subR;
			subR->_parent = ppnode;
		}

		//调节平衡因子
		parent->_bf = subR->_bf = 0;
	}

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

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		
		//保存parent节点的_parent节点
		Node* ppnode = parent->_parent;

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

		//判断parent节点是否为_root节点
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppnode->_left)
				ppnode->_left = subL;
			else
				ppnode->_right = subL;
			subL->_parent = ppnode;
		}
		//调节平衡因子
		subL->_bf = parent->_bf = 0;
	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		int bf = subLR->_bf;

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

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

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

		int bf = subRL->_bf;

		RotateR(parent->_right);//右单旋
		RotateL(parent);//左单旋

		//调整平衡因子
		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 if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
			assert(false);
	}

	//中序遍历子函数
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

//验证是否为AVL树
void TestAVLTree1()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
		cout << e << "插入：" << t1.IsBalance() << endl;
	}

	t1.InOrder();
	cout << t1.IsBalance() << endl;
}
//用N个测试用例来验证AVL树
void TestAVLTree2()
{
	srand(time(0));
	const size_t N = 100000;
	AVLTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		t.Insert(make_pair(x, x));
		//cout << t.IsBalance() << endl;
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
	cout << t.Height() << endl;
}

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

【C++】AVL树

【C++】AVL树

1. 什么是AVL树？

2. AVL树节点的定义

3. AVL树的插入

4. AVL树的旋转

4.1 左单旋

4.2 右单旋

4.3 左右双旋

4.4 右左双旋

5. AVL树的验证

6. AVL树的性能

7. AVL树代码实现

相关文章

查看RISC-V版本的gcc中默认定义的宏

《剑指Offer》搜索算法题篇——更易理解的思路~

复杂度的OJ练习

《剑指Offer》按之字形顺序打印二叉树——最容易理解的思路，两分钟学会~

《剑指Offer》二叉搜索树的第k个节点——真没你想象中那么难，一招教你秒杀它~

【牛客网+LeetCode】链表 OJ强训题——高效解法

背包问题——“0-1背包”，“完全背包”（这样讲，还能不会？）

多源BFS问题(4)_地图分析

递归,搜索,回溯算法(3)之穷举,暴搜,深搜,回溯,剪枝

多源BFS问题(2)_飞地的数量

作者介绍

最新文章

复杂度的OJ练习

【数据结构】详细介绍串的简单模式匹配——朴素模式匹配算法

超级好用的C++实用库之sha256算法

【C/C++算法】从浅到深学习--- 简单模拟算法（图文兼备 + 源码详解）

Java数据结构之《最短路径》

软件设计师教程（第5版）第4章 操作系统知识（更新中）

热门文章

C/C++泛型编程实现数据结构之栈

Lambda函数

Python：关于有序序列元素查找

QT中多线程的使用

0030 简单的四则运算 c/c++

C++虚函数知识点总结

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

解析conf配置文件的c++神器

c++入门篇之C++ 引用

Java 应用的限流策略：保护系统稳定性

C++算法：滑动窗口与双指针

Java中的Heap（堆）（如果想知道Java中有关堆的知识点，那么只看这一篇就足够了！）

MFC编程 -- 判断是否按下ctrl和shift键

软件设计师教程（第5版）第4章操作系统知识（更新中）