C++进阶--红黑树

红黑树

  • 一、红黑树的概念
  • 二、红黑树的性质
  • 三、红黑树结点的定义
  • 四、红黑树的插入
  • 五、红黑树的验证
  • 七、红黑树的查找
  • 七、红黑树与AVL树的比较
  • 七、完整代码
    • RBTree.h

一、红黑树的概念

  红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

在这里插入图片描述

二、红黑树的性质

红黑树一共有五个性质：
1.每个结点不是红色就是黑色
2.根结点是黑色的
3.如果一个结点是红色的，则它的两个孩子结点是黑色的
4.对于每个结点，从该结点到其他所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5.每个叶子结点都是黑色的（此处的叶子结点指的是空结点）

为什么满足上面的性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍？

  根据红黑树的性质3可以得出，红黑树当中不会出现连续的红色结点，而根据性质4又可以得出，从某一结点到其后代叶子结点的所有路径上包含的黑色结点的数目是相同的。
  我们假设在红黑树中，从根到叶子的所有路径上包含的黑色结点的个数都是N个，那么最短路径就是全部由黑色结点构成的路径，即长度为N。
  而最长可能路径就是由一黑一红结点构成的路径，该路径当中黑色结点与红色结点的数目相同，即长度为2N
  因此，红黑树从根到叶子的最长可能路径不会超过最短可能路径的两倍。

三、红黑树结点的定义

这里直接实现K V模型的红黑树，为了方便后续的旋转操作，将红黑树的结点定义为三叉链结构，除此之外还新加入了一个成员变量，用于表示结点的颜色。

template <class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};

这里使用枚举来定义结点的颜色，这样可以增加代码的可读性和可维护性

enum Colour
{
	RED,
	BLACK,
};

为什么构造结点时，默认将结点的颜色设置为红色？

  当我们向红黑树插入结点时，若我们插入的是黑色结点，那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个，即破坏了红黑树的性质4，此时我们就需要对红黑树进行调整。
  若我们插入红黑树的结点时红色的，此时如果其父结点也是红色的，那么表明出现了连续的红色结点，即破坏了红黑树的性质3，此时我们需要对红黑树进行调整，但如果其父结点是黑色的，那我们就无需对红黑树进行调整，插入后仍满足红黑树的要求。
总结：

  • 插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整
  • 插入红色结点，可能破坏红黑树的性质3，可能对红黑树进行调整

四、红黑树的插入

红黑树插入结点的逻辑分为三步
1.按二叉搜索树的插入方法，找到待插入位置。
2.将待插入结点插入到树中。
3.若插入结点的父结点是红色的，则需要对红黑树进行调整。
  其中前两步与二叉搜索树插入结点时的逻辑相同，红黑树的关键在于第三步对红黑树的调整。
  实际上插入结点后并不是一定会对红黑树进行调整，若插入结点的父结点是黑色的，那么我们就不用对红黑树进行调整，因为本次结点的插入并不会破坏红黑树的五点性质。
  只有当插入结点的父结点是红色时才需要对红黑树进行调整，因为我们默认插入的结点就是红色的，如果插入结点的父结点也是红色的，那么此时就出现了连续的红色结点，因此需要对红黑树进行调整。因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在。
  红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。

情况一：插入结点的叔叔存在，且叔叔的颜色是红色

  此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。
在这里插入图片描述

  但是调整还没有结束，因为此时祖父结点变成了红色，如果祖父结点是根节点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。
  但如果祖父结点不是根结点的话，我们就需要将祖父结点当作新插入的结点，再判断其父结点是否为红色，若其父结点也是红色，那么又需要根据其叔叔的不同，进行不同的调整操作

情况二：插入结点的叔叔存在，且叔叔的颜色是黑色

  这种情况一定是在情况一继续往上调整的过程中出现的，即这种情况下的cur结点一定不是新插入的结点，而是上一次情况一调整过程中的祖父结点。如果叔叔结点存在，则其一定是黑色的，那么cur结点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur结点的颜色由黑色改成红色。

注意
1.从根结点一直走到空位置就算一条路径，而不是从根结点走到左右结点均为空的叶子结点时才算一条路径。
2.情况二和情况三均需要进行旋转处理，旋转处理后无需往上进行调整。
在这里插入图片描述
当成直线关系时，p为g的左孩子，cur为p的左孩子，则进行右单旋转操作，再进行颜色调整。

在这里插入图片描述
当成折线关系时，p为g的左孩子，cur为p的右孩子，则进行左右双旋，再进行颜色调整。

情况三：插入结点的叔叔不存在

在这种情况下的cur结点一定是新插入的结点，而不可能是由情况一变化而来的，因为叔叔不存在说明在p的下面不可能再挂黑色结点了。

在这里插入图片描述

当成直线关系时，p为g的左孩子，cur为p的左孩子时，就需要进行左单旋操作，再进行颜色调整。

在这里插入图片描述
当出现折线关系时，p为g的左孩子，cur为p的右孩子时，就需要进行左右双旋操作，再进行颜色调整。

bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			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 && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					
					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else //情况2+3： u不存在/u存在且为黑，旋转+变色（p变黑，g变红）
				{
					//      g
					//   p     u
					// c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//       g
						//     p   u
						//       c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						//parent->_col = RED;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else // (grandfather->_right == parent)
			{
				//     g
				//   u   p
				//         c
				
				Node* uncle = grandfather->_left;
				//情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//     g
					//   u   p
					//         c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						//     g
						//   u   p
						//     c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
				
			}
		}

		_root->_col = BLACK;
		return true;
	}


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 (ppnode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}


	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 (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}

注意：在红黑树调整后，需要将根结点的颜色变为黑色，因为红黑树的根结点可能在情况一的调整过程中被变成了红色。

五、红黑树的验证

  红黑是也是一种特殊的二叉搜索树，因此我们可以先获取二叉树的中序遍历，来判断该二叉树是否满足二叉搜索树的性质。

void InOrder()
	{
		_InOrder(_root);
	}


void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

但中序有序只能证明是二叉搜索树，要证明二叉树是红黑树还需验证该二叉树是否满足红黑树的性质。

bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根结点颜色是红色" << endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		//连续红色结点
		return _Check(_root,0,benchmark);
	}

	int Height()
	{
		return _Height(_root);
	}

int _Height(Node* root)
	{
		if (root == NULL)
			return 0;

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}

	bool _Check(Node* root,int blackNum,int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色结点的数量不相等" << endl;
				return false;
			}
			//cout << blackNum << endl;
			return true;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col==RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}

		return _Check(root->_left,blackNum,benchmark)
			&& _Check(root->_right,blackNum,benchmark);
	}

七、红黑树的查找

红黑树的查找函数与二叉搜索树的查找方式一模一样
1.若树为空树，则查找失败，返回nullptr
2.若key值小于当前结点的值，则应该在该结点的左子树当中进行查找
3.若key值大于当前结点的值，则应该在该结点的右子树当中进行查找
4.若key值等于当前结点的值，则查找成功，返回对应结点

Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

七、红黑树与AVL树的比较

  红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

七、完整代码

RBTree.h

#pragma once

enum Colour
{
	RED,
	BLACK,
};


template <class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}

};


template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:

	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			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 && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					
					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else //情况2+3： u不存在/u存在且为黑，旋转+变色（p变黑，g变红）
				{
					//      g
					//   p     u
					// c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//       g
						//     p   u
						//       c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						//parent->_col = RED;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else // (grandfather->_right == parent)
			{
				//     g
				//   u   p
				//         c
				
				Node* uncle = grandfather->_left;
				//情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//     g
					//   u   p
					//         c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						//     g
						//   u   p
						//     c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
				
			}
		}

		_root->_col = BLACK;
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
	}


	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根结点颜色是红色" << endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		//连续红色结点
		return _Check(_root,0,benchmark);
	}

	int Height()
	{
		return _Height(_root);
	}

private:

	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}

	int _Height(Node* root)
	{
		if (root == NULL)
			return 0;

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}

	bool _Check(Node* root,int blackNum,int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色结点的数量不相等" << endl;
				return false;
			}
			//cout << blackNum << endl;
			return true;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col==RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}

		return _Check(root->_left,blackNum,benchmark)
			&& _Check(root->_right,blackNum,benchmark);
	}

	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 (ppnode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}


	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 (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	Node* _root=nullptr;
};



void Test_RBTree1()
{
	//int a[] = { 16,3,7,11,9,26,18,14,15 };
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
		//cout << e << "插入：" << t1.IsBalance() << endl;
	}
	t1.InOrder();
	cout << t1.IsBalance() << endl;
}


void Test_RBTree2()
{
	srand(time(0));
	const size_t N = 100000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand()+i;
		t.Insert(make_pair(x, x));
		//cout << t.IsBalance() << endl;
	}
	//t.InOrder();

	cout << t.IsBalance() << endl;
	cout << t.Height() << endl;
}

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

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

相关文章

IaC基础设施即代码：使用Terraform 连接 alicloud阿里云

IaC基础设施即代码：使用Terraform 连接 alicloud阿里云

目录 一、实验 1.环境 2.alicloud阿里云创建用户 3.Linux使用Terraform 连接 alicloud 4.Windows使用Terraform 连接 alicloud 二、问题 1.Windows如何申明RAM 相关变量 2.Linux如何申明RAM 相关变量 3. Linux terraform 初始化失败 4.Linux terraform 计划与预览失败…
阅读更多...
关于高通Android 平台上qssi的介绍

关于高通Android 平台上qssi的介绍

1. QSSI 是 Qualcomm Single System Image 的缩写。 2. Android Q上开始支持QSSI。 3. QSSI 是用来编译system.img的 3.1 QSSI编译注意事项 lunch qssi ------ 编译system.img lunch target ------ 编译其余的image 3.2 有QSSI和没有QSSI的编译流程对比 没有QS…
阅读更多...
YOLOv5独家原创改进：多层次特征融合（SDI）结合PConv、DualConv、GSConv，实现二次创新 | UNet v2最新论文

YOLOv5独家原创改进：多层次特征融合（SDI）结合PConv、DualConv、GSConv，实现二次创新 | UNet v2最新论文

💡💡💡本文独家改进：多层次特征融合（SDI）高效结合DualConv、PConv、GSConv等实现二次创新 1)替代原始的Concat； 收录 YOLOv5原创自研 https://blog.csdn.net/m0_63774211/category_12511931.html 💡💡💡全网独家首发创新（原创），适合paper ！！！ 💡�…
阅读更多...
Docker运行RabbitMQ并使用SpringAMQP操作

Docker运行RabbitMQ并使用SpringAMQP操作

文章目录 一、RabbitMQ运行二、整合SpringAMQP1. 引入依赖 三、测试1. 消费者2. 生产者3. 运行 一、RabbitMQ运行 拉取docker镜像 docker pull rabbitmq:3-management基础运行命令 docker run \-e RABBITMQ_DEFAULT_USERrabbitmq \-e RABBITMQ_DEFAULT_PASSrabbitmq \--name…
阅读更多...
Vue3 如何使用移动端调试工具vConsole

Vue3 如何使用移动端调试工具vConsole

1、安装 pnpm i vconsole2、在src/utils下新建vconsole.ts&#xff0c;写入以下代码 // 这是移动端控制台调试工具&#xff0c;需要调试就打开,不用就注释 import vConsole from vconsole const vconsole new vConsole()3、src/main.ts 引入&#xff0c;需要调试就打开,&…
阅读更多...
数据结构学习之链式栈应用的案例（最小栈）

数据结构学习之链式栈应用的案例（最小栈）

实例要求&#xff1a; 设计一个支持入栈、出栈、取栈顶元素等操作&#xff0c;并能在常数时间内检索到最小元素的栈&#xff1b; 实现 MinStack 类: MinStack* minStackCreate() 初始化堆栈对象&#xff0c;即建栈&#xff1b; void minStackPush(MinStack* obj, int val) …
阅读更多...
DICE模型的原理与推导、碳循环与气候变化、政策评估、不确定性分析与代码分析

DICE模型的原理与推导、碳循环与气候变化、政策评估、不确定性分析与代码分析

目录 专题一&#xff1a;DICE模型的原理与推导 专题二&#xff1a;碳循环与气候变化 专题三&#xff1a;政策评估 专题四&#xff1a;不确定性分析与代码分析 更多应用 随着温室气体排放量的增大和温室效应的增强&#xff0c;全球气候变化问题受到日益的关注。我国政府庄严…
阅读更多...
Linux驱动学习—IIC总线之FT5X06触摸驱动实验

Linux驱动学习—IIC总线之FT5X06触摸驱动实验

1、实现触摸坐标值上报 流程图&#xff1a; 设备树如下&#xff1a; 触摸设备对应的设备树节点是&#xff1a; 读取坐标的寄存器&#xff1a; #include <linux/init.h> #include <linux/module.h> #include <linux/i2c.h> #include <linux/gpio.h> #i…
阅读更多...
【排序篇3】快速排序、归并排序

【排序篇3】快速排序、归并排序

目录 一、快速排序1.1 递归1.2 非递归 二、归并排序2.1 递归2.2 非递归 一、快速排序 1.1 递归 快速排序的递归采用二叉树的前序遍历的思路&#xff0c;单趟排序先确定好一个元素的位置&#xff0c;然后往后递归再确定其他子区域内的某个元素的位置&#xff0c;直到只有一个元…
阅读更多...
隧道应用4-内网穿透EW的简单使用

隧道应用4-内网穿透EW的简单使用

与netsh端口映射内网类似&#xff0c;也是通过跳板机实现 EW官网地址&#xff1a;http://rootkiter.com/EarthWorm EW 是一套便携式的网络穿透工具&#xff0c;具有 SOCKS v5服务架设和端口转发两大核心功能&#xff0c;可在复杂网络环境下完成网络穿透。 注&#xff1a; 考虑…
阅读更多...
【洛谷千题详解】P7072 [CSP-J2020] 直播获奖

【洛谷千题详解】P7072 [CSP-J2020] 直播获奖

输入样例&#xff1a; 10 60 200 300 400 500 600 600 0 300 200 100 输出样例&#xff1a; 200 300 400 400 400 500 400 400 300 300 #include<bits/stdc.h> using namespace std; int main() {int n,w,s,a[605]{0};cin>>n>>w;for(int i1;i<n;i){sca…
阅读更多...
P1179 [NOIP2010 普及组] 数字统计————C++

P1179 [NOIP2010 普及组] 数字统计————C++

目录 [NOIP2010 普及组] 数字统计题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示 解题思路Code1Code2运行结果 [NOIP2010 普及组] 数字统计 题目描述 请统计某个给定范围 [ L , R ] [L, R] [L,R] 的所有整数中&#xff0c;数字…
阅读更多...
使用集群提交作业步骤

使用集群提交作业步骤

首先&#xff0c;先在terminal中创建脚本 vi job.slurmvi命令&#xff1a;打开文件 文本内容为&#xff1a; #!/bin/bash #sbatch -j test #作业名为test&#xff0c;可以自定义 #sbatch -w,--nodelist<Node1> #提交到节点1跑代码 #sbatch -o test.out #屏幕上的输出文…
阅读更多...
java客户端连接redis并设置序列化处理

java客户端连接redis并设置序列化处理

1、导入依赖 <!--继承父依赖--> <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.12.RELEASE</version><relativePath/> <!-- lookup paren…
阅读更多...
css深度选择器 /deep/

css深度选择器 /deep/

一、/deep/的含义和使用 /deep/ 是一种 CSS 深度选择器&#xff0c;也被称为深度组合器或者阴影穿透组合器&#xff0c;主要用在 Web 组件样式封装中。 在 Vue.js 或者 Angular 中&#xff0c;使用了样式封装技术使得组件的样式不会影响到全局&#xff0c;也就是说组件内部的…
阅读更多...
【漏洞复现】大华 DSS 数字监控系统 itcBulletin SQL 注入

【漏洞复现】大华 DSS 数字监控系统 itcBulletin SQL 注入

漏洞描述 大华 DSS存在SQL注入漏洞，攻击者 pota/services/itcBuletin 路由发送特殊构造的数据包，利用报错注入获取数据库敏感信息。攻击者除了可以利用 SQL注入漏词获取数据库中的信息例如，管理员后台密码、站点的用户人人信息)之外，甚至在高权限的情况可向服务器中写入木…
阅读更多...
Echarts图表如何利用formatter自定义tooltip的内容和样式

Echarts图表如何利用formatter自定义tooltip的内容和样式

在展示多数据图表的时候 有的时候需要图例也展示出一些内容来&#xff0c;例如官方这样子&#xff1a;鼠标悬停的时候展示该点数据 但是&#xff0c;官方提供的样式有时不适用所有的开发场景 我的项目需要实现鼠标悬停在某一点的时候&#xff0c;只展示该条线的数据&#xff0…
阅读更多...
异常处理注解 @ExceptionHandler

异常处理注解 @ExceptionHandler

今天记录下 SpringBoot 中 ExceptionHandler 的使用。 场景 有一个员工表(employee)&#xff0c;且给表中的 username 属性设置了唯一性。 -- auto-generated definition create table employee (id bigint auto_increment comment 主键primary key,name va…
阅读更多...
C++STL

C++STL

STL基本概念 standard template library : 标准模板库STL从广义上可以分为&#xff1a; 容器(container) 算法(algorithm) 迭代器(iterator)。 容器和算法之间通过迭代器进行无缝连接。 STL几乎所有的代码都采用了模板类或者模板函数STL六大组件 STL的容器 STL的容器就是将运…
阅读更多...
uniapp滑动页面切换和下拉刷新，触底加载更多（swiper + scroll-view）

uniapp滑动页面切换和下拉刷新，触底加载更多（swiper + scroll-view）

因为官方文档乱七八糟的&#xff0c;所以自己来总结下 需求&#xff1a; 常见的上方tag标签切换&#xff0c;下方是页面&#xff0c;上面点击切换&#xff0c;下面页面也切换&#xff0c;下方列表有下拉刷新&#xff0c;触底加载更多 因为这两个组件都是固定高度的&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023