平衡搜索二叉树（AVL树）

前言

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

一、AVL树的概念

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
                
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O(log n)，搜索时间复杂度O(log n)。

二、AVL树的定义

AVL树节点的定义：

我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。

template<class K, class V>
class AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf; // 平衡因子

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

三、AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为三步：
  1. 按照二叉搜索树的插入方法，找到待插入位置。
  2. 找到待插入位置后，将待插入结点插入到树中。
  3. 更新平衡因子，如果出现不平衡，则需要进行旋转。
因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照 二叉搜索树的插入规则：
  1. 待插入结点的key值比当前结点小就插入到该结点的左子树。
  2. 待插入结点的key值比当前结点大就插入到该结点的右子树。
  3. 待插入结点的key值与当前结点的key值相等就插入失败。
与二叉搜索树插入结点不同的是，AVL树插入结点后需要 更新树中结点的平衡因子 ，因为插入新结点后可能会影响树中某些结点的平衡因子。
pCur 插入后， pParent 的平衡因子一定需要调整，在插入之前， pParent 的平衡因子分为三种情况：-1 ， 0, 1, 分以下两种情况：

  1. 如果 pCur 插入到 pParent 的左侧，只需给 pParent 的平衡因子 -1 即可
  2. 如果 pCur 插入到 pParent 的右侧，只需给 pParent 的平衡因子 +1 即可
此时： pParent 的平衡因子可能有三种情况： 0 ，正负 1 ， 正负 2
  1. 如果 pParent 的平衡因子为 0 ，说明插入之前 pParent 的平衡因子为正负 1 ，插入后被调整成0 ，此时满足
    AVL 树的性质，插入成功
  2. 如果 pParent 的平衡因子为正负 1 ，说明插入前 pParent 的平衡因子一定为 0 ，插入后被更 新成正负1 ，此 时以 pParent 为根的树的高度增加，需要继续向上更新
  3. 如果 pParent 的平衡因子为正负 2 ，则 pParent 的平衡因子违反平衡树的性质，需要对其进 行旋转处理
而在最坏情况下，我们更新平衡因子时会一路更新到根结点。例如下面这种情况：
说明一下： 由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新。当然，我们也可以不用三叉链结构，可以在插入结点时将路径上的结点存储到一个栈当中，当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子，但是相对较麻烦。
若是在更新平衡因子的过程当中，出现了平衡因子为-2/2的结点，这时我们需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行以下分析：
我们将插入结点称为cur，将其父结点称为parent，那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，那么我们必定要执行以下逻辑：
cur = parent;
parent = parent->_parent;
这里我想说明的是： 当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。

理由如下：
若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。
而cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：

其父结点是一个左右子树均为空的叶子结点，其平

衡因子是0，新增结点插入后其平衡因子更新为-1/1。
其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。
综上所述，当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0
 

根据此结论，我们可以将旋转处理分为以下四类：  

  1. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
  2. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
  3. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。
  4. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。
并且，在进行旋转处理后就无需继续往上更新平衡因子了，因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了。
插入函数代码： 
//插入函数
bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) //若AVL树为空树，则插入结点直接作为根结点
	{
		_root = new Node(kv);
		return true;
	}
	//1、按照二叉搜索树的插入方法，找到待插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
		{
			//往该结点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
		{
			//往该结点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else //待插入结点的key值等于当前结点的key值
		{
			//插入失败（不允许key值冗余）
			return false;
		}
	}

	//2、将待插入结点插入到树中
	cur = new Node(kv); //根据所给值构造一个新结点
	if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
	{
		//插入到parent的左边
		parent->_left = cur;
		cur->_parent = parent;
	}
	else //新结点的key值大于parent的key值
	{
		//插入到parent的右边
		parent->_right = cur;
		cur->_parent = parent;
	}

	//3、更新平衡因子，如果出现不平衡，则需要进行旋转
	while (cur != _root) //最坏一路更新到根结点
	{
		if (cur == parent->_left) //parent的左子树增高
		{
			parent->_bf--; //parent的平衡因子--
		}
		else if (cur == parent->_right) //parent的右子树增高
		{
			parent->_bf++; //parent的平衡因子++
		}
		//判断是否更新结束或需要进行旋转
		if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
		{
			break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
		}
		else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子
		{
			//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了）
		{
			if (parent->_bf == -2)
			{
				if (cur->_bf == -1)
				{
					RotateR(parent); //右单旋
				}
				else //cur->_bf == 1
				{
					RotateLR(parent); //左右双旋
				}
			}
			else //parent->_bf == 2
			{
				if (cur->_bf == -1)
				{
					RotateRL(parent); //右左双旋
				}
				else //cur->_bf == 1
				{
					RotateL(parent); //左单旋
				}
			}
			break; //旋转后就一定平衡了，无需继续往上更新平衡因子(旋转后树高度变为插入之前了)
		}
		else
		{
			assert(false); //在插入前树的平衡因子就有问题
		}
	}

	return true; //插入成功
}

四、AVL树的旋转

4.1、右单旋

新节点插入较高左子树的左侧---左左：

右单旋的步骤：
  1. 让subL的右子树作为parent的左子树。
  2. 让parent作为subL的右子树。
  3. 让subL作为整个子树的根。
  4. 更新平衡因子。

右单旋后满足二叉搜索树的性质：

  1. subL的右子树当中结点的值本身就比parent的值小，因此可以作为parent的左子树。
  2. parent及其右子树当中结点的值本身就比subL的值大，因此可以作为subL的右子树。
可以看到，经过右单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以右单旋后无需继续往上更新平衡因子。
右单旋代码： 
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 (ppnode == nullptr) //如果父节点是根节点
	{
		_root = subL;      //改变根节点
		_root->_parent = nullptr;
	}
	else                   //如果父节点不是根节点
	{
		if (ppnode->_left == parent) //如果父节点是左孩子
		{
			ppnode->_left = subL;    
		}
		else                         //如果父节点是右孩子
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	parent->_bf = subL->_bf = 0;    //最后更新平衡因子
}

4.2、左单旋

. 新节点插入较高右子树的右侧---右右
左单旋的步骤如下：
  1. 让subR的左子树作为parent的右子树。
  2. 让parent作为subR的左子树。
  3. 让subR作为整个子树的根。
  4. 更新平衡因子。

左单旋后满足二叉搜索树的性质：

  1. subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。
  2. parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。
可以看到，经过左单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左单旋后无需继续往上更新平衡因子。
左单旋代码： 
//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* parentParent = parent->_parent;

	//1、建立subR和parent之间的关系
	parent->_parent = subR;
	subR->_left = parent;

	//2、建立parent和subRL之间的关系
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	//3、建立parentParent和subR之间的关系
	if (parentParent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr; //subR的_parent指向需改变
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subR;
		}
		else //parent == parentParent->_right
		{
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}

	//4、更新平衡因子
	subR->_bf = parent->_bf = 0;
}

4.3、左右双旋

新节点插入较高左子树的右侧---左右：
将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再
考虑平衡因子的更新。
左右双旋的步骤如下：
  1. 以subL为旋转点进行左单旋。
  2. 以parent为旋转点进行右单旋。
  3. 更新平衡因子。

左右双旋后满足二叉搜索树的性质：

左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根

1、subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
2、subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
3、经过步骤1/2后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树

左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

1、当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。

2、当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。
3、当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。
可以看到，经过左右双旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左右双旋后无需继续往上更新平衡因子。
左右双旋代码： 
//左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1

	//1、以subL为旋转点进行左单旋
	RotateL(subL);

	//2、以parent为旋转点进行右单旋
	RotateR(parent);

	//3、更新平衡因子
	if (bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false); //在旋转前树的平衡因子就有问题
	}
}

4.4、右左双旋

新节点插入较高右子树的左侧---右左：
右左双旋的步骤如下：
  1. 以subR为旋转点进行右单旋。
  2. 以parent为旋转点进行左单旋。
  3. 更新平衡因子。
右左双旋后满足二叉搜索树的性质：

右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根

1、subRL的左子树当中的结点本身就比parent的值大，因此可以作为parent的右子树。

2、subRL的右子树当中的结点本身就比subR的值小，因此可以作为subR的左子树

3、经过步骤1/2后，parent及其子树当中结点的值都就比subRL的值小，而subR及其子树当中结点的值都就比subRL的值大，因此它们可以分别作为subRL的左右子树

右左双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：和左右双旋情况一样，这里就不过多分析。

右左双旋代码：

//右左双旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	//1、以subR为轴进行右单旋
	RotateR(subR);

	//2、以parent为轴进行左单旋
	RotateL(parent);

	//3、更新平衡因子
	if (bf == 1)
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false); //在旋转前树的平衡因子就有问题
	}
}

五、AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

5.1、 验证其为二叉搜索树

        如果中序遍历可得到一个有序的序列，就说明为二叉搜索树 
//中序遍历
void Inorder()
{
    _Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{
    if (root == nullptr)
        return;
    _Inorder(root->_left);
    cout << root->_kv.first << " ";
    _Inorder(root->_right);
}

5.2、 验证其为平衡树

        
        每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
        节点的平衡因子是否计算正确 
//判断是否为AVL树
bool IsAVLTree()
{
	int hight = 0; //输出型参数
	return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int& hight)
{
	if (root == nullptr) //空树是平衡二叉树
	{
		hight = 0; //空树的高度为0
		return true;
	}
	//先判断左子树
	int leftHight = 0;
	if (_IsBalanced(root->_left, leftHight) == false)
		return false;
	//再判断右子树
	int rightHight = 0;
	if (_IsBalanced(root->_right, rightHight) == false)
		return false;
	//检查该结点的平衡因子
	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子设置异常：" << root->_kv.first << endl;
	}
	//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
	hight = max(leftHight, rightHight) + 1;
	return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
}

六、AVL树的性能

  1. 平衡性：AVL树保持了一种平衡性，对于任意节点，其左子树和右子树的高度差不超过1。这种平衡性保证了在最坏情况下，AVL树的插入、删除和查找操作的时间复杂度都是O(log n)。

  2. 插入和删除效率：由于AVL树的平衡性，插入和删除操作可能会导致树进行旋转操作，使得树重新达到平衡状态。虽然旋转操作会增加一定的开销，但是由于树的平衡性，插入和删除操作的时间复杂度仍然是O(log n)。

  3. 查找效率：由于AVL树是一种二叉搜索树，查找操作的时间复杂度也是O(log n)。这使得AVL树非常适合需要高效的查找操作的场景。

  4. 尽管AVL树具有良好的平衡性和较高的查找效率，但是由于需要维护平衡性，插入和删除操作的性能可能会受到一定的影响。在一些特定的插入、删除操作频繁的场景下，可能会考虑使用其他平衡树结构（如红黑树）来获得更好的性能表现。

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

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

相关文章

体元法--体积计算

体元法--体积计算

文章目录 环境&#xff1a;1.1 体元法介绍&#xff1a;2.1 python代码3.1 可视化 环境&#xff1a; Open3D 1.1 体元法介绍&#xff1a; 用一个个体素去占据点云&#xff0c;然后对所有体素求和 2.1 python代码 conda activete deeplabv3plus(环境名称–安装好open3D的) py…
阅读更多...
【Python机器学习】决策树集成——随机森林

【Python机器学习】决策树集成——随机森林

理论知识&#xff1a; 集成是合并多个机器学习模型来构建更强大模型法方法。 随机森林本质上是许多决策树的集合&#xff0c;其中每棵树都和其他数略有不同&#xff0c;随机森林背后的思想是&#xff1a;每棵树的预测可能都比较好&#xff0c;但是可能对部分数据过拟合&#…
阅读更多...
若依项目的table列表中对每一个字段增加排序按钮（单体版和前后端分离版）

若依项目的table列表中对每一个字段增加排序按钮（单体版和前后端分离版）

一、目标：每一个字段都添加上下箭头用来排序 只需要更改前端代码，不需要更改后端代码，后面会讲解原理 二、单体版实现方式： 1.在options中添加sortable:true 2.在需要排序的字段中添加sortable:true 三、前后端分离版 1.el-table上添加@sort-change=“handleSortChange”…
阅读更多...
MySQL的导入导出及备份

MySQL的导入导出及备份

一.准备导入之前 二.navicat导入导出 ​编辑 三.MySQLdump命令导入导出 四.load data file命令的导入导出 五.远程备份 六. 思维导图 一.准备导入之前 需要注意&#xff1a; 在导出和导入之前&#xff0c;确保你有足够的权限。在进行导入操作之前&#xff0c;确保目标数据…
阅读更多...
Tensorflow2.0笔记 - 创建tensor

Tensorflow2.0笔记 - 创建tensor

tensor创建可以基于numpy&#xff0c;list或者tensorflow本身的API。 笔记直接上代码&#xff1a; import tensorflow as tf import numpy as np import matplotlib.pyplot as plttf.__version__#通过numpy创建tensor tensor0 tf.convert_to_tensor(np.ones([2,3])) print(te…
阅读更多...
GitHub 一周热点汇总 第4期 (2024/01/01-01/06)

GitHub 一周热点汇总 第4期 (2024/01/01-01/06)

GitHub一周热点汇总第四期 (2023/12/24-12/30)&#xff0c;梳理每周热门的GitHub项目&#xff0c;了解热点技术趋势&#xff0c;掌握前沿科技方向&#xff0c;发掘更多商机。2024年到了&#xff0c;希望所有的朋友们都能万事顺遂。 说明一下&#xff0c;有时候本周的热点项目会…
阅读更多...
null和undefined的区别

null和undefined的区别

null 和 undefined 是 JavaScript 中的两个基础类型特殊值。它们都表示“空”&#xff0c;但是有一些区别。 一、null 在 JavaScript 内部&#xff0c;null 被视为一个表示空值或缺少值的对象指针。在计算机内存中&#xff0c;它通常被表示为一个指向内存空间的空指针。这意味…
阅读更多...
源码开发实践：搭建企业培训APP的技术难题及解决方案

源码开发实践：搭建企业培训APP的技术难题及解决方案

在企业培训源码开发实践中&#xff0c;各位开发者可能遇到各种各样的问题&#xff0c;本文将深入探讨这些挑战&#xff0c;并提供解决方案&#xff0c;助力你顺利搭建企业培训APP。 1.多平台兼容性 企业中员工使用的设备多种多样&#xff0c;包括iOS、Android等不同操作系统。…
阅读更多...
电力监控系统在数据中心应用

电力监控系统在数据中心应用

摘 要&#xff1a;在电力系统的运行过程中&#xff0c;变电站作为整个电力系统的核心&#xff0c;在保证电力系统可靠的运行方面起着至关重要的作用&#xff0c;基于此需对变电站监控系统的特点进行分析&#xff0c;结合变电站监控系统的功能需求&#xff0c;对变电站电力监控系…
阅读更多...
BitMap解析（一）

BitMap解析（一）

文章目录 前言数据结构添加与删除操作 JDK中BitSet源码解析重要成员属性初始化添加数据清除数据获取数据size和length方法集合操作&#xff1a;与、或、异或 前言 为什么称为bitmap&#xff1f; bitmap不仅仅存储介质以及数据结构不同于hashmap&#xff0c;存储的key和value也…
阅读更多...
Spring MVC概述及入门

Spring MVC概述及入门

MVC介绍 MVC是一种设计模式&#xff0c;将软件按照模型、视图、控制器来划分&#xff1a; M&#xff1a;&#xff08;Model&#xff09;模型层&#xff0c;指工程中的JavaBean&#xff0c;作用是处理数据 数据模型&#xff1a;User、Student&#xff0c;装数据 业务模型&#…
阅读更多...
C++ Primer 第五版 中文版 阅读笔记 + 个人思考

C++ Primer 第五版 中文版 阅读笔记 + 个人思考

C Primer 第五版 中文版 阅读笔记 个人思考 第 10 章 泛型算法10.1 概述练习10.1练习10.2 第 10 章 泛型算法 泛型的体现&#xff1a;容器类型&#xff08;包括内置数组&#xff09;&#xff0c;元素类型&#xff0c;元素操作方法。 顺序容器定义的操作&#xff1a;insert&a…
阅读更多...
Android-多线程

Android-多线程

线程是进程中可独立执行的最小单位&#xff0c;也是 CPU 资源&#xff08;时间片&#xff09;分配的基本单位&#xff0c;同一个进程中的线程可以共享进程中的资源&#xff0c;如内存空间和文件句柄。线程有一些基本的属性&#xff0c;如id、name、以及priority。 id&#xff1…
阅读更多...
API调试怎么做？Apipost快速上手

API调试怎么做？Apipost快速上手

前言 Apipost是一款支持 RESTful API、SOAP API、GraphQL API等多种API类型&#xff0c;支持 HTTPS、WebSocket、gRPC多种通信协议的API调试工具。除此之外&#xff0c;Apipost 还提供了自动化测试、团队协作、等多种功能。这些丰富的功能简化了工作流程&#xff0c;提高了研发…
阅读更多...
antv/x6_2.0学习使用（四、边）

antv/x6_2.0学习使用（四、边）

一、添加边 节点和边都有共同的基类 Cell&#xff0c;除了从 Cell 继承属性外&#xff0c;还支持以下选项。 属性名类型默认值描述sourceTerminalData-源节点或起始点targetTerminalData-目标节点或目标点verticesPoint.PointLike[]-路径点routerRouterData-路由connectorCon…
阅读更多...
网络流量分析与故障分析

网络流量分析与故障分析

1.网络流量实时分析 网络监控 也snmp协议 交换机和服务器打开 snmp就ok了 MRTG或者是prgt 用于对网络流量进行实时监测&#xff0c;可以及时了解服务器和交换机的流量&#xff0c;防止因流量过大而导致服务器瘫痪或网络拥塞。 原理 通过snmp监控 是一个…
阅读更多...
MES/MOM标准之ISA-95基础内容介绍

MES/MOM标准之ISA-95基础内容介绍

ISA-95 简称S95&#xff0c;也有称作SP95。ISA-95 是企业系统与控制系统集成国际标准&#xff0c;由国际自动化学会(ISA&#xff0c;International Society of Automation) 在1995年投票通过。该标准的开发过程是由 ANSI(美国国家标准协会) 监督并保证其过程是正确的。ISA-95不…
阅读更多...
acwing 并查集

acwing 并查集

目录 并查集的路径压缩两种方法法一法二 AcWing 240. 食物链AcWing 837. 连通块中点的数量示例并查集自写并查集 并查集的路径压缩两种方法 法一 沿着路径查询过程中&#xff0c;将非根节点的值都更新为最后查到的根节点 int find(int x) {if (p[x] ! x) p[x] find(p[x]);r…
阅读更多...
爬取去哪网旅游攻略信息

爬取去哪网旅游攻略信息

代码展现&#xff1a; import requests import parsel import csv import time f open(旅游去哪攻略.csv,modea,encodingutf-8,newline) csv_writer csv.writer(f) csv_writer.writerow([标题,浏览量,日期,天数,人物,人均价格,玩法]) for page in range(1,5):url fhttps://…
阅读更多...
整理的Binder、DMS、Handler、PMS、WMS等流程图

整理的Binder、DMS、Handler、PMS、WMS等流程图

AMS&#xff1a; Binder&#xff1a; Handler&#xff1a; PMS&#xff1a; starActivity&#xff1a; WMS&#xff1a; 系统启动&#xff1a;
阅读更多...
最新文章

Copyright @ 2022~2023