当前位置： 首页 > article >正文

AVL树（平衡二叉树）的介绍以及相关构建

article 2024/11/17 9:25:51

欢迎光临 ：          羑悻的小杀马特-CSDN博客

目录

一·AVL树的介绍：

二·AVL树的实现：

1·结构框架：

2·节点的插入： 

旋转： 

2·1左单旋：

2.1.1左单旋介绍及步骤：

2.1.2左单旋代码实现：

2.1.3左单旋技巧总结： 

2·2右单旋：

2.2.1右单旋介绍及步骤：

2.2.2右单旋代码实现：

2.2.3右单旋技巧总结：  

2·3左右双旋 ：

2.3.1左右双旋介绍及步骤：

2.3.2左右双旋代码实现：

 2.3.3左右双旋技巧总结：  

2.4右左双旋：

2.4.1右左双旋介绍及步骤：

2.4.2右左双旋代码实现：

  2.4.3右左双旋技巧总结：  

旋转系列的总结：

3.节点的查找：

4.检验AVL树是否平衡： 

三·AVL树的代码汇总： 

一·AVL树的介绍：

AVL树，它的左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树， 通过控制⾼度差去控制平衡。

因此为了能记录它是否平衡这里引入了一个新名词也就是平衡因子：balance factor：某个结点的平衡因子就是它右子树的高度减去左子树的高度，也就是说这个树要是AVL树那么它的平衡因子一定是-1或0或1，否则就要旋转调整（后面会介绍到）。

那为啥高度差不能都为0呢？如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法作为⾼度差是0，因此这样设计是比较合理的

当然因为这样设计就趋近于完全二叉树，那么高度就可以理解为log(n)，那么此时它的增删查改也可以这么认为成log(n)。

二·AVL树的实现：

1·结构框架：

template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指针，后续更新平衡因子可以看到
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	int _bf; // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};
template<typename K,typename V>
class AVLTree {
public:
	using node = AVLTreeNode<K, V>;
private:
	node* _root = nullptr;
};

2·节点的插入： 

这里插入其实和上次写的二叉搜索树的插入差不多，但是就多了控制高度平衡以及对平衡因子的控制操作。

也就是我们找到空位置连接插入后，然后把它的parent处节点的平衡因子更新一下，看一下是否符合条件：然后分情况决定继续向上遍历查找还是停止还是旋转。下面分为三种情况：

1·情况一：恰好为0，也就是原来是-1或者1变来的，此时就不需要向上调整了，为什么呢？因为未插入前parent作为一个节点的右孩子或者左孩子，那么这个节点的假设是左孩子是parent，可以发现此时插入还是不插入这个节点的平衡因子都不变故这时就不需要向上判断。

如：

2·情况二：恰好为1或者-1，也就是从-2或者0变来的，那么此时它变化了，可能会导致上面变化因此还要向上继续遍历找平衡因子的变化。

3·情况三：恰好是-2或者是2，那么此时就不符合平衡规则那就涉及到旋转了（下面会讲到）。

旋转： 

这里旋转是为了什么呢？1·保持搜索树的原则。2·可以降低树的高度。3·可以保证树的平衡。，因此根据parent为2或者-2，以及它的左或右孩子为1或-1的几种情况可以把它分为左单旋，右单旋，左右双旋，右左双旋等。

2·1左单旋：

2.1.1左单旋介绍及步骤：

左单旋肯定是右边高，这里为了方便对下面很多节点，这里直接把剩下的子树抽象化，因为它是平衡二叉树故因此可以把再你插入之前，将要变成2或者-2的节点作为parent以及它的下面分割下来成为抽象的树部分如：

这样的话，左单旋也就是在最右边的h（当然这里的h>=0）高度的下面插入一个节点， 然后通过左单旋变为平衡状态：

这里我们可以看出来，就是把pr的左指针指向parent，parent的右指针指向pr1，但是这里就忽视了最终要的父亲指针，此时也要注意，把pr1（注意是否为空）的父亲指针指向parent，然后保存原先parent的父亲指针（也要判断一下parent是否为根节点从而单独做处理），然后把此时的连接连成pr即可了。

2.1.2左单旋代码实现：

下面展示一下代码：

void RotateL(node* parent) {//左旋
	node* subr = parent->_right;
	node* subrl = subr->_left;
	//处理sublr：
	parent->_right = subrl;
	if (subrl) subrl->_parent = parent;//sublr为空不能访问

	node* pp = parent->_parent;//保存parent的父节点指针
	//调节新旧“parent”位置：
	subr->_left = parent;
	parent->_parent = subr;

	if (pp == nullptr) {
		_root = subr;
		subr->_parent = nullptr;
	}
	else {
		if (parent == pp->_left) pp->_left = subr;
		else pp->_right = subr;
		subr->_parent = pp;
	}
	parent->_bf = subr->_bf = 0;


}

2.1.3左单旋技巧总结： 

技巧总结：这里对于左单旋的操作进行一下总结：把parent节点向下压，然后把 pr的左孩子也就是prl作为parent右孩子，其他注意连接即可。

 

2·2右单旋：

2.2.1右单旋介绍及步骤：

右单旋肯定是左边高，其实也是根左单旋大差不差，下面上图：

这里也和上面类似只不过是把parent的左指针指向plr，pl的右指针指向parent，还有一些其他的注意连接方法，右单旋也就是在最左边的h插入使它变为h+1：

这里与左单旋大差不差，因此就不重复了。

2.2.2右单旋代码实现：

代码：

void RotateR(node* parent) {//右旋
	node* subl = parent->_left;
	node* sublr = subl->_right;

	parent->_left = sublr;
	if (sublr) sublr->_parent = parent;

	node* pp = parent->_parent;
	subl->_right = parent;
	parent->_parent = subl;
	if (pp == nullptr) {
		_root = subl;
		subl->_parent = nullptr;
	}
	else {
		if (parent == pp->_left) pp->_left = subl;
		else pp->_right = subl;
		subl->_parent = pp;
	}
	parent->_bf = subl->_bf = 0;
}

2.2.3右单旋技巧总结：  

技巧总结：把parent向下压，然后把plr与parent的左指针相连，然后注意parent指针的控制即可。 

2·3左右双旋 ：

2.3.1左右双旋介绍及步骤：

这里为什么叫这个呢？其实它的步骤可以分为先对parent的孩子进行左单旋，然后再对parent进行右单旋，即可。这里我们可以这么理解，即就是在进行右单旋的插入图，把节点插在中间的h上即可，而这时根据h>=0;分为了三种情况，对应的是平衡因子的变化：

情况一：就是h为0的情况：那么此时到最后进行旋转后它们的平衡因子都是0。

情况二：插入h的右边，那么旋转后，pl的平衡因子就是-1，其他都是零。

情况三：插入h的左边，那么旋转后parent的平衡因子就是1。

那么我们写代码的时候怎么区分这三种情况就成了写左右双旋的关键了，即这时候我们得到的插入后的plr这个节点的bf一定是如果是0，就是第一种情况，如果是-1就是第三种情况 ，如果是1就是第二种情况，因此可以根据这个进行代码的编写。

步骤1：首先先把pl左旋，然后parent进行右旋，这时大概结构就搞好了，也就是高度OK了，步骤2：接下来就是平衡因子的更改，可以根据我们旋转之前保存的pl的bf分情况进行对旋转后parent，pl和plr三个节点处平衡因子进行更新操作。

2.3.2左右双旋代码实现：

代码展示：

void	RotateLR(node* parent) {//左右双旋
	node* subl = parent->_left;
	node* sublr = subl->_right;
	int bf = sublr->_bf;
	RotateL(subl);
	RotateR(parent);
	if (bf == -1) {//插入的是sublr的左支
		sublr->_bf = 0;
		subl->_bf = 0;
		parent->_bf = 1;

	}
	else if (bf == 1) {//插入的是sublr的右支
		sublr->_bf = 0;
		subl->_bf = -1;
		parent->_bf = 0;

	}
	else if (bf == 0) {//插入前sublr为空
		sublr->_bf = 0;
		subl->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}


}

 2.3.3左右双旋技巧总结：  

技巧总结：就是把parent节点压下来，plr节点提到最上面，之后pl连接它的左指针，parent连接它的右指针，然后plr的左孩子给pl右指针，右孩子给parent左指针。

2.4右左双旋：

2.4.1右左双旋介绍及步骤：

这里其实和左右双旋一样，但是是左旋最初的那个图在中间的h插入，然后也是分为那三种情况。

情况1：h=0，最后插入的就是prl这个节点，那么此时parent，prl和pr平衡因子都是0.

情况2：h>=1,但是插入的那个h的右边，那么此时，pr的bf是0，parent的bf是-1，然后prl的平衡因子就是0。

情况3： h>=1,但是插入的那个h的左边，那么此时，pr的bf是1，parent的bf是0，然后prl的平衡因子就是0。

跟左右双旋一样，那么我们写代码的时候怎么区分这三种情况就成了写右左双旋的关键了，即这时候我们得到的插入后的plr这个节点的bf一定是如果是0，就是第一种情况，如果是-1就是第三种情况 ，如果是1就是第二种情况，因此可以根据这个进行代码的编写。

步骤1：类似，还是pr右旋，然后parent左旋，链接好形状。

步骤2：更新平衡因子，如果第一种情况，此时parent，pr，prl的平衡因子都是0，第二种情况，prl是0，parent是-1，pr是0，第三种情况：prl还是0，parent是0，pr是1。

2.4.2右左双旋代码实现：

代码：

void RotateRL(node* parent) {//右左双旋
	node* subr = parent->_right;
	node* subrl = subr->_left;
	int bf = subrl->_bf;
	RotateR(subr);
	RotateL(parent);
	if (bf == -1) { //插入的是subrl的左支
		subrl->_bf = 0;
		subr->_bf = 1;
		parent->_bf = 0;

	}
	else if (bf == 1) {//插入的是subrl的右支
		subrl->_bf = 0;
		subr->_bf = 0;
		parent->_bf = -1;

	}

	else if (bf == 0) {//插入前subrl为空
		subrl->_bf = 0;
		subr->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}


}

  2.4.3右左双旋技巧总结：  

 技巧总结：就是把parent节点压下来，prl节点提到最上面，之后parent连接它的左指针，pr连接它的右指针，然后prl的左孩子给parent右指针，右孩子给pr左指针。

旋转系列的总结：

这里对上面四种旋转方式如何进行的做一个总结：

1·首先是左单旋和右单旋:可以这么想向哪一边旋转就是另一边高，故就是插入的是最边上才导致增高的，根据此画出相应的图来，都是parent被拽下来，然后少的孩子用旁边的离得最近的孩子补上，其次就是注意各个节点对应的指针的连接。

2·左右双旋和右左双旋:可以这么理解，左右：右单旋的图，只是节点插在了中间的h处（再分三种情况判断平衡因子）右左：左单旋的图，节点插在了中间的h；操作就是：plr或者prl（中间h分出去的节点或者是h=0，新插入的节点）提到最上面，然后pl成左支或者pr成右支，然后被截下来的plr或者prl的左支向左补，右支向右补，最后处理好节点之间的连接即可。

3.节点的查找：

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;
}

4.检验AVL树是否平衡： 

导致其不平衡的条件有两个：要么高度不符合要求，要么就是高度正确而平衡因子未更新正确。

因此可以根据这两个条件来写代码完成检验操作。

int treehight(node* root) {
	if (root == nullptr)  return 0;
	int lefthight = treehight(root->_left);
	int righthight = treehight(root->_right);
	return lefthight > righthight ? lefthight + 1 : righthight + 1;
}

bool _IsBalanceTree(node* root) {//不平衡肯定是在插入数据的时候没有更新正确导致：
	//如高度没有控制好，或者就是高度控制了当往上调整的时候平衡因子没有及时更新导致平衡因子不符合要求
	if (root == nullptr) return true;

	int lefthight = treehight(root->_left);
	int righthight = treehight(root->_right);
	int gap = abs(lefthight - righthight);
	if (gap >= 2)
	{
		cout << root->_kv.first << ":高度存在问题" << endl;
		return false;
	}
	if (abs(root->_bf) != gap) {
		cout << root->_kv.first << ":平衡因子存在问题"<< endl;
		return false;
	}
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);

}

这里顺便说一下删除操作：如果没找到此节点就直接返回了，要么就是删除的是叶子节点直接删除就可，要么是删除一个节点，它的左孩子为空或者右孩子为空，那么此时删除这个节点后，把另一端不为空的孩子补过去，最后一种就是要删除节点的 左右孩子都不为空，此时就要类似二叉搜索树删除一样找替代的孩子，即此节点右孩子一直向左遍历找到最后一个节点与它替换在完成间接删除操作。这里就不做操作了，大致就是这个意思。

三·AVL树的代码汇总： 

#pragma once
#include<iostream>
#include<assert.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指针，后续更新平衡因子可以看到
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	int _bf; // balance factor

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

	

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr) {
			_root = new node(kv);
			return true;
		}
		else {
			//寻找空位置进行插入：
			node* cur = _root;
			node* parent = nullptr;
			while (cur) {
				if (cur->_kv.first > kv.first) {
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first) {
					parent = cur;
					cur = cur->_right;
				}
				else {
					return false;
				}
			}

			//插入：
			cur = new node(kv);
			if (kv.first < parent->_kv.first) parent->_left = cur;
			else parent->_right = cur;
			cur->_parent = parent;
			//更新平衡因子:平衡更新完要么找到parent的bf等于0，要么找到了root发现它的平衡因子还是1或-1
			//保持parent始终是cur的父亲
			while (parent) {//cur仍旧是当前插入的节点
				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 = cur->_parent;
				}
				else if (parent->_bf == 2 || parent->_bf == -2) {
					//判断如何旋转：
					if (parent->_bf == 2 && parent->_right ->_bf== -1) {
						RotateRL(parent);
					}
					else if (parent->_bf == -2 && parent->_left->_bf == 1) {
						RotateLR(parent);
					}
					else if (parent->_bf == 2 && parent->_right->_bf == 1) {
						RotateL(parent);
					}
					else if (parent->_bf == -2 && parent->_left->_bf ==-1) {
						RotateR(parent);
					}

					else {
						assert(false);
					}
					break;//这里由于给它旋转后肯定保证了parent出平衡因子为0，故不用上调了

				}
				else assert(false);
			}
			return true;

		}

	}


	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;
	}

	int treehight(node* root) {
		if (root == nullptr)  return 0;
		int lefthight = treehight(root->_left);
		int righthight = treehight(root->_right);
		return lefthight > righthight ? lefthight + 1 : righthight + 1;
	}
	
	void InOrder() {
		_inorder(_root);
	}
	bool IsBalanceTree() {
		 return _IsBalanceTree(_root);
	}
private:

	void RotateL(node* parent) {//左旋
		node* subr = parent->_right;
		node* subrl = subr->_left;
		//处理sublr：
		parent->_right = subrl;
		if (subrl) subrl->_parent = parent;//sublr为空不能访问

		node* pp = parent->_parent;//保存parent的父节点指针
		//调节新旧“parent”位置：
		subr->_left = parent;
		parent->_parent = subr;

		if (pp == nullptr) {
			_root = subr;
			subr->_parent = nullptr;
		}
		else {
			if (parent == pp->_left) pp->_left = subr;
			else pp->_right = subr;
			subr->_parent = pp;
		}
		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;

		node* pp = parent->_parent;
		subl->_right = parent;
		parent->_parent = subl;
		if (pp == nullptr) {
			_root = subl;
			subl->_parent = nullptr;
		}
		else {
			if (parent == pp->_left) pp->_left = subl;
			else pp->_right = subl;
			subl->_parent = pp;
		}
		parent->_bf = subl->_bf = 0;
	}

	void	RotateLR(node* parent) {//左右双旋
		node* subl = parent->_left;
		node* sublr = subl->_right;
		int bf = sublr->_bf;
		RotateL(subl);
		RotateR(parent);
		if (bf == -1) {//插入的是sublr的左支
			sublr->_bf = 0;
			subl->_bf = 0;
			parent->_bf = 1;

		}
		else if (bf == 1) {//插入的是sublr的右支
			sublr->_bf = 0;
			subl->_bf = -1;
			parent->_bf = 0;

		}
		else if (bf == 0) {//插入前sublr为空
			sublr->_bf = 0;
			subl->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}


	}

	void RotateRL(node* parent) {//右左双旋
		node* subr = parent->_right;
		node* subrl = subr->_left;
		int bf = subrl->_bf;
		RotateR(subr);
		RotateL(parent);
		if (bf == -1) { //插入的是subrl的左支
			subrl->_bf = 0;
			subr->_bf = 1;
			parent->_bf = 0;

		}
		else if (bf == 1) {//插入的是subrl的右支
			subrl->_bf = 0;
			subr->_bf = 0;
			parent->_bf = -1;

		}

		else if (bf == 0) {//插入前subrl为空
			subrl->_bf = 0;
			subr->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}


	}



	void _inorder(node* root) {
		if (root == nullptr) return;
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_inorder(root->_right);

		
	}

	bool _IsBalanceTree(node* root) {//不平衡肯定是在插入数据的时候没有更新正确导致：
		//如高度没有控制好，或者就是高度控制了当往上调整的时候平衡因子没有及时更新导致平衡因子不符合要求
		if (root == nullptr) return true;

		int lefthight = treehight(root->_left);
		int righthight = treehight(root->_right);
		int gap = abs(lefthight - righthight);
		if (gap >= 2)
		{
			cout << root->_kv.first << ":高度存在问题" << endl;
			return false;
		}
		if (abs(root->_bf) != gap) {
			cout << root->_kv.first << ":平衡因子存在问题"<< endl;
			return false;
		}
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);

	}
	node* _root = nullptr;
};

 

 这些也仅是个人对AVL有限的理解，希望大佬多多指导。

 


http://www.kler.cn/a/324073.html

相关文章：

  • CentOS7.9 源码编译 FreeSWITCH 1.10.12
  • 后端——接口文档（API）
  • SpringBoot（5）-SpringSecurity
  • 跨域请求解决的核心
  • 智能化护士排班系统的设计与实现（文末附源码）
  • 华为数字化转型的本质为何是管理变革
  • Augular 学习步骤建议
  • 并查集 (Union-Find) ：从基础到优化
  • C++学习笔记（35）
  • 数组的练习
  • 域 缺省参数 函数重载 引用
  • 828华为云征文｜部署基于 LLM 的私有知识库系统 AnythingLLM
  • Magnific推V2图像生成服务 可直出4K图像
  • 发掘3D文件格式的无限潜力：打造沉浸式虚拟世界
  • 数据结构：树（并查集）
  • LeetCode[中等] 138. 随机链表的复制
  • 9.28学习
  • 人工智能的基本概念与发展历程
  • 【第十四章：Sentosa_DSML社区版-机器学习之时间序列】
  • 从碎片到整合：EasyCVR平台如何重塑城市感知系统的视频数据生态
  • 【matlab画多纵坐标图像】
  • io流（学习笔记04）io流的概述
  • 看Threejs好玩示例，学习创新与技术(Noise)
  • 饿了么 表单 回填后 无法更新 问题
  • Rider快捷键笔记
  • 计算机视觉方面的一些模块