会旋转的树,你见过吗?

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯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.mfbz.cn/a/254406.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

工业数据的特殊性和安全防护体系探索思考

工业数据的特殊性和安全防护体系探索思考

随着工业互联网的发展&#xff0c;工业企业在生产运营管理过程中会产生各式各样数据&#xff0c;主要有研发设计数据、用户数据、生产运营数据、物流供应链数据等等&#xff0c;这样就形成了工业大数据&#xff0c;这些数据需要依赖企业的网络环境和应用系统进行内外部流通才能…
阅读更多...
字体包引入以及使用

字体包引入以及使用

将UI给的字体包下载到assets文件夹下 app.vue全局定义 <style> * {margin: 0;padding: 0; }font-face {font-family: PangMenZhengDao-3;src: url(/assets/fonts/庞门正道标题体3.0.TTF) format(truetype);font-weight: bold;font-style: normal; } </style>页面使…
阅读更多...
亚马逊云科技re:Invent推出生成式AI技术堆栈及关键服务和工具

亚马逊云科技re:Invent推出生成式AI技术堆栈及关键服务和工具

亚马逊云科技于29日推出“生成式AI技术堆栈”后&#xff0c;又在30日的re:Invent 2023大会上宣布了一系列支持这一全新堆栈的关键服务和工具。 亚马逊云科技数据和人工智能副总裁Swami Sivasubramanian在主题演讲中&#xff0c;将生成式人工智能与“超新星爆炸”进行了比较&am…
阅读更多...
ffmpeg可以做什么

ffmpeg可以做什么

用途 FFmpeg是一个功能强大的多媒体处理工具&#xff0c;可以处理音频和视频文件。它是一个开源项目&#xff0c;可在各种操作系统上运行&#xff0c;包括Linux、Windows和Mac OS X等。以下是FFmpeg可以做的一些主要任务&#xff1a; 转换媒体格式&#xff1a;可将一个媒体格式…
阅读更多...
云原生基础入门概念

云原生基础入门概念

文章目录 发现宝藏云原生的概念云原生的关键技术为何选择云原生&#xff1f;云原生的实际应用好书推荐 发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【宝藏入口】。 云原生的概念 当谈及现…
阅读更多...
http跟https的区别

http跟https的区别

只要上过网的朋友一定接触过“HTTP”&#xff0c;每次开网页的时候&#xff0c;不管是什么网址&#xff0c;其前面都会出现HTTP字样&#xff0c;比如 “http&#xff1a;55049sjad.com”、“http&#xff1a;544.65.5.6.com”等等&#xff0c;而有些时候打开如银行等对安全性要…
阅读更多...
【linux】SSH终端Putty配置：文件上传/下载、显示中文字体、自动登录

【linux】SSH终端Putty配置：文件上传/下载、显示中文字体、自动登录

文章目录 写在前面putty上传/下载文件1. 下载2. 解压和配置3. 使用sz/rz3.1 下载文件:sz3.2 上传文件:rz 显示中文字体1. 下载合适的字体2. 解压和安装3. putty配置 putty自动登录1. putty配置2. putty快捷方式配置3. 使用putty 写在后面 写在前面 一篇博客介绍了12种SSH终端工…
阅读更多...
D3132|贪心算法

D3132|贪心算法

435.无重叠区间 初始思路&#xff1a; 我的思路就是如果有两个区间重叠&#xff0c;保留end比较小的那个区间&#xff0c;删除end比较大的区间。 class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>…
阅读更多...
恐怖题材黑马大作，艾尔莎B760M-E D5和你玩转《心灵杀手2》

恐怖题材黑马大作，艾尔莎B760M-E D5和你玩转《心灵杀手2》

说起恐怖题材的游戏&#xff0c;相信不少朋友都会第一时间想到《生化危机》、《寂静岭》、《死亡空间》等经典系列与作品。而在最近这几年&#xff0c;恐怖题材游戏也有不少黑马出现&#xff0c;比如最近推出的《心灵杀手2》就是2010年《心灵杀手》的续作&#xff0c;它是由开发…
阅读更多...
iPhone16:首款AI iPhone?

iPhone16:首款AI iPhone?

随着科技水平的不断发展&#xff0c;智能手机逐渐成为人们最依赖的电子产品之一。为能够满足用户需求&#xff0c;手机的硬件、外观设计与性能飞速提升&#xff0c;这也导致智能手机市场快速进入到瓶颈期。 为了能够带来更优秀的表现&#xff0c;苹果可能会为iPhone 16系列带来…
阅读更多...
中国首家！腾讯云入选Gartner®视频平台服务市场指南代表厂商

中国首家！腾讯云入选Gartner®视频平台服务市场指南代表厂商

近日&#xff0c; Gartner正式发布《Market Guide for Video Platform Services》&#xff08;《视频平台服务市场指南》&#xff0c;下称“《指南》”&#xff09;&#xff0c;凭借领先的音视频技术和产品组合优势&#xff0c;腾讯云成为中国首家且唯一入选的代表厂商。 腾讯…
阅读更多...
GZ015 机器人系统集成应用技术样题8-学生赛

GZ015 机器人系统集成应用技术样题8-学生赛

2023年全国职业院校技能大赛 高职组“机器人系统集成应用技术”赛项 竞赛任务书&#xff08;学生赛&#xff09; 样题8 选手须知&#xff1a; 本任务书共 25页&#xff0c;如出现任务书缺页、字迹不清等问题&#xff0c;请及时向裁判示意&#xff0c;并进行任务书的更换。参赛队…
阅读更多...
Vue学习笔记-Vue3中的customRef

Vue学习笔记-Vue3中的customRef

作用 创建一个自定义的ref&#xff0c;并对其依赖项的更新和触发进行显式控制 案例 描述&#xff1a;向输入框中输入内容&#xff0c;在下方延迟1秒展示输入内容 代码&#xff1a; <template><input type"text" v-model"keyword"><h3&…
阅读更多...
力扣刷题记录（15）LeetCode：509、70、746

力扣刷题记录（15）LeetCode：509、70、746

目录 509.斐波那契数 70.爬楼梯 746.使用最小花费爬楼梯 总结 ​​​​​​ 用一个数组来存储前两个数的值&#xff0c;然后根据前两个数的值来确定当前的值。 class Solution { public:int fib(int n) {if(n<2) return n;vector<int> v;v.push_back(0);v.push…
阅读更多...
3 使用postman批量创建测试数据

3 使用postman批量创建测试数据

上一篇：2 使用postman进行接口测试-CSDN博客 在软件测试实际工作中，因测试需要，我们要批量创建测试数据。如果某些接口不允许输入重复数据，我们在做批量请求时就要做参数处理了。 比如在上一篇介绍的用户注册接口，一般注册的时候用户名是不允许重复的，如果要批量创…
阅读更多...
8.完成任务实现的SDK封装及插件式加载

8.完成任务实现的SDK封装及插件式加载

1.设计 任务的实现目前完成了Modbus RTU、Modbus TCP、Virtule。任务实现应该是任意的&#xff0c;比如打印一段话&#xff0c;执行一句SQL等&#xff0c;所以系统内部的必然要做到可扩展。 要做到可扩展&#xff0c;首先第一步就是定义标准&#xff0c;所以我们首先需要封装…
阅读更多...
FA1210AN (MHz范围晶体单元超小型低轮廓贴片)

FA1210AN (MHz范围晶体单元超小型低轮廓贴片)

FA1210AN体积小&#xff0c;高度低&#xff0c;设计人员可以在不影响性能的情况下节省板空间。这对于那些限制功能和尺寸的设备和模块来说是必不可少的。 宽MHz范围的频率服务于流行的&#xff0c;无线通信协议&#xff0c;理想的消费者和工业物联网应用。应用程序&#xff1a…
阅读更多...
第15章 《乐趣》Page375~379定时器，定时回调，定时回调线程id, 停止后续定时

第15章 《乐趣》Page375~379定时器，定时回调，定时回调线程id, 停止后续定时

运行效果&#xff1a;在骏马窗口中&#xff0c;按下ctrl t 键&#xff0c;就可以看到定时回调&#xff0c;同时可以看出timer_callback和main()真的不在同一线程中运行 代码如下&#xff1a;仅给出main.cpp, 其他的头文件和源文件和Page355~375的代码一样&#xff0c;可参看上…
阅读更多...
【C语言】数组（一维）详解，手把手教你，保姆级！！！

【C语言】数组（一维）详解，手把手教你，保姆级！！！

目录 数组的概念 数组的创建 数组的初始化 数组的类型 数组使用下标 数组的打印 数组的输入 数组的储存 总结 数组的概念 数组是⼀组相同类型元素的集合&#xff1b; 从这个概念中我们有3点拓展&#xff1a; 1&#xff0c;数组中存放的是1个或者多个数据&#xff0c;但…
阅读更多...
4.raft协议及简化版raft协议

4.raft协议及简化版raft协议

1.Raft协议介绍 这篇文章&#xff1a;百度安全验证 讲的比较详细了&#xff0c;我再以我的方式汇总一下&#xff1a; Raft协议是一种分布式一致性协议&#xff0c;比Pasox简单&#xff0c;旨在解决数据的一致性和高可用性Raft在选举中的方式&#xff1a; 所有节点相互建立连…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站