【C++进阶学习】第七弹——AVL树——树形结构存储数据的经典模块

GG Bond1

发布于 2024-07-20 17:08:24

330

发布于 2024-07-20 17:08:24

文章被收录于专栏：C/C++葵花宝典

二叉搜索树：【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客

前言：

在前面我们学习二叉搜索树的时候，虽然大部分情况下二叉搜索树的效率都是很高的，但是如果是一组相对有序的数字，我们用二叉搜索树来排序就会显得比较麻烦了，因此，AVL树就出现了，下面就让我们一起来学习以下AVL树的相关知识

一、AVL树的概念

AVL树实际上就是特殊的二叉搜索树，是对二叉搜索树的改进，我们在用树形结构来查找或操作数据的时候，一般都是要从树根一层一层往下找，所以树高越低，效率越高，但是二叉搜索树在有些场景下比较麻烦，比如一个相对有序的数组{2，1，3，4，5，6}

这样一个数组如果通过二叉搜索树处理就会显得层数太多，效率很低所以人们也就有了这样一种思考：我们可不可以通过某种操作让左右子树的高度差不超过1，这样就能极大的提高效率，这就是AVL树的概念

AVL树中任何节点的左右子树的高度差（平衡因子）绝对值不超过1。这意味着树始终保持平衡，避免了二叉搜索树在节点插入或删除后可能出现的退化现象。

二、AVL树的原理与实现

了解了AVL树的基本内容之后，接下来我们就来一步一步学习以下AVL树的原理到底是什么以及如何实现一个AVL树：

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)     //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1
	{}
};

AVL树的节点操作与二叉搜索树还是比较相似的，都有左子树右子树和父亲节点的叉式结构，比较不同的是加入了一个平衡因子

AVL树的插入

实现AVL树的重点就是解决AVL树的插入问题，而解决插入问题最关键的就是要做到如何让左右子树高度的绝对值适合不大于1，我们是通过合理的旋转来实现的，而且需要旋转的情况也是分为四种的：

RR型：左旋 LL型：右旋 RL型：先右旋，再左旋 LR型：先左旋，再右旋

下面我们来看这样几个例子：

1、RR型（左旋）

2、LL型（右旋）

3、LR型（先左旋，再右旋）

4、RL型（先右旋，再左旋）

操作与3正好相反，不过多赘述

下面就让我们看一下插入的代码：

	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 (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;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		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)
				{
					//左单旋
					RotateL(parent);
					break;
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					//右单旋
					RotateR(parent);
					break;
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					//RL型
					RotateRL(parent);
					break;
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					//LR型
					RotateLR(parent);
					break;
				}
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

AVL树的旋转

	void RotateL(Node* parent)   //左单旋（RR型）
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;

		parent->_right = subRL;
		subR->_left = parent;
		
		if(subRL)
		   subRL->_parent = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
		parent->_parent = subR;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	void RotateR(Node* parent)   //右单旋（LL型）
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;

		parent->_left = subLR;
		subL->_right = parent;

		if (subLR)
		{
			subLR->_parent = parent;
		}
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
		parent->_parent = subL;
		subL->_bf = parent->_bf = 0;
	}
	void RotateRL(Node* parent)      //先右单旋，再左单旋（RL型）
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

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

		if (bf == 0)
		{
			//subRL自己就是新增点
			parent->_bf = subR->_bf = 0;
		}
		else if (bf == -1)
		{
			//subRL的左子树上新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			//subRL的右子树上新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	void RotateLR(Node* parent)      //先左单旋，再右单旋（LR型）
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

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

		if (bf == 0)
		{
			//subLR自己就是新增点
			parent->_bf = subL->_bf = 0;
		}
		else if (bf == -1)
		{
			//subLR的左子树上新增
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 1)
		{
			//subLR的右子树上新增
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}

AVL树的打印

AVL树的打印与二叉搜索树一致，都是中序打印，我们就直接来看代码了

	//中序打印
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		cout << root->_kv.first << " ";
		_Inorder(root->_right);
	}

AVL树的检查

检查是否为AVL树，一方面我们可以通过打印的结果先来判断一下它是不是二叉搜索树，然后我们可以通过比较左右子树的高度差来判断它是否为AVL树（根据前面可知AVL树左右子树高度差最大为1）

	//检查是否为AVL树
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	int _High(Node* root)
	{
		if (root == nullptr)
			return 0;

		int LeftHigh = _High(root->_left);
		int RightHigh = _High(root->_right);
		return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		int LeftHigh = _High(root->_left);
		int RightHigh = _High(root->_right);
		if (RightHigh - LeftHigh != root->_bf)
		{
			cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;
			return false;
		}
		return abs(LeftHigh- RightHigh) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

三、实现AVL树的完整代码

AVLTree.h

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)     //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	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 (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;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		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)
				{
					//左单旋
					RotateL(parent);
					break;
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					//右单旋
					RotateR(parent);
					break;
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					//RL型
					RotateRL(parent);
					break;
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					//LR型
					RotateLR(parent);
					break;
				}
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

	void RotateL(Node* parent)   //左单旋（RR型）
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;

		parent->_right = subRL;
		subR->_left = parent;
		
		if(subRL)
		   subRL->_parent = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
		parent->_parent = subR;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	void RotateR(Node* parent)   //右单旋（LL型）
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;

		parent->_left = subLR;
		subL->_right = parent;

		if (subLR)
		{
			subLR->_parent = parent;
		}
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
		parent->_parent = subL;
		subL->_bf = parent->_bf = 0;
	}
	void RotateRL(Node* parent)      //先右单旋，再左单旋（RL型）
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

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

		if (bf == 0)
		{
			//subRL自己就是新增点
			parent->_bf = subR->_bf = 0;
		}
		else if (bf == -1)
		{
			//subRL的左子树上新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			//subRL的右子树上新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	void RotateLR(Node* parent)      //先左单旋，再右单旋（LR型）
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

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

		if (bf == 0)
		{
			//subLR自己就是新增点
			parent->_bf = subL->_bf = 0;
		}
		else if (bf == -1)
		{
			//subLR的左子树上新增
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 1)
		{
			//subLR的右子树上新增
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}

	//中序打印
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		cout << root->_kv.first << " ";
		_Inorder(root->_right);
	}

	//检查是否为AVL树
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	int _High(Node* root)
	{
		if (root == nullptr)
			return 0;

		int LeftHigh = _High(root->_left);
		int RightHigh = _High(root->_right);
		return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		int LeftHigh = _High(root->_left);
		int RightHigh = _High(root->_right);
		if (RightHigh - LeftHigh != root->_bf)
		{
			cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;
			return false;
		}
		return abs(LeftHigh- RightHigh) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
private:
	Node* _root = nullptr;
};

test.c

//AVL树
#include"AVLTree.h"
int main()
{
	int a[] = { 16,3,7,11,9,26,18,14,15 };   
	AVLTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.Inorder();
	cout << "输出1代表是AVL树，输出0代表不是：" << t.IsBalance() << endl;

	return 0;
}

运行结果：