会旋转的树,你见过吗?

news/2024/5/19 23:41:17 标签: 数据结构, 推荐算法, 算法, 高阶数据结构

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:AVL树的实现，旋转的详细分析，抽象图，具体图分步骤讲解，保姆级教学。
金句分享:
✨人生若只如初见，✨
✨何事秋风悲画扇。✨

前言

前面我们学习了二叉搜索树,二叉搜索树如果左右子树高度相差不大,那么效率还是可观的,比如:满二叉搜索树的查询效率为 O(logn).
但是,如果插入的数据是有序的,或者大部分有序,则会导致 “二叉搜索树” 退化为类似于链表的结构.
那链表查询数据的时间复杂度牛牛就不用多说了吧.答案: O(n)

示例:
在这里插入图片描述

目录

  • 前言
  • 一、AVL树的介绍
  • 二、AVL树的模拟实现
    • 🍭结点类
    • 🍔AVL树的框架:
    • 2.1 "插入"操作(重点)
      • ①:右旋
        • (1) 右旋具体图:
        • (2)右旋抽象图:
      • ②左旋:
        • (1)左旋具体图:
        • (2)左旋抽象图
      • ③右左双旋
        • （1）右左双旋具体图
        • （2）右左双旋抽象图
      • ④左右双旋
        • （1）左右双旋具体图
        • （2）左右双旋抽象图
      • "插入"操作的代码实现:
    • 2.2 中序遍历:
    • 2.3 AVL树的"高度"
    • 2.4 验证AVL树
  • 结语

一、AVL树的介绍

AVL树是一种自"平衡二叉搜索树"，它的每个节点存储一个关键字，具有以下特点：

  1. 每个节点的左右子树高度差至多为1，也就是说，AVL树的任何一个节点的左右子树高度差不超过1。

  2. 对于任意一个节点，其左子树和右子树都是一个AVL树。

  3. AVL树中的每个节点都能保证左子树中的所有节点小于当前节点的关键字，右子树中的所有节点大于当前节点的关键字。(也就是满足二叉搜索树的性质)

如果我们定义 平衡因子=右子树的高度-左子树的高度
则树中每个结点的平衡因子的绝对值 不超过1 即可以为( 1 0 -1三种)
1:表示右子树比左子树高.
0:表示左子树和右子树一样高.
-1:表示左子树比右子树高.

每当向AVL树中插入、删除节点时，AVL树会自动地进行旋转操作将树变为平衡状态，从而保证了AVL树的平衡性。

在这里插入图片描述
会旋转的树才够强,AVL树的查询数据的时间复杂度总是控制在 O(logn)量级.

二、AVL树的模拟实现

补充知识点:
在c++中 pair类是一个模板类,用于将两个值组成一个单元,也就是我们称为的键值对.

template<class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;  // 第一个元素
    T2 second; // 第二个元素

    // 默认构造函数
    pair() : first(T1()), second(T2()) {}
    // 初始化构造函数
    pair(const T1& x, const T2& y) : first(x), second(y) {}
};

🍭结点类

没错,AVL树是三叉树,为了方便旋转,我们需要多存储一个指针域(_parent) ,指向父节点.

template<class K, class V>
struct AVLTreeNode
{
	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)
	{}
};

🍔AVL树的框架:

// AVL树的结构
template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;		
public:
	AVLTree()
		: _root(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const pair<K, V>& kv);
	void  InOrder();

	// AVL树的验证
	bool IsAVLTree(){
		return _IsAVLTree(_root);
	}

private:
	// 根据AVL树的概念验证proot是否为有效的AVL树
	bool _IsAVLTree(Node* root);
	size_t _Height(Node* root);
	void  _InOrder(Node* root);
	
	// 右单旋
	void RotateR(Node* parent);
	// 左单旋
	void RotateL(Node* parent);
	// 右左双旋
	void RotateRL(Node* parent);
	// 左右双旋
	void RotateLR(Node* parent);

private:
	Node* _root;
};

2.1 "插入"操作(重点)

注意: 本篇实现的AVL树,平衡因子是右子树高度—左子树高度.

故:
当新增结点在父亲结点的左边时,左子树的高度+1,则平衡因子-1.
当新增结点在父亲结点的右边时,右子树的高度+1,则平衡因子+1.
在这里插入图片描述
子树的平衡因子变化,可能会影响祖先路径上的结点,需要继续向上更新.

(1) 当新增结点后,父节点的平衡因子变成0,则插入结束.
在这里插入图片描述
(2) 当新增结点后,父节点的平衡因子变成1或者-1,则需要向上更新.

在这里插入图片描述
(3)当新增结点后,父节点的平衡因子变成2或者-2需要旋转.

①:右旋

当继续向上更新到父节点是平衡因子-2时,则需要右旋.
因为左边比右边高,需要旋转到右边.使其平衡.

(1) 右旋具体图:

在这里插入图片描述

关键步骤:

使cur成为新的父节点
cur的右孩子,成为parent的左孩子
parent成为cur的右孩子
在这里插入图片描述

(2)右旋抽象图:

在这里插入图片描述

更新平衡因子:
从抽象图可以看出,右旋旋转后,平衡因子cur parent都可以无脑设置为0.

代码实现:

//右旋
template<class K,class V>
void AVLTree<K,V>::RotateR(Node* parent)
{
	Node* ppnode = parent->_parent;
	Node* cur = parent->_left;
	Node* cur_right = cur->_right;

	//cur的右子树变成parent的左子树
	if (cur_right) {					//cur_right  可能不存在
		parent->_left = cur_right;
		cur_right->_parent = parent;//保持三叉连
	}
	else {
		parent->_left = nullptr;
	}
	//parent变成cur的右子树
	cur->_right = parent;		
	parent->_parent = cur;//保持三叉连


	if (ppnode) {		
		cur->_parent = ppnode;

		if (ppnode->_left == parent) {		//如果是上面的左子树
			ppnode->_left = cur;
		}
		else {
			ppnode->_right = cur;			//如果是上面的右子树
		}
	}
	else {									//如果ppnode是nullptr,则代表parent为root
		_root = cur;
		cur->_parent = nullptr;
	}
	
	parent->_bf = 0;
	cur->_bf = 0;
}

②左旋:

当继续向上更新到父节点平衡因子是2时,则需要左旋.
因为右边比左边高,需要旋转到左边,使其平衡.

(1)左旋具体图:

在这里插入图片描述
关键步骤:

使cur成为新的父节点
cur的左孩子,成为parent的右孩子
parent成为cur的左孩子
在这里插入图片描述

(2)左旋抽象图

在这里插入图片描述

更新平衡因子:
从抽象图可以看出,左旋旋转后,平衡因子cur parent都可以无脑设置为0.

代码实现:

//左旋
template<class K, class V>
void AVLTree<K, V>::RotateL(Node* parent)
{
	Node* ppnode = parent->_parent;
	Node* cur = parent->_right;
	Node* cur_left = cur->_left;

	//cur的右子树变成parent的左子树
	if (cur_left) {					//cur_right  可能不存在
		parent->_right = cur_left;
		cur_left->_parent = parent;//保持三叉连
	}
	else {
		parent->_right = nullptr;
	}

	//parent变成cur的左子树
	cur->_left = parent;
	parent->_parent = cur;//保持三叉连


	if (ppnode) {
		cur->_parent = ppnode;

		if (ppnode->_left == parent) {		//如果是上面的左子树
			ppnode->_left = cur;
		}
		else {
			ppnode->_right = cur;			//如果是上面的右子树
		}
	}
	else {									//如果ppnode是nullptr,则代表parent为root
		_root = cur;
		cur->_parent = nullptr;
	}
	//更新平衡因子
	parent->_bf = 0;
	cur->_bf = 0;
}

③右左双旋

当cur->_bf 的值是-1，并且parent->_bf 的值是 2，如下图15结点，22结点，18结点这般成折线状。
在这里插入图片描述

（1）右左双旋具体图

在这里插入图片描述

（2）右左双旋抽象图

在这里插入图片描述

对于双旋，重点在于如何更新平衡因子。

双旋的重点！！！：
在这里插入图片描述

代码实现:

// 右左双旋

template<class K, class V>
void AVLTree<K, V>::RotateRL(Node* parent) {
	Node* cur = parent->_right;
	Node* cur_left = cur->_left;

	RotateR(cur);			//以parent的right作为新的parent进行右单旋
	RotateL(parent);

	//更新平衡因子(最重要)
	if (cur_left->_bf == 0) {		//情况1
		parent->_bf = 0;
		cur_left->_bf = 0;
		cur->_bf = 0;
	}
	else if(cur_left->_bf == 1) {	//情况3
		parent->_bf = -1;
		cur_left->_bf = 0;
		cur->_bf = 0;
	}
	else if (cur_left->_bf == -1) {	//情况2
		parent->_bf = 0;
		cur_left->_bf = 0;
		cur->_bf = 1;
	}
	else {
		assert(false);
	}
}

④左右双旋

与左右双旋类似，这里不过多介绍了，注意更新平衡因子！！！

（1）左右双旋具体图

在这里插入图片描述

（2）左右双旋抽象图

在这里插入图片描述

template<class K, class V>
void AVLTree<K, V>::RotateLR(Node* parent) {
	Node* cur = parent->_left;
	Node* cur_right = cur->_right;

	RotateR(cur);			//以parent的right作为新的parent进行右单旋
	RotateL(parent);

	//更新平衡因子(最重要)
	if (cur_right->_bf == 0) {
		parent->_bf = 0;
		cur_right->_bf = 0;
		cur->_bf = 0;
	}
	else if (cur_right->_bf == 1) {
		parent->_bf = 0;
		cur_right->_bf = 0;
		cur->_bf = -1;
	}
	else if (cur_right->_bf == -1) {
		parent->_bf = 1;
		cur_right->_bf = 0;
		cur->_bf = 0;
	}
	else {
		assert(false);
	}
}

"插入"操作的代码实现:

template<class K,class V>
bool AVLTree<K,V>::Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) {
		_root = new Node(kv);
		return true;
	}

	Node* cur = _root, * parent = nullptr;
	//寻找插入位置
	while (cur) {
		parent = cur;
		if (_root->_kv.first > kv.first) {
			cur = cur->_left;
		}
		else if (_root->_kv.first < kv.first) {
			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;					//保证三叉链的关系

	//更新平衡因子,最终可能更新到根节点
	while (parent) {							
		if (cur==parent->_left) {			//如果是插入在左边,平衡因子-1
			parent->_bf--;					
		}
		else if(parent->_right == cur) {								//如果是插入在右边,//平衡因子+1
			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 (cur->_bf == -1 && parent->_bf == -2) {
				RotateR(parent);
			}else 	if (cur->_bf == 1 && parent->_bf == 2) {	//右边高,左单旋
				RotateL(parent);
			}else 	if (cur->_bf == 1 && parent->_bf == -2) {	//左右双旋
				RotateLR(parent);
			}else 	if (cur->_bf == -1 && parent->_bf == 2) {	//右左双旋
				RotateRL(parent);
			}
		}
	}
	return true;
}

2.2 中序遍历:

由于中序遍历需要传参 参数为根节点，而根节点是私有成员变量，所以这里用再套一层函数的方法，是一个不错的设计。

template<class K, class V>
void  AVLTree<K, V>::_InOrder(Node* root)
{
	if (root == nullptr)return;
	_InOrder(root->_left);
	cout << root->_kv.first << "->" << root->_kv.second << endl;
	_InOrder(root->_right);
}

template<class K, class V>
void  AVLTree<K, V>::InOrder()
{
	if (_root == nullptr)
	{
		cout << "空树" << endl;
		return;
	}
	_InOrder(_root);
}

2.3 AVL树的"高度"

同求二叉树的高度没有啥区别。

需要注意的是：
1处和2处，需要记录左右子树的根否则后面的都需要重新大量的重复计算。


template<class K, class V>
size_t AVLTree<K, V>::_Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int leftHeight = _Height(root->_left);		//1
	int rightHeight = _Height(root->_right);	//2

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

2.4 验证AVL树

判断每棵树的平衡因子是否=右子树-左子树的高度即可。

template<class K, class V>
bool AVLTree<K, V>::_IsAVLTree(Node* root) {
	if (root == nullptr)
		return true;

	int leftHight = _Height(root->_left);
	int rightHight = _Height(root->_right);

	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
		return false;
	}

	return abs(rightHight - leftHight) < 2
		&& _IsAVLTree(root->_left)
		&& _IsAVLTree(root->_right);
}

结语

AVL树的平衡性使得它的插入、删除和查找操作的时间复杂度都是O(logn)，与红黑树相当。然而，由于AVL树在每次插入或删除时都需要进行平衡调整，所以它的常数比红黑树稍大，因此在实际应用中，红黑树更为常用。
后续会更新红黑树的介绍，很多人认为红黑树是比AVL树还要优秀的结构，不想要了解一下吗？ 还请保持关注哦！
在这里插入图片描述


http://www.niftyadmin.cn/n/5271685.html

相关文章

Spring Integration接收TCP与UDP请求

Spring Integration接收TCP与UDP请求

1. 简介 Spring Integration 是一个开源的项目&#xff0c;它是 Spring 生态系统的一部分&#xff0c;旨在简化企业集成&#xff08;Enterprise Integration&#xff09;的开发。它提供了一种构建消息驱动的、松散耦合的、可扩展的企业应用集成解决方案的方式。Spring Integra…
阅读更多...
记录 | Visual Studio报错：const char*类型的值不能用于初始化char*类型

记录 | Visual Studio报错：const char*类型的值不能用于初始化char*类型

Visual Studio 报错&#xff1a; const char *”类型的值不能用于初始化“char *”类型的实体错误 解决办法&#xff1a; 1&#xff0c;强制类型转换&#xff0c;例如&#xff1a; char * Singer::pv[] {(char*)"other", (char*)"alto", (char*)"c…
阅读更多...
​springboot代码混淆及反混淆代码工具

​springboot代码混淆及反混淆代码工具

​springboot代码混淆及反混淆代码工具 目录 介绍 什么是混淆 为什么用混淆&#xff1f; 基础混淆 高级混淆工具 #0x1 ipaguard Tool - springboot混淆工具 ipaguard界面概览 ipaguard启动界面 ipaguard代码混淆界面 资源文件混淆界面 重签名界面 尽管到目前为止&a…
阅读更多...
MILP加速运算技巧——模型对称性的预处理

MILP加速运算技巧——模型对称性的预处理

文章目录 整数规划的对称性什么是对称性对称性的影响 对称性的预处理方法 整数规划的对称性 什么是对称性 许多整数规划问题存在对称性&#xff0c;这种对称性是指问题解空间的对称&#xff0c;即在对称的解空间当中解的优化目标值上是相同的。这种对称性并不会改变问题的最优…
阅读更多...
更新钉钉文档封装好的代码

更新钉钉文档封装好的代码

import json import requestsclass OperateKnowledgeBaseExcel():robot_code #机器人agent_id app_key #机器人密钥 获取方法见我的其他博客app_secret #机器人密钥def __init__(self,union_id, workbook_id, worksheet_id):self.union_…
阅读更多...
苹果明年春季将发布多款新品！

苹果明年春季将发布多款新品！

大家期待已久的iPad系列终于要迎来更新了&#xff0c;据彭博社记者马克古尔曼最新爆料称&#xff0c;苹果为了提振下滑的iPad销售&#xff0c;计划在2024年初对iPad系列进行重大更新&#xff0c;包括2款不同尺寸的新iPad Air和新iPad Pro&#xff0c;这些机型都将有显著的变化。…
阅读更多...
QUIC在零信任解决方案的落地实践

QUIC在零信任解决方案的落地实践

一 前言 ZTNA为以“网络为中心”的传统企业体系架构向以“身份为中心”的新型企业安全体系架构转变&#xff0c;提供解决方案。随着传统网络边界不断弱化&#xff0c;企业SaaS规模化日益增多&#xff0c;给终端安全访问接入创造了多元化的空间。其中BYOD办公方式尤为突出&#…
阅读更多...
【JAVA】CyclicBarrier源码解析以及示例

【JAVA】CyclicBarrier源码解析以及示例

文章目录 前言CyclicBarrier源码解析以及示例主要成员变量核心方法 应用场景任务分解与合并应用示例 并行计算应用示例 游戏开发应用示例输出结果 数据加载应用示例 并发工具的协同应用示例 CyclicBarrier和CountDownLatch的区别循环性&#xff1a;计数器的变化&#xff1a;用途…
阅读更多...
最新文章

Copyright @ 2022~2023