数据结构：红黑树的原理和实现

文章目录

  • 红黑树的概念
  • 红黑树的性质
  • 红黑树的模拟实现
    • 红黑树的平衡问题
  • 整体实现和测试

本篇用于进行红黑树的拆解和模拟实现，为之后的map和set的封装奠定基础

红黑树的概念

红黑树也是一种二叉搜索树，但是在每一个节点的内部新增了一个用以表示该节点颜色的值，有黑色和红色两种，通过对任何一条从根到叶子的路径上的各个节点着色方式的限制，红黑树可以保证没有一条路径可以比其他路径长出两倍，因此是平衡的

红黑树的基本模式如下图所示
在这里插入图片描述

红黑树的性质

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

为什么红黑树具有最长路径中节点的个数不超过最短路径个数的2倍？

其实原因在于红黑树的性质，在红黑树中可以存在两个相同黑色节点连在一起，但是绝对不会存在两个连在一起的红色节点，并且每个路径上的黑色节点数量是相同的，基于这两点原因，在红黑树中最长的路径不过是一个红节点穿插一个黑节点…而最短的路径就是所有黑节点是一个接着一个，基于这样的原因就可以保证上面的性质了

红黑树的模拟实现

基本的定义

enum Color
{
	RED,
	BLEAK
};

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

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

为什么这里在定义信息的时候，默认值使用的是RED？

由于红黑树的性质可以知道，一条路径中的黑节点的数量是确定的，当插入的是一个红色节点时，最多会影响的是当前路径的信息，但是如果插入的是一个黑色节点，那么势必会引起整个树中所有完整的路径中的异常，会破坏红黑树中的平衡

红黑树的平衡问题

在插入新节点后，红黑树的平衡可能会受到破坏，下面分情况来进行讨论

定义：当前节点为cur，父亲节点为parent，祖父节点为grandparent，叔叔节点为uncle，而红黑树的插入问题重点看叔叔

1. 如果双亲节点是黑色

在这里插入图片描述
最简单的一种情况，不需要做任何处理，只需要插入即可

2. cur为红色，parent为红色，grandfather为黑色，uncle存在并且是红色

在这里插入图片描述
此时，出现了两个红色节点相继出现的情况，这种情况是不被允许的，因此要做出调整：把parent和uncle都改成黑色，同时将grandfather改成红色

此时需要继续进行情况讨论，如果grandfather是根节点，那么就意味着此时调整已经完毕了，不需要再进行调整，因此把根节点置为黑色，而如果grandfather不为根节点，并且上面一个节点还是红色，那么此时又有两个红色节点相继出现了，此时就需要继续进行调整，把grandfather当成cur，然后进行调整即可

在这里插入图片描述
3. cur为红色，parent为红色，grandfather为黑色，uncle不存在或者是黑色

根据uncle的情况来进行分析：

  1. 如果uncle节点不存在，那么就说明cur一定是新插入的节点，这是因为路径下的黑色节点必定要相同，此时又有两种情况，可能插入在parent的左右两边

在这里插入图片描述

  1. 如果uncle节点存在，并且是黑色，那么就意味着cur节点一定是黑的，现在体现为红色是因为cur子树在调整的过程中把cur的节点变成红色了，如果cur是新插入节点，那么红黑树原来就是错的，因为下面的场景不存在
    在这里插入图片描述
    所以一定是这样的情景：

在这里插入图片描述

而此时cur并不是新插入的节点，新插入节点是cur的左右子树中的一个，现在体现为红色是因为下面子树的调整把cur变成红色了，它原来是黑色的

那么此时就要进行旋转了：令grandparent右旋即可完成降高度的效果，再进行变色即可

在这里插入图片描述
因此将上述的过程都综合起来，就可以完成代码的实现了

	bool insert(const pair<K, V>& kv)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		// 根据搜索二叉树的基本逻辑完成
		if (_root == nullptr)
		{
			_root = new Node(kv);
		}
		else
		{
			// 插入数据
			while (cur)
			{
				if (cur->_kv.second > kv.second)
				{
					// 插入元素小于当前节点元素，插入到左边
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.second < kv.second)
				{
					// 插入元素大于当前节点元素，插入到右边
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			// 此时parent指向最后一个节点，cur为空
			cur = new Node(kv);
			if (parent->_kv.second > cur->_kv.second)
			{
				// 如果插入节点小于它的父亲，就插入到左边
				parent->_left = cur;
				cur->_parent = parent;
			}
			else if (parent->_kv.second < cur->_kv.second)
			{
				// 如果插入节点大于它的父亲，就插入到右边
				parent->_right = cur;
				cur->_parent = parent;
			}
			else
			{
				return false;
			}
		}

		// 至此，普通二叉搜索树的插入已经完成，该进行红黑树的高度调整了
		// 终止条件是parent为空，或者parent已经是黑色了，就意味着不需要调整了
		// parent是红色，意味着grandparent一定存在
		while (parent && parent->_col == RED)
		{
			// 更变的核心是舅舅，因此要先找到舅舅
			// 整体来说还有两种情况，parent可能是grandparent的左或者右，舅舅就是另外一边
			Node* grandparent = parent->_parent;
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				// 1. 舅舅存在，并且是红色
				if (uncle && uncle->_col == RED)
				{
					//     g
					//   p   u
					// c
					
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
				
					// 向上处理
					cur = grandparent;
					parent = cur->_parent;
				}

				// 2. 舅舅不存在
				else
				{
					// 如果cur是左孩子
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						
						// 对grandparent进行右旋
						RotateR(grandparent);
						// 变色
						cur->_col = grandparent->_col = RED;
						parent->_col = BLACK;
					}
					// 如果cur是右孩子
					else
					{
						//     g               g
						//  p       -->     c         -->    c
						//    c           p                p   g
						
						// 对parent左旋，对grandparent右旋
						RotateL(parent);
						RotateR(grandparent);
						// 变色
						cur->_col = BLACK;
						parent->_col = grandparent->_col = RED;
					}

					// 更新之后parent和grandparent顺序乱了，而且也不需要继续调整了，直接break
					break;
				}
			}
			
			// parent是grandparent的右孩子，相同的逻辑再进行一次
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 继续往上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						//   g
						//      p
						//         c
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//     g
						//       p 
						//     c

						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}

					break;
				}
			}
		}
		// 不管上面怎么变都无所谓，只需要保证根节点是黑的就可以了
		_root->_col = BLACK;

		return true;
	}

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

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

整体实现和测试

enum Color
{
	RED,
	BLACK
};

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

	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Color _col;
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(nullptr)
	{}

	bool insert(const pair<K, V>& kv)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		// 根据搜索二叉树的基本逻辑完成
		if (_root == nullptr)
		{
			_root = new Node(kv);
		}
		else
		{
			// 插入数据
			while (cur)
			{
				if (cur->_kv.second > kv.second)
				{
					// 插入元素小于当前节点元素，插入到左边
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.second < kv.second)
				{
					// 插入元素大于当前节点元素，插入到右边
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			// 此时parent指向最后一个节点，cur为空
			cur = new Node(kv);
			if (parent->_kv.second > cur->_kv.second)
			{
				// 如果插入节点小于它的父亲，就插入到左边
				parent->_left = cur;
				cur->_parent = parent;
			}
			else if (parent->_kv.second < cur->_kv.second)
			{
				// 如果插入节点大于它的父亲，就插入到右边
				parent->_right = cur;
				cur->_parent = parent;
			}
			else
			{
				return false;
			}
		}

		// 至此，普通二叉搜索树的插入已经完成，该进行红黑树的高度调整了
		// 终止条件是parent为空，或者parent已经是黑色了，就意味着不需要调整了
		// parent是红色，意味着grandparent一定存在
		while (parent && parent->_col == RED)
		{
			// 更变的核心是舅舅，因此要先找到舅舅
			// 整体来说还有两种情况，parent可能是grandparent的左或者右，舅舅就是另外一边
			Node* grandparent = parent->_parent;
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				// 1. 舅舅存在，并且是红色
				if (uncle && uncle->_col == RED)
				{
					//     g
					//   p   u
					// c
					
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
				
					// 向上处理
					cur = grandparent;
					parent = cur->_parent;
				}

				// 2. 舅舅不存在
				else
				{
					// 如果cur是左孩子
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						
						// 对grandparent进行右旋
						RotateR(grandparent);
						// 变色
						cur->_col = grandparent->_col = RED;
						parent->_col = BLACK;
					}
					// 如果cur是右孩子
					else
					{
						//     g               g
						//  p       -->     c         -->    c
						//    c           p                p   g
						
						// 对parent左旋，对grandparent右旋
						RotateL(parent);
						RotateR(grandparent);
						// 变色
						cur->_col = BLACK;
						parent->_col = grandparent->_col = RED;
					}

					// 更新之后parent和grandparent顺序乱了，而且也不需要继续调整了，直接break
					break;
				}
			}
			
			// parent是grandparent的右孩子，相同的逻辑再进行一次
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 继续往上处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						//   g
						//      p
						//         c
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//     g
						//       p 
						//     c

						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}

					break;
				}
			}
		}
		// 不管上面怎么变都无所谓，只需要保证根节点是黑的就可以了
		_root->_col = BLACK;

		return true;
	}

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

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

	void inorder()
	{
		_inorder(_root);
		cout << endl;
	}

	bool isbalance()
	{
		return _isbalance(_root);
	}

private:
	bool _check(Node* root, int blacknum, const int RefVal)
	{
		// 判断黑色路径数量是否相等
		if (root == nullptr)
		{
			if (blacknum != RefVal)
			{
				cout << "黑色节点数量不相等" << endl;
				return false;
			}
			return true;
		}

		// 判断是否有连续的红色节点
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}

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

		return _check(root->_left, blacknum, RefVal)
			&& _check(root->_right, blacknum, RefVal);
	}

	// 判断红黑树是否平衡
	bool _isbalance(Node* root)
	{
		// 如果根节点是红的，说明错了
		if (root->_col == RED)
		{
			cout << "根节点是红色" << endl;
			return false;
		}

		// 统计一下路径中有多少黑色节点
		int RefVal = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->_col == BLACK)
				RefVal++;
			cur = cur->_left;
		}

		// 判断路径中的黑色节点是否相等
		return _check(root, 0, RefVal);
	}

	void _inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_inorder(root->_left);
		cout << root->_kv.second << " ";
		_inorder(root->_right);
	}

	Node* _root = nullptr;
};

int main()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	RBTree<int, int> t;
	for (auto e : v)
	{
		cout << "Insert:" << e << "->";
		t.insert(make_pair(e, e));
		cout << t.isbalance() << endl;
	}

	cout << t.isbalance() << endl;

	return 0;
}

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

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

相关文章

【python自动化】Playwright基础教程(八)鼠标操作

【python自动化】Playwright基础教程(八)鼠标操作

【python自动化】Playwright基础教程(八)鼠标操作 本文目录 文章目录 【python自动化】Playwright基础教程(八)鼠标操作playwright系列回顾前文代码click模拟鼠标点击dblclick模拟鼠标双击down模拟鼠标按下move模拟鼠标移动up模拟鼠标释放wheel模拟鼠标滚动鼠标长按常用实战引…
阅读更多...
mysql数据库可以执行定时任务

mysql数据库可以执行定时任务

在一些业务需要中&#xff0c;经常需要一些定时任务。如Java的schedule&#xff0c;nodejs的node-schedule等。今天第一次接触了使用数据库的存储过程来执行定时任务。 本篇文章以MySQL数据库为例&#xff0c;介绍通过数据库设置定时任务的方法。本文中以介绍操作过程为主&…
阅读更多...
三数之和问题

三数之和问题

题目描述 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的三元组。…
阅读更多...
asp.net core mvc之 布局

asp.net core mvc之 布局

一、布局是什么&#xff1f; 布局是把每个页面的公共部分&#xff0c;提取成一个布局页面&#xff08;头、导航、页脚&#xff09;。 二、默认布局 _Layout.cshtml 默认的布局是在 /Views/Shared 目录的 _Layout.cshtml文件。通常Shared目录中的视图都是公共视图。该目录下的…
阅读更多...
瑞利长度(Rayleigh length)

瑞利长度(Rayleigh length)

瑞利长度 Rayleigh length 在光学&#xff0c;特别是激光学中&#xff0c;我们设鞍腰部&#xff08;如图中所示的最低处&#xff09;为A&#xff0c;其横截面面积为a&#xff0c;沿光的传播方向&#xff0c;当横截面面积因为散射达到2a时&#xff0c;我们设此处为B&#xff0c;…
阅读更多...
二维码智慧门牌管理系统升级解决方案：运营可视化之道

二维码智慧门牌管理系统升级解决方案：运营可视化之道

文章目录 前言一、系统概述二、数据可视化与运营决策 前言 随着科技的飞速发展和人们生活水平的提高&#xff0c;传统的门牌管理系统已经无法满足现代社会的需求。在这个信息化、智能化的时代&#xff0c;一款升级版的二维码智慧门牌管理系统应运而生&#xff0c;它将以全新的…
阅读更多...
Vmware虚拟机重装 虚拟机能ping通主机，而主机不能ping通虚拟机的问题

Vmware虚拟机重装 虚拟机能ping通主机，而主机不能ping通虚拟机的问题

CClean&#xff0c;用它把你电脑上已经卸载的软件但是注册表还没删干净的把注册表删干净&#xff0c;之前说的那种情况&#xff08;虚拟网络编辑器打不上勾&#xff09;就迎刃而解了。 Ps&#xff1a;CClean&#xff1a;再网上百度就可以查到&#xff0c;软件对用户也很友好&a…
阅读更多...
（11.13 知识总结（路由层）

（11.13 知识总结（路由层）

一、路由层 1.1路由匹配 1.1.1 什么是路由&#xff1f; 路由可以看成是跟在 ip 和 port 之后的地址 1.1.2 url( ) 方法 # 示例 urlpatterns [ url(r^admin/, admin.site.urls), url(r^login/, views.login_func), url(r^register/$, views.register_func), ] url…
阅读更多...
【异步并发编程】使用aiohttp构建Web应用程序

【异步并发编程】使用aiohttp构建Web应用程序

文章目录 1. 写在前面1. 什么是aiohttp&#xff1f;1.1. 什么是异步编程&#xff1f; 2. 安装aiohttp3. 异步HTTP服务器4. 异步请求5. aiohttp REST实例 【作者主页】&#xff1a;吴秋霖 【作者介绍】&#xff1a;Python领域优质创作者、阿里云博客专家、华为云享专家。长期致力…
阅读更多...
iOS：何为空指针和野指针

iOS：何为空指针和野指针

一&#xff1a;什么是空指针和野指针 1、空指针 ①.没有存储任何内存地址的指针就成为空指针&#xff08;NULL指针&#xff09; ②.空指针就是被赋值为0的指针&#xff0c;在没有被具体初始化之前&#xff0c;其值为0. //以下都是空指针&#xff0c;eg: Person *p1 NULL; …
阅读更多...
Linux上C++通过LDAP协议使用kerberos认证AES加密连接到AD服务器

Linux上C++通过LDAP协议使用kerberos认证AES加密连接到AD服务器

一.前言 记录自己在实现这个流程遇到的各种问题&#xff0c;因为我也是看了许多优质的文章以及组内大佬的帮助下才弄成的&#xff0c;这里推荐一个大佬的文章&#xff0c;写的非常优秀&#xff0c;比我这篇文章写得好得很多&#xff0c;最后我也是看这个大佬的代码最终才实现的…
阅读更多...
一行JavaScrip可以做什么？

一行JavaScrip可以做什么？

说在前面 JavaScript 提供了许多方便的方法和操作符来简化常见的任务&#xff0c;使得编程变得更加高效和便捷。无论是数学计算、字符串处理还是数据操作&#xff0c;JavaScript 都能帮助我们以简洁的方式实现所需功能。 代码 1、生成指定范围内的随机整数 const randomInt …
阅读更多...
部分背包问题【贪心算法】

部分背包问题【贪心算法】

部分背包问题是一种经典的贪心问题&#xff0c;物品可以取一部分&#xff0c;也就是可以随意拆分的物品。 算法思路&#xff1a; 用列表保存每个物品的价值及总重量、平均价值&#xff08;性价比&#xff09;。输入数据同时计算每种物品的平均价值。使用自定义的compare函数以…
阅读更多...
2023亚太杯数学建模思路 - 复盘：校园消费行为分析

2023亚太杯数学建模思路 - 复盘：校园消费行为分析

文章目录 0 赛题思路1 赛题背景2 分析目标3 数据说明4 数据预处理5 数据分析5.1 食堂就餐行为分析5.2 学生消费行为分析 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 赛题背景 校园一卡通是集…
阅读更多...
苹果独占鳌头，国产手机围攻，双十一“照妖镜”显露谁有真实力

苹果独占鳌头，国产手机围攻，双十一“照妖镜”显露谁有真实力

随着双十一购物节的结束&#xff0c;电商平台也给出了各手机品牌的销量数据&#xff0c;苹果毫无疑问成为双十一的赢家&#xff0c;不过两家国产手机品牌也显露了他们的实力&#xff0c;已具有与苹果一战之力。 与去年双十一和今年618类似&#xff0c;苹果仍然占据热销榜前列&a…
阅读更多...
信驰达科技加入车联网联盟(CCC)，推进数字钥匙发展与应用

信驰达科技加入车联网联盟(CCC)，推进数字钥匙发展与应用

CCC)的会员。 图 1 深圳信驰达正式成为车联网联盟(CCC)会员 车联网联盟(CCC)是一个跨行业组织&#xff0c;致力于推动智能手机与汽车连接解决方案的技术发展。CCC涵盖了全球汽车和智能手机行业的大部分企业&#xff0c;拥有150多家成员公司。CCC成员公司包括智能手机和汽车制造…
阅读更多...
TLP超线程技术

TLP超线程技术

在实现IPL指令级并行的同时实现TLP(Thread Level Parallelism)线程级并行实现多线程有两种主要的方法超线程即同时多线程&#xff0c;在单个处理器或单个核中设置了两套线程状态部件&#xff0c;共享高速缓存和功能部件当两个线程同时需要某个资源时&#xff0c;其中一个线程必…
阅读更多...
Mac 本地部署thinkphp8【配置环境】

Mac 本地部署thinkphp8【配置环境】

PHP开发工具 我这里选择的是VSCode,里面安装PHP插件 把thinkphp的项目放到 切换到phpenv ![在这里插入图片描述](https://img-blog.csdnimg.cn/a15cc442fab74754ad86d74f6d9942e5.png URL重写如果不改&#xff0c;在请求的时候地址是这样的‘http://tp.com/index.php…
阅读更多...
Prim算法（C++）

Prim算法（C++）

目录 介绍&#xff1a; 代码&#xff1a; 结果&#xff1a; 介绍&#xff1a; Prim算法是一种用于解决最小生成树问题的贪心算法。该算法的主要思想是从一个顶点开始&#xff0c;不断向图中添加边&#xff0c;直到构成一棵包含所有顶点的生成树&#xff0c;使得树的边权之…
阅读更多...
安全认证框架Shrio学习，入门到深度学习,SpringBoot整合Shiro小案例，含代码

安全认证框架Shrio学习，入门到深度学习,SpringBoot整合Shiro小案例，含代码

权限概述 什么是权限 什么是权限 权限管理&#xff0c;一般指根据系统设置的安全策略或者安全规则&#xff0c;用户可以访问而且只能访问自己被授权的资源&#xff0c;不多不少。权限管理几乎出现在任何系统里面&#xff0c;只要有用户和密码的系统。 权限管理再系统中一般分…
阅读更多...
最新文章

Copyright @ 2022~2023