数据结构：AVL树的旋转（平衡搜索二叉树）

1、AVL树简介

 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

  • 它的子树都是AVL树
  • 左右子树高度插（平衡因子）的绝对值不超过1

AVL树还是一个搜索二叉树，只不过因为普通的搜索二叉树有可能变成单只树，这样就使查找效率非常的低。我们就给普通的搜索二叉树增加了一个平衡因子来使AVL左右子树的高度差的绝对值不超过1

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;              
	pair<K, V> _kv;                          // 存储的键对
	int _bf;                                 // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv);
	bool IsBalance();
	void InOrder();
	void Height();

private:
	void RotateL(Node* parent);              //左旋转
	void RotateR(Node* parent);              //右旋转
	void RotateRL(Node* parent);             //右左旋转
	void RotateLR(Node* parent);             //左右旋转
	bool _IsBalance(Node* root);
	void _InOrder(Node* root);
	int _Height(Node* root);


	Node* _root = nullptr;
};

2、AVL树的插入

  • AVL树的插入前面和搜索二叉树的插入一模一样，只不过我们要注意平衡因子
  • 因为AVL树保持平衡是要平衡因子的绝对值不超过1，而插入会使平衡因子改变，所以我们也要要相应的旋转，使平衡因子的绝对值不超过一，我们又有几种情况
  1. 假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
  2. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋。当subR的平衡因子为-1时，执行右左双旋
  3. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋。当subL的平衡因子为1时，执行左右双旋
  4. 旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新
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* parent = nullptr;
	Node* cur = _root;
	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 > kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;

	// 更新平衡因子
	while (parent)
	{
		if (cur == parent->_right)
		{
			parent->_bf++;
		}
		else
		{
			parent->_bf--;
		}

		if (parent->_bf == 1 || parent->_bf == -1)
		{
			// 继续更新
			parent = parent->_parent;
			cur = cur->_parent;
		}
		else if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 需要旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度
			if (parent->_bf == 2 && cur->_bf == 1)
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{
				RotateRL(parent);
			}
			else
			{
				assert(false);
			}

			break;
		}
		else
		{
			assert(false);
		}
	}

	return true;
}

2.1、左单旋

  1. subRL变成parent的右子树 
  2. parent变成subR的左子树
  3. subR变成新根
  4. 更新平衡因子
template<class K, class V>
void AVLTree<K, V>::RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	subR->_left = parent;

	Node* parentParent = parent->_parent;

	parent->_parent = subR;
	if (subRL)
		subRL->_parent = parent;

	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
		}
		else
		{
			parentParent->_right = subR;
		}

		subR->_parent = parentParent;
	}

	parent->_bf = subR->_bf = 0;
}

2.2、右单旋

60为parent，30为subL，b为subLR 

  1. subLR变成parent的左子树 
  2. parent变成subL的右子树
  3. subL变成新根
  4. 更新平衡因子
template<class K, class V>
void AVLTree<K, V>::RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

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

	Node* parentParent = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;

	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subL;
		}
		else
		{
			parentParent->_right = subL;
		}

		subL->_parent = parentParent;
	}

	subL->_bf = parent->_bf = 0;
}

2.3、左右双旋 

先对30进行左单旋，先对90右单旋

template<class K, class V>
void AVLTree<K, V>::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 = subL->_bf = subLR->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = -1;
	}
	else
	{
		assert(false);
	}
}

2.3、右左双旋 

先对90进行右单旋，先对30左单旋 

template<class K, class V>
void AVLTree<K, V>::RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 0)
	{
		// subRL自己就是新增
		parent->_bf = subR->_bf = subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		// subRL的左子树新增
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1)
	{
		// subRL的右子树新增
		parent->_bf = -1;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

 3、AVL树的性能

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合

4、实现

#include<assert.h>

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;              
	pair<K, V> _kv;                          // 存储的键对
	int _bf;                                 // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv);
	bool IsBalance();
	void InOrder();
	void Height();

private:
	void RotateL(Node* parent);              //左旋转
	void RotateR(Node* parent);              //右旋转
	void RotateRL(Node* parent);             //右左旋转
	void RotateLR(Node* parent);             //左右旋转
	bool _IsBalance(Node* root);
	void _InOrder(Node* root);
	int _Height(Node* root);


	Node* _root = nullptr;
};

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* parent = nullptr;
	Node* cur = _root;
	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 > kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;

	// 更新平衡因子
	while (parent)
	{
		if (cur == parent->_right)
		{
			parent->_bf++;
		}
		else
		{
			parent->_bf--;
		}

		if (parent->_bf == 1 || parent->_bf == -1)
		{
			// 继续更新
			parent = parent->_parent;
			cur = cur->_parent;
		}
		else if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 需要旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度
			if (parent->_bf == 2 && cur->_bf == 1)
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{
				RotateRL(parent);
			}
			else
			{
				assert(false);
			}

			break;
		}
		else
		{
			assert(false);
		}
	}

	return true;
}

template<class K, class V>
void AVLTree<K, V>::RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	subR->_left = parent;

	Node* parentParent = parent->_parent;

	parent->_parent = subR;
	if (subRL)
		subRL->_parent = parent;

	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
		}
		else
		{
			parentParent->_right = subR;
		}

		subR->_parent = parentParent;
	}

	parent->_bf = subR->_bf = 0;
}

template<class K, class V>
void AVLTree<K, V>::RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

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

	Node* parentParent = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;

	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subL;
		}
		else
		{
			parentParent->_right = subL;
		}

		subL->_parent = parentParent;
	}

	subL->_bf = parent->_bf = 0;
}

template<class K, class V>
void AVLTree<K, V>::RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 0)
	{
		// subRL自己就是新增
		parent->_bf = subR->_bf = subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		// subRL的左子树新增
		parent->_bf = 0;
		subRL->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1)
	{
		// subRL的右子树新增
		parent->_bf = -1;
		subRL->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

template<class K, class V>
void AVLTree<K, V>::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 = subL->_bf = subLR->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = -1;
	}
	else
	{
		assert(false);
	}
}

template<class K, class V>
void AVLTree<K, V>::InOrder()
{
	_InOrder(_root);
	cout << endl;
}

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

	_InOrder(root->_left);
	cout << root->_kv.first << " ";
	_InOrder(root->_right);
}

template<class K, class V>
bool AVLTree<K, V>::IsBalance()
{
	return _IsBalance(_root);
}

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

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

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

template<class K, class V>
void AVLTree<K, V>::Height()
{
	cout << _Height(_root) << endl;
}

template<class K, class V>
bool AVLTree<K,V>::_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->_kv.first << "平衡因子异常" << endl;
		return false;
	}

	return abs(rightHeight - leftHeight) < 2
		&& _IsBalance(root->_left)
		&& _IsBalance(root->_right);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/120158.html

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

相关文章

双11购物节想入手一款音画好的智能电视，大家推荐一下吧？

双11购物节想入手一款音画好的智能电视，大家推荐一下吧？

智能家电更新太快,不想三五年后就淘汰,那就入手东芝电视Z700吧,Z700这次把观影体验和音箱效果做到哇塞,既然要享受生活那就要享受高品质的体验。东芝电视拥有70余年的原色调校技术,每款产品都有专属的日本调校工程师匠心打造,可以真实还原画面色彩,而且还有火箭炮音响系统,也是…
阅读更多...
C++ 图解二叉树非递归后序 + 实战力扣题

C++ 图解二叉树非递归后序 + 实战力扣题

145.二叉树的后序遍历 145. 二叉树的后序遍历 - 力扣&#xff08;LeetCode&#xff09; class Solution { public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> vec;if(root NULL) return vec;TreeNode* guard root…
阅读更多...
大型企业是否有必要进行数字化转型？_数据治理平台_光点科技

大型企业是否有必要进行数字化转型？_数据治理平台_光点科技

数字化转型是大型企业在现代商业环境中保持竞争力的关键。一开始我们要明确数字化转型指的是利用数字技术来改变企业的业务模式和企业文化&#xff0c;以提高效率和效益。对于大型企业而言&#xff0c;进行数字化转型有着多重必要性。 1.数字化转型可以帮助企业优化内部流程&am…
阅读更多...
记一次经典SQL双写绕过题目[极客大挑战 2019]BabySQL 1

记一次经典SQL双写绕过题目[极客大挑战 2019]BabySQL 1

题目环境&#xff1a; 作者已经描述进行了严格的过滤 做好心理准备进行迎接 判断注入类型 admin 1’ 字符型注入万能密码注入 admin 1’ or ‘1’1 报错 已经是字符型注入了&#xff0c;所以的话只有or这里存在了过滤 联想到buuctf里面还没有碰到双写绕过的题目 所以这里斗胆试…
阅读更多...
ESXi配置两个不同网段虚拟机互通

ESXi配置两个不同网段虚拟机互通

ESXi配置两个不同网段虚拟机互通 拓扑图&#xff1a; 步骤 在ESXi上新建一个虚拟交换机新建两个端口组&#xff0c;VLAN ID分别为30和31&#xff0c;添加到新建的虚拟交换机上创建两个虚拟机&#xff0c;网络适配器分别使用新建的端口组30和31对新建的虚拟机配置IP在物理交换…
阅读更多...
【计算机组成】实模式/保护模式下地址分段（基段地址+偏移地址）的原因

【计算机组成】实模式/保护模式下地址分段（基段地址+偏移地址）的原因

一.硬编码/静态重定向 我们先来观察下没有地址分段时代CPU是怎么和内存们打交道&#xff0c;在8086CPU以前的老大哥们&#xff0c;访问内存时通常就是实打实的“指哪打哪”&#xff0c;程序指定要放在哪个地址&#xff0c;那就老老实实地放在哪个地址&#xff0c;比如程序A要放…
阅读更多...
微信小程序案例3-1 比较数字

微信小程序案例3-1 比较数字

文章目录 一、运行效果二、知识储备&#xff08;一&#xff09;Page()函数&#xff08;二&#xff09;数据绑定&#xff08;三&#xff09;事件绑定&#xff08;四&#xff09;事件对象&#xff08;五&#xff09;this关键字&#xff08;六&#xff09;setData()方法&#xff0…
阅读更多...
Azure 机器学习 - 设置 AutoML 训练时序预测模型

Azure 机器学习 - 设置 AutoML 训练时序预测模型

目录 一、环境准备二、训练和验证数据三、配置试验支持的模型配置设置特征化步骤自定义特征化 四、可选配置频率和目标数据聚合启用深度学习目标滚动窗口聚合短时序处理非稳定时序检测和处理 五、运行试验六、用最佳模型进行预测用滚动预测评估模型精度预测未来 七、大规模预测…
阅读更多...
《深入立即计算机系统》书籍学习笔记 - 第二课 - 位，字节和整型

《深入立即计算机系统》书籍学习笔记 - 第二课 - 位，字节和整型

Lecture 02 Bits,Bytes, and Integer 位&#xff0c;字节和整型 文章目录 Lecture 02 Bits,Bytes, and Integer 位&#xff0c;字节和整型Byte 字节位操作布尔代数集合的表现形式和操作C语言的逻辑操作 位移操作整型数值范围无符号与有符号数值无符号与有符号在C中 拓展和截断拓…
阅读更多...
安防监控EasyCVR视频汇聚平台使用海康SDK播放时，画面播放缓慢该如何解决？

安防监控EasyCVR视频汇聚平台使用海康SDK播放时，画面播放缓慢该如何解决？

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。安防视频平台EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、云存储、…
阅读更多...
物业报修管理软件哪个好？如何提升物业管理和维修服务质量？

物业报修管理软件哪个好？如何提升物业管理和维修服务质量？

在当前的数字化时代&#xff0c;物业管理软件在物业行业中的作用日益凸显。它不仅能够有效提升管理效率&#xff0c;还能够优化服务质量&#xff0c;拓展收入来源&#xff0c;推动智慧物业的全面实现。本文将深入探讨“的修”报修管理软件如何通过其独特的功能和优势&#xff0…
阅读更多...
【机器学习】Kmeans聚类算法

【机器学习】Kmeans聚类算法

一、聚类简介 Clustering (聚类)是常见的unsupervised learning (无监督学习)方法&#xff0c;简单地说就是把相似的数据样本分到一组&#xff08;簇&#xff09;&#xff0c;聚类的过程&#xff0c;我们并不清楚某一类是什么&#xff08;通常无标签信息&#xff09;&#xff0…
阅读更多...
《009.Springboot+vue之进销存管理系统》

《009.Springboot+vue之进销存管理系统》

《009.Springbootvue之进销存管理系统》 项目简介 [1]本系统涉及到的技术主要如下&#xff1a; 推荐环境配置&#xff1a;DEA jdk1.8 Maven MySQL 前后端分离; 后台&#xff1a;SpringBootMybatisredis; 前台&#xff1a;vueElementUI; [2]功能模块展示&#xff1a; 1.用户管…
阅读更多...
AC修炼计划（AtCoder Regular Contest 163）

AC修炼计划（AtCoder Regular Contest 163）

传送门&#xff1a;AtCoder Regular Contest 163 - AtCoder 第一题我们只需要将字符串分成两段&#xff0c;如果存在前面一段比后面一段大就成立。 #include<bits/stdc.h> #define int long long using namespace std; typedef long long ll; typedef pair<int,int&g…
阅读更多...
程序设计：控制台输出二叉树 二叉树的形象显示

程序设计：控制台输出二叉树 二叉树的形象显示

本文指导你编写一个输出到字符控制台的形象的二叉树展示。 目录 一般的Tree显示方式 理想的显示方式 实现方法 计算显示位置 输出数据 计算显示位置的代码 输出数据的代码 一般的Tree显示方式 编写二叉树算法时调试是很头疼的&#xff0c;如何显示成一目了然的树结构呢…
阅读更多...
Flink SQL DataGen Connector 示例

Flink SQL DataGen Connector 示例

Flink SQL DataGen Connector 示例 1、概述 使用 Flink SQL DataGen Connector&#xff0c;可以快速地生成符合规则的测试数据&#xff0c;可以在不依赖真实数据的情况下进行开发和测试。 2、使用示例 创建一个名为 “users” 的表&#xff0c;包含 6 个字段&#xff1a;id…
阅读更多...
PHP分类信息网站源码系统 电脑+手机+微信端三合一 带完整前后端部署教程

PHP分类信息网站源码系统 电脑+手机+微信端三合一 带完整前后端部署教程

大家好啊&#xff01;今天源码小编来给大家分享一款PHP分类信息网站类源码系统。这款源码系统是一套专业的信息发布类网站综合管理系统&#xff0c;适合各类地方信息和行业分类站点建站。随着这几年我们国家网民爆炸式的增 长&#xff0c;网络信息也随之越来越庞大&#xff0c;…
阅读更多...
为什么亚马逊的轻量应用服务器这么受欢迎 | 个人体验 | 优势所在

为什么亚马逊的轻量应用服务器这么受欢迎 | 个人体验 | 优势所在

文章目录 &#x1f33a;前言⭐什么是轻量应用服务器&#x1f6f8;特点 &#x1f384;亚马逊轻量应用服务器体验如何&#x1f339;亚马逊轻量应用服务器的优势 &#x1f33a;前言 作为一为开发者&#xff0c;我们要开发部署一个自己的网站&#xff0c;要选择一个性能好的服务器…
阅读更多...
算法训练 第六周

算法训练 第六周

一、用栈实现队列 本题要求我们使用栈这个数据结构来模拟实现队列的各种操作&#xff0c;我们的具体思路是使用两个栈&#xff0c;将一个栈当作输入栈&#xff0c;用于压入 push传入的数据&#xff1b;另一个栈当作输出栈&#xff0c;用于 pop和 peek 操作。每次 pop 或 peek 时…
阅读更多...
大数据学习之Spark性能优化

大数据学习之Spark性能优化

文章目录 Spark三种任务提交模式宽依赖和窄依赖StageSpark Job的三种提交模式 Shuffle机制分析未优化的Hash Based Shuffle优化后的Hash Based ShuffleSort-Based Shuffle Spark之checkpointcheckpoint概述checkpoint与持久化的区别checkPoint的使用checkpoint源码分析 Spark程…
阅读更多...
最新文章

Copyright @ 2022~2023