C++进阶--＞红黑树的实现

1、红黑树的概念

红黑树是一棵二叉搜索树，他和前面AVL树不同的是红黑树不是通过平衡因子来保证树的平衡，而是在树结点的处加多了个记录颜色的变量，这个变量可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，从而确保没有一条路径会比其他路径长处2倍。

1.1 红黑树的特性：

1、每个结点不是黑色就是红色，没有其他颜色。

2、根结点是黑色的。

3、每个根结点到每个路径的结尾处也就是nullptr处时，访问到黑色结点的数量一样，简单点说就是每个路径上的黑色结点的个数是一样的。

4、如果一个结点是红色的，那么他的孩子结点必定是黑色，不能是红色，也就是说一条路径上没有连续的红色结点。

这里补充一下就是黑色结点可以有无数个连续的，不像红色的结点那样有限制。

 1.2 红黑树的路径（解释）

可能我们会好奇为什么红黑树能够确保没有路径能比任何一条路径的长度超出两倍。这里我们进行解释一下。

首先我们观察红黑树的特性的最后两条即“每条路径上黑色结点的个数相同”，还有“如果有红色结点，则红色结点的孩子结点必然是黑色，不能存在连续的红色结点”，而这两个条件就已经定死了。

比方说我们想实现最短路径和最长路径，且里面都只有2个黑色结点，最短路径就只能是两个黑色结点连着，而最长路径就是“黑红黑红”的顺序链接，所以最长路径的长度为4。如下图可见

假设最短距离为bh（black height），最长距离就为2bh，我们知道最短距离和最长距离是极端情况，我们平常是很少达到这种情况的所以我们设树长为h，

那么我们就可以推导出一个公式：bh <= h <= 2bh。

根据上面这个公式，我们又可以推出时间复杂度，因为前面二叉树我们讲过树的高度是h， 每层结点的个数为2^h-1，推得2^h-1 <= N <= 2^2*h - 1，h≈logN，红黑树的增删查改最坏也要走2logN，所以时间复杂度为O（logN）。        

2、红黑树的实现

2.1 红黑树的结构实现

上面我们说了红黑树和前面的结构几乎类似，只是多了一个表示该结点是什么颜色的变量，该颜色的变量我们可以枚举完即“红”和“黑”那么，我们就可以使用枚举关键字enum进行存储红和黑变量。

而红黑树我们是用key_value结构实现的，那么我们就使用到pair类，然后还有一个Color类型；

结点结构的实现：

#pragma once
#include<iostream>
using namespace std;
//设置红黑结点的定义
enum Colour
{
	RED,
	BLACK

};

//使用key_value的结构来实现红黑树
template<class K, class V>

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

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

树结构的实现：

和前面AVL树基本类似，只需要传入一个根结点给他就可以，这些都不是重点，所以这里直接上代码。

//定义红黑树的树结构
template<class K, class V>
class BRTree
{
	typedef RBTreeNode<K, V> Node;
public:
private:
	Node* _root = nullptr;
};

2.2 红黑树插入的实现

红黑树的插入我们需要遵循上面红黑树的4条特性，这里我们先列个大概过程出来，因为后面有多种情况需要进行分析。

1、插入的值按二叉搜索树的规则插入。

2、如果树为空，那么插入的结点就是黑色的结点，遵循前面提到的红黑树的特性第二点“根结点是黑色的”。

3、如果树不为空，那么插入的结点即新增的结点就必须是红色的，这个对应前面的第4条规则，因为插入的结点如果是黑色的话就会破坏第四条特性即“每条路径上的黑色结点的数量是相同的”。

4、如果树不为空，插入结点后，如果插入结点的父亲结点也是红色的话违反第三个特性即“不能存在连续两个红色的结点”，那么我们就需要进行分类讨论处理。

这里我们先说明一下等会图内出现的单个字母的表示意思

c为cur，c的父亲为p（parent），p的父亲为g（grandparent），p的兄弟为u（uncle）。

  2.2.1 情况一：只需要变色

情况一的条件：只需要变色的条件是c为红，p为红，u存在且为红，g为黑。

即如下图这种情况：

OK，我们来分析一下，首先我们的红黑树的一条特性“如果一个结点是红色，那么他的孩子结点都必须是黑色”，我们看p和c都是红色，连续了，所以我们需要把他们纠正过来，有两种方法：

1、让p变为黑色

2、让c变为黑色

如果我们选择第二种的话，那我们插入的规则即“新插入的结点必须是红色”就被破坏了，那为什么我们不直接改掉规则，让新插入的结点必须是黑色呢？如果我们这么做的话就会破坏“每条路径上黑色结点的数量相同”的规则，这条规则最难维护，因为如果我们在一条路径插入了一个黑色结点，那么我们为了保证这条规则，还需要改变每一条路径上的黑色结点的数量，这样就太麻烦了。

所以我们选择第一种，让parent变为黑色，然后为了解决“每条路径上黑色结点的数量相同”的规则，我们只需要让grandparent变为红色，parent和uncle变为黑色即可。

如果这棵树是某棵树的子树的话则还需要往上继续修改颜色。

实现如下代码所示：

				Node* grandparent = parent->_parent;
				if (grandparent->_left == parent)
				{
					Node* uncle = grandparent->_right;
					//uncle存在且为红色
					if (uncle && uncle->_col == RED)
					{
						//开始变色
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;

						//往上走
						cur = grandparent;
						parent = cur->_parent;
					}

这里只是部分代码的实现，只是这一棵子树的代码实现。最后面会给出完整的代码实现。

2.2.2 情况二：单旋+变色

情况二的条件：cur为红，parent为红，grandparent为黑，uncle不存在或存在且为黑。

uncle不存在的：

uncle存在且为黑色的：

uncle存在或者不存在与cur的关系：

如果uncle不存在，那么cur一定是新增的结点，因为如果u不存在，cur是旧结点的话（旧结点就是本身就存在树内，只是因为子树的变化导致cur从黑色变成红色），那么在变成红色前就已经对不上了，因为那会cur是黑色结点，uncle不存在，root到cur路径就会比root到uncle路径上多一个黑色结点，这不符合红黑树的规则。

如果uncle存在而且为黑色结点的话，那么cur就肯定是旧的结点，c之前就是黑色结点，只不过c的子树中插入了一个结点然后符合情况一（只需要变色），cur作为下面子树的grandparent最终就变成红色了。

分析：因为上面说过了，不能对cur进行改变，那么我们就需要对parent进行修改颜色，让parent的颜色变成黑色，这样就可以解决，但是如果我们按情况一的方法来变色的话就会导致左子树出现两个黑色，因为根结点必须是黑色，尽管通过情况一进行变色后是没有违反黑色结点数量的规则，但是违反了root结点必须为黑色的规则，所以我们 需要对其进行旋转。

实现操作如下：

如果出现下图的情况，那我们必须要让g为旋转点进行右单旋，让p变成root，p变黑，g变红

进行旋转加变色后得到下面这个图：

如果出现下图的情况：那我们一样是按照让g进行单旋，，d变成g的左边，g变成p的右边，p成为新的root，p变黑，g变红，和前面其实是一样的，只不过多了几个结点而已，因为单旋的规则是一样的，变色的规则也是一样的，这里就不细讲单旋操作的逻辑关系，因为前面AVL树有比较详细的讲解。

而单旋+变色的实现很简单，我们只需要使用程序员的“cv大法”，去前面那一篇AVL树的实现那里拿一个右单旋过来使用即可，旋转完我们再让g变成红色，p变成黑色即可。

实现代码如下可见：

						//进行单旋操作
						if (cur == parent->_left)
						{
							RotateR(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}

通过此处我们可以发现当cur==parent->_left的时候就进行单旋加变色操作，如果我们看过前面的AVL树实现那一篇就会发现，当插入的那个结点在插入节点的parent结点的左边的时候是进行单旋操作，在右边如果单单只是用单旋不行，还需要通过双旋进行处理，至此，我们就引出情况三；

2.2.3 情况三：双旋+变色

情况三：c为红，p为红，g为黑，u存在为黑或者不存在都可以，主要的条件是：如果p在g的左边，那么c在p的右边，如果p在g的右边，那么c在p的左边。

其实和前面AVL树实现单旋和双旋的条件很相似，只不过红黑树需要改变结点的颜色。

实现操作如下：

如果出现下面这种情况，我们就思考：我们前面的情况二是通过单旋+变色来解决问题的，但是这个图和前面情况二的不一样，情况二插入的结点是一直往一边倾，那我们就需要构造出一直往一边倾得情况，需要让p进行左旋（因为以p为root的子树是往右倾了，我们想让他往左倾那就需要让他左单旋）。

对p进行左单旋就得到这个，那么我们发现这个结构就和上面的单旋的结构一样了，就可以对g使用右单旋，然后再让c变黑，g变红。

最终得到这个。

如果出现下面这个图，解决思路也是一样的，因为下面这张图其实是一张抽象图，包含了上面图的情况，但是解决思路也是完全类似，所以这里直接开始讲实现的思路；

首先是对p进行左单旋，然后再对g进行右单旋，让c变成树的root，b变成g的左子树，p和g分别变成c的左右子树，然后再让c变黑，g变红，这里的双旋思路和前面实现AVL树也是一样的，只不过就是删掉了平衡因子的修改，添加了颜色的改变。

直接上代码：

						//进行双旋操作
						else
						{
							RotateR(parent);
							RotateL(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
						break;
					}

ps：这个else是接着上面那个if条件的。

因为左右双旋和右左双旋的实现思路也几乎一样，所以这里也不过多讲述，主要就是uncle结点和parent结点换了位置。

所以接下来我们直接上insert的完整代码：

	bool Insert(const pair<K, V>& kv)
	{
		//如果树为空插入结点就需要让该结点为黑色
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		//不是空树，开始找合适的插入位置
		Node* cur = _root;
		Node* parent = nullptr;
		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);
			cur->_col = RED;
			if (parent->_kv.first < kv.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			//链接上父亲
			cur->_parent = parent;

			//判断parent是否存在，因为这是遍历完整个树的
			while (parent && parent->_col == RED)
			{
				Node* grandparent = parent->_parent;
				if (grandparent->_left == parent)
				{
					Node* uncle = grandparent->_right;
					//uncle存在且为红色
					if (uncle && uncle->_col == RED)
					{
						//开始变色
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;

						//往上走
						cur = grandparent;
						parent = cur->_parent;
					}
					//uncle不存在或者为黑色就需要进行旋转
					else
					{
						//进行单旋操作
						if (cur == parent->_left)
						{
							RotateR(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}
						//就说明插入或存在且从黑变成红的C在parent的右边，就需要进行双旋操作
						else
						{
							//      g
							//   p    u
							//     c
							RotateL(parent);
							RotateR(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
						break;
					}
				}
				//parent在grandparent的右边
				else
				{
					//   g
					// u   p
					Node* uncle = grandparent->_left;
					//如果uncle存在且uncle的col为红色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandparent->_col = RED;

						cur = grandparent;
						parent = cur->_parent;
					}
					//uncle不存在或uncle为黑需要进行旋转操作
					else
					{
						if (cur == parent->_right)
						{
							RotateL(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}
						//进行双旋操作
						else
						{
							RotateR(parent);
							RotateL(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
						break;
					}
				}
			}
			_root->_col = BLACK;
			return true;
	}

ps：前面一大段其实就是平衡二叉树搜索规矩，如果忘记了我们可以看前面平衡二叉树的实现，那里讲的比较详细，其实就是cur->key如果比根结点的大就往右走，小就往左走，一直走到他该处的位置即可，最后这段代码还有一句_root->col = BLACK的作用就是保证根结点的颜色是黑色的。

2.3 红黑树查找的实现

按照二叉搜索树的逻辑实现即可，如果cur的key比当前根结点的key大就往根结点的右子树走，如果cur的key比当前根结点的key小就往根结点的左子树走，一直走到cur该待的位置为止即可。

	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;
	}

2.4 红黑树的验证

如果我们想验证我们的红黑树是否正常，我们只需要验证他们路径上黑色结点的数量是否相等即可。为什么只需要验证第三点特性而不需要验证其他三点特性呢？

其实我们前面的各种操作已经保证了其他三点特性：第一点“每个结点不是黑色就是红色”在用枚举定义变量Colour的时候就已经定死了。

第二点"根结点是黑色"的我们在上面insert的实现的最后一行代码即：_root->col = BLACK也已经保证了这点特性的实现。

第四点"没有连续的两个红色结点"，这个验证很麻烦，因为有两个左右子树结点，且不一定存在，但是我们可以放过来检查孩子结点的父亲结点。（等会这点会在下面的check成员函数实现里实现）。

那么通过第三点验证我们可以找一个参考是refNum，然后我们遍历整棵树的左子树找到一条路径上的黑色结点的值，然后再使用递归检查每一棵树到走到空后黑色结点的个数，然后判断是否和refNum相等，如果不相等就返回false即可。如下代码所示：

	
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}
			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}

    bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 前序遍历走到空时，意味着一条路径走完了
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色结点的数量不相等的路径" << endl;
				return false;
			}
			return true;
		}

		// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色结点" << endl;
			return false;
		}

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

		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}

ps：上面Isbalance就是实现了找refNum值的操作，下面就是实现递归检查最后一个blackNum是否等于refNum的值的操作。

3、完整代码.h和.cpp的代码展示

因为有很多代码例如得到树的高度，树的结点个数还有前序遍历打印都在前面AVL树实现，和在数据结构里的二叉树讲过，而且难度也不是很大，对递归有一定的了解即可看懂，如果不懂的话可以尝试画一下递归展开图进行了解。

3.1 .h代码

#pragma once
#include<iostream>
using namespace std;
//设置红黑结点的定义
enum Colour
{
	RED,
	BLACK

};

//使用key_value的结构来实现红黑树
template<class K, class V>

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

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

//定义红黑树的树结构
template<class K, class V>
class BRTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		//如果树为空插入结点就需要让该结点为黑色
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		//不是空树，开始找合适的插入位置
		Node* cur = _root;
		Node* parent = nullptr;
		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);
			cur->_col = RED;
			if (parent->_kv.first < kv.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			//链接上父亲
			cur->_parent = parent;

			//判断parent是否存在，因为这是遍历完整个树的
			while (parent && parent->_col == RED)
			{
				Node* grandparent = parent->_parent;
				if (grandparent->_left == parent)
				{
					Node* uncle = grandparent->_right;
					//uncle存在且为红色
					if (uncle && uncle->_col == RED)
					{
						//开始变色
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;

						//往上走
						cur = grandparent;
						parent = cur->_parent;
					}
					//uncle不存在或者为黑色就需要进行旋转
					else
					{
						//进行单旋操作
						if (cur == parent->_left)
						{
							RotateR(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}
						//就说明插入或存在且从黑变成红的C在parent的右边，就需要进行双旋操作
						else
						{
							//      g
							//   p    u
							//     c
							RotateL(parent);
							RotateR(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
						break;
					}
				}
				//parent在grandparent的右边
				else
				{
					//   g
					// u   p
					Node* uncle = grandparent->_left;
					//如果uncle存在且uncle的col为红色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandparent->_col = RED;

						cur = grandparent;
						parent = cur->_parent;
					}
					//uncle不存在或uncle为黑需要进行旋转操作
					else
					{
						if (cur == parent->_right)
						{
							RotateL(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}
						//进行双旋操作
						else
						{
							RotateR(parent);
							RotateL(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
						break;
					}
				}
			}
			_root->_col = BLACK;
			return true;
	}




	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* pParent = parent->_parent;

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

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

			subL->_parent = pParent;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

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


	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 前序遍历走到空时，意味着一条路径走完了
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色结点的数量不相等的路径" << endl;
				return false;
			}
			return true;
		}

		// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色结点" << endl;
			return false;
		}

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

		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}


	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

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

	int Size()
	{
		return _Size(_root);
	}

	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 IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}
			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}
private:
	Node* _root = nullptr;



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

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

	int _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;
	}

	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _Size(root->_left) + _Size(root->_right) + 1;
	}
};

3.2 .cpp代码

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

#include"BRTree.h"

void TestRBTree1()
{
	BRTree<int, int> t;
	// 常规的测试用例
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试用例
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

	for (auto e : a)
	{
		t.Insert({ e, e });
	}

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

int main()
{
	TestRBTree1();

	return 0;
}

END!

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

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

相关文章

微信公众号绑定设计-WeChat public platform bing and send message

微信公众号绑定设计-WeChat public platform bing and send message

一 WeChat bind ui 二、message style 三、 consume style 四、send log 五、temp setting
阅读更多...
Linux多线程(个人笔记)

Linux多线程(个人笔记)

Linux多线程 1.Linux线程概念1.1线程的优点1.2线程的缺点 2.Linux线程VS进程3.Linux线程控制3.1创建线程3.2线程tid及进程地址空间布局3.3线程终止3.4线程等待 4.分离线程5.线程互斥5.1互斥锁mutex5.2互斥锁接口5.3互斥锁实现原理5.4可重入VS线程安全 6.线程同步6.1条件变量6.2…
阅读更多...
Java项目实战II基于Spring Boot的药店管理系统的设计与实现（开发文档+数据库+源码）

Java项目实战II基于Spring Boot的药店管理系统的设计与实现（开发文档+数据库+源码）

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 一、前言 随着医疗行业的快速发展和人们对健康需…
阅读更多...
LDO电路分析

LDO电路分析

一、LDO概述 在电压转换电路中&#xff0c;LDO和DC-DC电路是最常用的两种方式&#xff0c;本篇主要介绍LDO相关内容。 LDO是线性电源的一种&#xff0c;它可以实现电源电压的转换&#xff0c;不过主要用在降压领域。它的全称是Low Dropout Regulaor&#xff0c;就是低压差线性…
阅读更多...
VirtualBox虚拟机扩容详解

VirtualBox虚拟机扩容详解

VirtualBox虚拟机扩容详解 virtualbox 扩容找到虚拟机需要扩容的磁盘更改虚拟磁盘的大小 逻辑卷扩容1. 扩展物理卷2. 扩展逻辑卷3. 扩展文件系统 Ubuntu系统安转 minikube 集群后&#xff0c;提示文件系统要炸了&#xff0c;效果如下&#xff1a;可以明显看到 /dev/mapper/ubu…
阅读更多...
第02章 MySQL环境搭建

第02章 MySQL环境搭建

一、MySQL的卸载 如果安装mysql时出现问题&#xff0c;则需要将mysql卸载干净再重新安装。如果卸载不干净&#xff0c;仍然会报错安装不成功。 步骤1&#xff1a;停止MySQL服务 在卸载之前&#xff0c;先停止MySQL8.0的服务。按键盘上的“Ctrl Alt Delete”组合键&#xff0…
阅读更多...
HTML 基础概念：什么是 HTML ? HTML 的构成 与 HTML 基本文档结构

HTML 基础概念：什么是 HTML ? HTML 的构成 与 HTML 基本文档结构

文章目录 什么是 HTML &#xff1f;HTML 的构成 &#xff1f;什么是 HTML 元素&#xff1f;HTML 元素的组成部分HTML 元素的特点 HTML 基本文档结构如何打开新建的 HTML 文件代码查看 什么是 HTML &#xff1f; HTML&#xff08;超文本标记语言&#xff0c;HyperText Markup L…
阅读更多...
AI笔筒操作说明及应用场景

AI笔筒操作说明及应用场景

AI笔筒由来&#xff1a; 在快节奏的现代办公环境中&#xff0c;我们一直在寻找既能提升效率、增添便利&#xff0c;又能融入企业文化、展现个人品味的桌面伙伴。为此&#xff0c;我们特推出专为追求卓越、注重细节的您设计的AI笔筒礼品版&#xff0c;它集高科技与实用性于一身…
阅读更多...
开源项目OpenVoice的本地部署

开源项目OpenVoice的本地部署

前言 本文介绍开源项目OpenVoice的本地部署&#xff0c;基于VsCode和Anaconda(提供python虚拟环境)&#xff0c;来进行部署的。下述不介绍Anaconda的安装流程&#xff0c;要自行安装。且只截图演示关键部分图文演示。 官方项目介绍&#xff1a;OpenVoice&#xff1a;多功能即时…
阅读更多...
【Vue 全家桶】2、Vue 组件化编程

【Vue 全家桶】2、Vue 组件化编程

目录 模块与组件、模块化与组件化 component模块组件 非单文件组件单文件组件 .vue 模块与组件、模块化与组件化 component 模块 组件 局部功能代码和资源的集合 非单文件组件 // 1、创建组件 const school Vue.extend({data(){return {}} }) const student Vue.extend(…
阅读更多...
11.6 校内模拟赛总结

11.6 校内模拟赛总结

打的很顺的一场 复盘 7:40 开题&#xff0c;看到题目名很interesting T1 看起来很典&#xff0c;中位数显然考虑二分&#xff0c;然后就是最大子段和&#xff1b;T2 构造&#xff1f;一看数据范围这么小&#xff0c;感觉不是很难做&#xff1b;T3 神秘数据结构&#xff1b;T…
阅读更多...
nacos本地虚拟机搭建切换wiff问题

nacos本地虚拟机搭建切换wiff问题

背景 在自己的电脑上搭建了vm虚拟机&#xff0c;安装上系统&#xff0c;设置网络连接。然后在vm的系统上安装了中间件nacos&#xff0c;mysql&#xff0c;redis等&#xff0c;后续用的中间件都是在虚拟机系统上安装的&#xff0c;开发在本地电脑上。 我本地启动项目总是请求到…
阅读更多...
深入探讨钉钉与金蝶云星空的数据集成技术

深入探讨钉钉与金蝶云星空的数据集成技术

钉钉报销数据集成到金蝶云星空的技术案例分享 在企业日常运营中&#xff0c;行政报销流程的高效管理至关重要。为了实现这一目标&#xff0c;我们采用了轻易云数据集成平台&#xff0c;将钉钉的行政报销数据无缝对接到金蝶云星空的付款单系统。本次案例将重点介绍如何通过API接…
阅读更多...
Rust 力扣 - 3090. 每个字符最多出现两次的最长子字符串

Rust 力扣 - 3090. 每个字符最多出现两次的最长子字符串

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 本题使用滑动窗口进行求解&#xff0c;使用左指针和右指针分别表示窗口的左边界和窗口的右边界&#xff0c;使用哈希表记录窗口内的字符及其对应数量 我们首先向右移动右指针&#xff0c;将字符加入到哈希表中进…
阅读更多...
Jekins篇（搭建/安装/配置）

Jekins篇（搭建/安装/配置）

目录 一、环境准备 1. Jenkins安装和持续集成环境配置 2. 服务器列表 3. 安装环境 Jekins 环境 4. JDK 环境 5. Maven环境 6. Git环境 方法一&#xff1a;yum安装 二、JenKins 安装 1. JenKins 访问 2. jenkins 初始化配置 三、Jenkins 配置 1. 镜像配置 四、Mave…
阅读更多...
uniApp使用canvas制作签名板

uniApp使用canvas制作签名板

插件市场大佬封装好的 组件 可以直接拿过去 <template><viewclass"whole canvas-autograph flexc"touchmove.prevent.stopwheel.prevent.stopv-show"modelValue"><canvasclass"scroll-view"id"mycanvas"canvas-id&quo…
阅读更多...
解决Knife4j 接口界面UI中文乱码问题

解决Knife4j 接口界面UI中文乱码问题

1、查看乱码情况 2、修改 编码设置 3、删除 target 文件 项目重新启动 被坑死了
阅读更多...
FFmpeg 4.3 音视频-多路H265监控录放C++开发八，使用SDLVSQT显示yuv文件 ，使用ffmpeg的AVFrame

FFmpeg 4.3 音视频-多路H265监控录放C++开发八，使用SDLVSQT显示yuv文件 ，使用ffmpeg的AVFrame

一. AVFrame 核心回顾&#xff0c;uint8_t *data[AV_NUM_DATA_POINTERS] 和 int linesize[AV_NUM_DATA_POINTERS] AVFrame 存储的是解码后的数据&#xff0c;&#xff08;包括音频和视频&#xff09;例如&#xff1a;yuv数据&#xff0c;或者pcm数据&#xff0c;参考AVFrame结…
阅读更多...
【算法】递归+深搜+哈希表：889.根据前序和后序遍历构造二叉树

【算法】递归+深搜+哈希表：889.根据前序和后序遍历构造二叉树

目录 1、题目链接 相似题目: 2、题目 ​3、解法&#xff08;针对无重复值&#xff0c;哈希表递归&#xff09; 函数头-----找出重复子问题 函数体---解决子问题 4、代码 1、题目链接 889.根据前序和后序遍历构造二叉树&#xff08;LeetCode&#xff09; 相似题目: 105.…
阅读更多...
基于SpringBoot的“乐校园二手书交易管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“乐校园二手书交易管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“乐校园二手书交易管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统首页界面图 用户注册界面图 二手…
阅读更多...
最新文章

Copyright @ 2022~2023