行业资讯

C++数据结构之AVL树如何实现

发布时间：2022-06-10 09:59:39 作者：zzz
来源：亿速云 阅读：143

这篇文章主要讲解了“C++数据结构之AVL树如何实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C++数据结构之AVL树如何实现”吧！

1.概念

(1)二叉搜索树的缺点

要手撕AVL树，我们首先要知道什么是AVL树。AVL树是在二叉搜索树的基础之上改造的。当我们插入的是一个有序的序列的时候，二叉搜素树会使用一条直线来进行存储，这样并不利于查找。

C++数据结构之AVL树如何实现

当遇到这种情况的时候我们就需要对这棵树来进行调整。AVL树会通过旋转等操作，来规避这种情况。最终满足每一个节点的平衡因子的绝对值<=1，从而达到近似平衡的目的。

节点的平衡因子值=右子树的高度-左子树高度

(2)定义节点

在AVL树中，除了需要定义平衡因子bf之外，还需要定义指向节点父节点的指针。方便我们来进行平衡因子的更新。

struct AVLTreeNode
{
	AVLTreeNode* right;
	AVLTreeNode* left;
	AVLTreeNode* parent;
	pair<int, int> _kv;
	int _bf;
	AVLTreeNode(pair<int, int> kv)
		:right(nullptr)
		,left(nullptr)
		,parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

同时和map一样，我们使用pair类型来进行数据的存储。

2.插入

(1)拆分

AVL树的插入就是AVL树的精髓所在，我们在插入节点的同时还需要对平衡因子进行控制。

AVL树的插入我们可以拆分成五个函数，其中四个为旋转函数，一个为主要的插入函数。

而这个主要的插入函数，我们还可以将其分为三个部分：找节点，插节点，更新平衡因子。而更新平衡因子后就需要判断是否需要进行旋转的操作。

在进行插入之前，我们将插入的节点定义为kv。

(2)找节点与插节点

这一过程与二叉搜索树是相同的，这里就不多赘述了。二叉搜索树

直接上代码：

		//初始化头结点
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//找到要插入节点的位置
		Node* cur = _root;
		Node* parent = nullptr;
		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
			{
				assert(false);
			}
		}
		//插入节点
		cur = new Node(kv);
		if (parent->_kv.first<kv.first)
		{
			parent->right = cur;
			cur->parent = parent;
		}
		else if (parent->_kv.first>kv.first)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			assert(false);
		}

(3)更新平衡因子与旋转

更新平衡因子

每当我们插入一个节点的时候，就需要对该节点的所有父辈节点来进行平衡因子的更新。注意，当插入节点后，只有其父辈节点的平衡因子才会受到影响，而其他节点的平衡因子不会被影响。

可以根据每个节点的parent来找到其父亲节点，从而逐渐向上更新平衡因子。

当遇到以下两种情况平衡因子的更新停止。

1.某一父辈节点的平衡因子为0。

2.更新到根节点。

旋转

当更新之后的平衡因子为2或者-2的时候，不符合AVL树的平衡因子在-1~1之间的定义，此时需要发生旋转。触发旋转的条件与当前节点cur和它的parent有关。

当parent和cur的平衡因子分别为：

(1)2和1，触发左旋

	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}

用一张图来表示一下这个过程：

h表示某树的高度，当在红色部分处插入一个节点时，60的平衡因子变为1，30的平衡因子变为2。

C++数据结构之AVL树如何实现

此时就需要发生旋转：

C++数据结构之AVL树如何实现

通过旋转使树重新变成一棵AVL树，整个过程分为三步：

注意，由于AVL树是三叉树，因此在链接的时候需要将父节点也链接起来。因此在将60的左子树链接到30的右子树的时候，需要进行判空来避免空指针的解引用：

	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}

(2)-2和-1，触发右旋

C++数据结构之AVL树如何实现

C++数据结构之AVL树如何实现

右旋同样分为三步：

	void RotateR(Node* parent)
	{
		Node* cur = parent->left;
		Node* curL = cur->left;
		Node* curR = cur->right;
		Node* parentParent = parent->parent;
		parent->left = curR;
		if (curR)
			curR->parent = parent;
		cur->right = parent;
		parent->parent = cur;
		if (parent == _root)
		{
		    _root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		cur->_bf = 0;
		parent->_bf = 0;
	}

(3)-2和1，左右双旋

当为-2和1或者2和-1的时候，仅仅靠单旋是解决不了问题的，这个时候我们就需要进行双旋：

C++数据结构之AVL树如何实现

左单旋：

C++数据结构之AVL树如何实现

右单旋：

C++数据结构之AVL树如何实现

无论是在红色部分或者蓝色部分插入节点，都会导致发生左右双旋。

左右双旋分为三步：

	void RotateLR(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR =subL->right;
		int bf = subLR->_bf;
		RotateL(parent->left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
	}

(4)2和-1，右左双旋

C++数据结构之AVL树如何实现

右单旋：

C++数据结构之AVL树如何实现

左单旋：

C++数据结构之AVL树如何实现

无论是在红色部分或者蓝色部分插入节点，都会导致发生右左双旋。

右左双旋分为三步：

	void RotateRL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;
		int bf = subRL->_bf;
		RotateR(parent->right);
		RotateL(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);
		}
	}

3.判断

我们可以建立一个函数来判断一棵树是否为AVL树。

我们使用递归来进行这一过程，依次判断各个子树是否为AVL树。

要判断我们就需要知道每一棵树的高度，此时我们需要构造一个求树的高度的函数Height。它也由递归来实现。

	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 IsBalance()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		if ((rightHeight - leftHeight) != root->_bf)
		{
			cout << "现在是：" << root->_bf << endl;
			cout << "应该是：" << rightHeight - leftHeight << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
	}

4.完整代码及测试代码

完整代码

#pragma once
#include<iostream>
#include<assert.h>
#include<math.h>
using namespace std;
struct AVLTreeNode
{
	AVLTreeNode* right;
	AVLTreeNode* left;
	AVLTreeNode* parent;
	pair<int, int> _kv;
	int _bf;
	AVLTreeNode(pair<int, int> kv)
		:right(nullptr)
		,left(nullptr)
		,parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree()
	{
		_root = nullptr;
	}
	void InOrder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->right);
	}
	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 IsBalance()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		if ((rightHeight - leftHeight) != root->_bf)
		{
			cout << "现在是：" << root->_bf << endl;
			cout << "应该是：" << rightHeight - leftHeight << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
	}
	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->left;
		Node* curL = cur->left;
		Node* curR = cur->right;
		Node* parentParent = parent->parent;
		parent->left = curR;
		if (curR)
			curR->parent = parent;
		cur->right = parent;
		parent->parent = cur;
		if (parent == _root)
		{
		    _root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		cur->_bf = 0;
		parent->_bf = 0;
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_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 == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
	}
	//右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;
		int bf = subRL->_bf;
		RotateR(parent->right);
		RotateL(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 InsertNode(pair<int, int> kv)
	{
		//初始化头结点
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//找到要插入节点的位置
		Node* cur = _root;
		Node* parent = nullptr;
		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
			{
				assert(false);
			}
		}
		//插入节点
		cur = new Node(kv);
		if (parent->_kv.first<kv.first)
		{
			parent->right = cur;
			cur->parent = parent;
		}
		else if (parent->_kv.first>kv.first)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			assert(false);
		}
		//更新插入节点以上的平衡因子
		while (parent)
		{
			if (cur == parent->left)
			{
				parent->_bf--;
			}
			else if (cur == parent->right)
			{
				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)
				{
					RotateR(parent);//右单旋
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);//左单旋
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
			}
			else
			{
				assert(false);
			}
		}
	}
private:
	Node* _root;
};

测试代码

#define _CRT_SECURE_NO_WARNINGS 1  
#include"AVLTree.h"
void TestRotateR()
{
	AVLTree t;
	t.InsertNode(make_pair(5, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(0, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestRotateL()
{
	AVLTree t;
	t.InsertNode(make_pair(0, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(5, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void Testbf()
{
	AVLTree t;
	t.InsertNode(make_pair(5, 1));
	t.InsertNode(make_pair(7, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(8, 1));
	t.InsertNode(make_pair(9, 1));
	t.InsertNode(make_pair(6, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(11, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestRL()
{
	AVLTree t;
	t.InsertNode(make_pair(60, 1));
	t.InsertNode(make_pair(50, 1));
	t.InsertNode(make_pair(90, 1));
	t.InsertNode(make_pair(100, 1));
	t.InsertNode(make_pair(80, 1));
	t.InsertNode(make_pair(70, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestLR()
{
	AVLTree t;
	t.InsertNode(make_pair(90, 1));
	t.InsertNode(make_pair(100, 1));
	t.InsertNode(make_pair(60, 1));
	t.InsertNode(make_pair(50, 1));
	t.InsertNode(make_pair(70, 1));
	t.InsertNode(make_pair(80, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
int main()
{
	//TestRotateR();
	//Testbf();
	//TestRotateL();
	//TestRL();
	TestLR();
}

感谢各位的阅读，以上就是“C++数据结构之AVL树如何实现”的内容了，经过本文的学习后，相信大家对C++数据结构之AVL树如何实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！

推荐阅读：
  1. 浅析AVL树算法
  2. AVL树之删除算法

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

c++ avl

上一篇：Java线程优先级变量及功能实例分析

下一篇：C#中的延时函数sleep怎么使用

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号