【C++高阶(三)】AVL树深度剖析&模拟实现

💓博主CSDN主页:杭电码农-NEO💓

 

⏩专栏分类:C++从入门到精通⏪

 

🚚代码仓库:NEO的学习日记🚚

 

🌹关注我🫵带你学习C++

  🔝🔝

AVL树

• 1. 前言
• 2. AVL树的概念以及特性
• 3. AVL树模拟实现基本框架
• 4. AVL树插入函数深度剖析
• 5. AVL树插入代码剖析(无旋转)
• 6. AVL树的旋转操作深度剖析(一)
• 7. AVL树的旋转操作深度剖析(二)
• 8. AVL树旋转的代码实现
• 9. 总结以及所有代码

1. 前言

如果你不知道什么是二叉搜索树

请一定先阅读这篇文章:

二叉搜索树深度剖析

二叉搜索树如果插入顺序是有序的
那么这棵树的查找效率将会是O(N)
所以说在实际情况下,二叉搜索很少被使用

为了解决二叉搜索树不稳定的问题

于是乎有人提出了AVL树结构,也就是

高度平衡二叉搜索树!

本章重点:

本篇文章着重讲解AVL树的概念以及

定义,并且在模拟实现AVL树前,将AVL

树的插入的情况做系统分析,最后模拟

实现AVL树的插入操作,进一步理解它!

2. AVL树的概念以及特性

AVL树通过一个特性来保证二叉

搜索的平衡性问题: 那就是任一

节点两边的子树高度差不超过1!

高度差一般是右子树高度减左子树高度

由于AVL树的这种特殊性质,使得它的

查找效率是百分百的O(logn),可以说

这是天才的发明,当插入或删除节点时,

高度差不符合要求后,可以通过旋转的

方式来重新让这棵树变成AVL树!

下面,我们一般尝试理解AVL树

一边来模拟实现它!

3. AVL树模拟实现基本框架

首先我们应该想到一点,当高度差

大一1时我们需要做处理,但是我们

怎么知道哪个节点高度差大于1呢?

因此应该在节点中多定义一个整数

来记录当前节点的左右高度差!

AVL树的节点结构体:

template
struct AVLTreeNode   //高度平衡二叉搜索树
{
	AVLTreeNode(const pair& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
	//用三叉链,方便更新祖先的平衡因子
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	pair _kv; //存储的数据
	int _bf; //balance factor平衡因子
};

有了节点的结构体后,定义一下

AVL树的基本结构吧:

template
struct AVLTree
{
	typedef AVLTreeNode Node;
private:
	Node* _root;//定义一个根节点
};

4. AVL树插入函数深度剖析

AVL数的插入有三个步骤:

1. 按照二叉搜索树规则插入节点
2. 插入完成后更新平衡因子
3. 若平衡因子不正确需要采取措施

所以当前目标就是把这三步搞清楚

更新平衡因子规则:

1. 新增在右,父亲的bf加一

   新增在左,父亲的bf减一

2. 更新完成后,父亲的bf==1/-1,说明

   父亲插入前的bf一定是0,并且插入后

   一边高一边低,需要继续向上更新

3. 更新完成后,父亲的bf==0,说明父亲

   在插入前的bf是1/-1,并且插入后两边高度

   一致,就不需要继续往上更新了!

4. 更新完成后,父亲的bf==2/-2,打破

   了平衡,父亲所在的子树要旋转处理

由于旋转处理的过程比较复杂

所以先将除了旋转的所有代码写出来

后再去讨论旋转的话题!

5. AVL树插入代码剖析(无旋转)

话不多说,直接上手!

bool insert(const pair& 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 return false;
		}
		//走到这一步后,已经找到了位置,开空间后插入
		cur = new Node(kv);
		if (parent->_kv.first _right = cur;
		else
			parent->_left = cur;
		//此时new出来的节点的parent还指向空
		cur->_parent = parent;

		//插入完成后,此时需要查看平衡因子来控制平衡
		//沿着插入的位置往上更新平衡因子 
		while (parent)//由于parent需要不断向上更新,所以要使用循环!
		{
			if (cur == parent->_right)
				parent->_bf++;
			else
				parent->_bf--;
			if (parent->_bf == 0)//不用向上更新了
				break;
			else if (parent->_bf == 1 || parent->_bf == -1)//若高度出现变化,需要往上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)//说明parent所在的子树不平衡了,需要旋转处理
			{
				//后面再处理这个过程......
			}
		}
}

关于代码的解释都在注释中,请耐心查看!

6. AVL树的旋转操作深度剖析(一)

首先,旋转一共由四种情况,不管是

哪一种情况,我们的目的都是将原本

不平衡的树变成符合规则的AVL树!

先看两个最简单的例子:

左单选和右单旋:

大概了解了它的规则后,再来看泛型的:

1. 右单旋

   

2. 左单旋:

   

7. AVL树的旋转操作深度剖析(二)

当你了解了前两种最简单的情况后

就可以来看看”双旋”操作了!

还是先看看最简单的例子:

先左旋再右旋

先右旋再左旋

了解了最简单了例子后,直接上手!

8. AVL树旋转的代码实现

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	Node* ppNode = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;
	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
			ppNode->_left = subR;
		else
			ppNode->_right = subR;
		subR->_parent = ppNode;
	}

	subR->_bf = parent->_bf = 0;
}
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	Node* ppNode = parent->_parent;
	subL->_right = parent;
	parent->_parent = subL;
	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
			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);
	subLR->_bf = 0;
	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_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);
	subRL->_bf = 0;
	if (bf == 1)
	{
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else assert(false);
}

你问我我怎么写出代码的?

那是一段痛苦的回忆,代码的验证就交给你们了

代码中对于平衡因子的更新有细节!

9. 总结以及所有代码

AVL树的模拟实现属于了解的内容

并不需要完全掌握,所以同学了只需

理解了AVL树的旋转即可,不要求手撕代码!

(当然前几年有学长面试时被要求手撕了doge)

AVL树模拟实现全部代码:

我的gitee仓库

🔎
下期预告:红黑树树深度剖析 🔍