当前位置： 首页 > article >正文

C++：红黑树

article 2024/11/8 16:06:21

目录

红黑树的概念

红黑树的约束颜色规则

​编辑

​编辑

如何确保最长路径不超过最短路径的2倍

红黑树的效率

红黑树的实现

红黑树的整体框架

红黑树的插入

变色

单旋+变色

双旋+变色

插入的完整代码

红黑树的查找

红黑树的验证

红黑树的测试

红黑树的概念

红黑树，是一种二叉搜索树，但在每个节点增加一个存储位来表示节点的颜色（红色或者黑色），通过对任意一条从根到叶子的路径上各个节点的颜色进行约束，以达到没有任何一条路径会比其他路径的2倍还大，从而保持高度差的平衡。

红黑树的约束颜色规则

1.每个节点不是红色就是黑色。

2.根节点是黑色的。

3.红色节点的两个子节点必须是黑色，任意路径下不允许有连续的两个红色节点。

4.从任一节点到其每个叶子的所有路径上黑色节点数相同。

 以下4可树均是合法的红黑树。

《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这⾥所指的叶子结点不是传统的意义上的叶子结点，⽽是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了 ⽅便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，知道下即可。

如何确保最长路径不超过最短路径的2倍

根据颜色规则可知，在一棵红黑树中，设从根到叶子的每条路径都有 x 个黑色节点，那么最短路径就是全黑，长度为x，最长路径是一黑一红交替，长度为 2 * x。

事实上，最长路径和最短路径在每棵红黑树中不一定存在，任意一条从根到叶子的路径长度 l 的范围应该是x <= l <= 2 * x。

红黑树的效率

假设N为红黑树中节点数量，h是最短路径长度，既有 2 ^ h - 1 <= N < 2 ^ (2h) - 1，那么就有h ≈ logN，增删查改的时间复杂度为O(logN)。

红黑树的表达相对AVL树要抽象⼀些，AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对而言，插⼊相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

红黑树的实现

红黑树的整体框架

//枚举值表示颜色
enum Color
{
	RED,
	BLACK
};

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

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

};

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

public:

private:
	Node* _root = nullptr;
};

红黑树的插入

红黑树的插入是实现红黑树最关键的一步，具体过程如下：

  • 插入一个值按照二叉搜索树插入，插入后判断是否符合红黑树的4条规则
  • 非空树的插入，插入的节点必须是红色节点，因为插入黑色节点破坏规则4，规则4很难维护；只有在空树插入的情况下，插入节点才可是是黑色，因为根节点必须是黑色。
  • 非空树插入红色节点，如果父亲节点是黑色的，插入结束；如果父亲节点是红色的，违反了规则3，需要分情况讨论，进行变色和旋转操作。

新增节点为cur，cur的父亲为parent，parent的父亲为grandfather，parent的兄弟为uncle，这4个节点缩写为c、p、g、u。

以下这种情况就违反了规则3，需要特殊处理。

变色

当cur为红，parent为红，grandfather为黑，uncle存在且为红时，则将parent和parent变黑，grandfather变红，那这样就行了嘛吗？不，还没有结束，grandfather变红了，你无法保证grandfather的parent是黑色，grandfather的parent是红色的话还是违反规则，那就得把grandfather当成新的cur继续往上更新，可以说就是往上更新颜色这步，间接导致了单旋+变色和双旋+变色的情况出现。

无论cur是parent的左节点还是右节点，parent是grandparent的左节点还是节点，都是上面的处理方式。

单旋+变色

当cur为红，parent为红，grandfather为黑时：

若uncle不存在，则cur一定是新增节点；

若uncle存在且为黑，则cur一定不是新增的，是更新颜色变化出来的（将原来的grandfather黑色节点变成了红色，然后更新cur到grandfather）。

解决方法就是parent必须变黑，解决连续红色节点问题，但uncle不存在或者存在且为黑，单纯的变色无法解决，需要旋转+变色。

单旋+变色也需要分情况进行不同的旋转处理。

1.若parent是grandfather的左孩子，cur是parent的左孩子，那么先对parent进行右单旋，再把parent变黑，grandfather变红。

 

2.若parent是grandfather的右孩子，cur是parent的右孩子，那么先对parent进行左单旋，再把parent变黑，grandfather变红。

 

双旋+变色

单旋+变色的情况都是在cur和parent偏向同一边的情况下（同在左或同在右），那如果cur和parent不在同一边怎么办？这时候就要用双旋+变色解决了。

1.若parent是grandfather的左孩子，cur是parent的右孩子，那么先对parent进行左单旋，再把cur变黑，grandfather变红。

 

 2.若parent是grandfather的右孩子，cur是parent的左孩子，那么先对parent进行左单旋，再把cur变黑，grandfather变红。

插入的完整代码

void RotateR(Node* parent)
{
	//subL为parent的左孩子节点
	Node* subL = parent->_left;
	//subLR为subL的右子节点
	Node* subLR = subL->_right;

	// 将parent与subLR节点进行链接
	parent->_left = subLR;
	//在SubLR的情况下更改，让其指向正确的父亲
	if (subLR)
		subLR->_parent = parent;

	//提前记录祖父节点
	Node* pParent = parent->_parent;

	//链接subL与parent
	subL->_right = parent;
	parent->_parent = subL;

	//根据parent是否是根节点进行不同处理
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		//将pParent和subL链接
		//但得先判断parent是pParent的左节点还是右节点
		if (pParent->_left == parent)
			pParent->_left = subL;
		else
			pParent->_right = subL;

		//修改subL的parent指针，让其指向正确的父亲
		subL->_parent = pParent;
	}

}

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

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

	Node* pParent = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR;

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

		subR->_parent = pParent;
	}

}


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);
	//非空树插入红色节点
	cur->_col = RED;

	//判断cur应该插入到parent的左节点还是右节点
	if (kv.first > parent->_kv.first)
		parent->_right = cur;
	else
		parent->_left= cur;

	//链接父亲
	cur->_parent = parent;

	//父亲是红色节点，出现连续的红色节点，要处理
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;

		//判断叔叔是grandfather的左节点还是右节点
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;

			//uncle存在且为红
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续向上更新颜色
				cur = grandfather;
				parent = cur->_parent;
			}
			else  //uncle不存在 或者 uncle存在且为黑
			{
				if (cur == parent->_left)
				{
					//     g
				    //   p    u
				    // c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//     g
					//   p    u
					//     c
					RotateL(parent);
					RotateR(grandfather);

					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
		else if (parent == grandfather->_right)
		{
			Node* uncle = grandfather->_left;

			//uncle存在且为红
			if (uncle && uncle->_col == RED)
			{
				//变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续向上更新颜色
				cur = grandfather;
				parent = cur->_parent;
			}
			else //uncle不存在 或者 uncle存在且为黑
			{
				if (cur == parent->_right)
				{
					//     g
					//   u   p
					//        c
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//     g
					//   u    p 
					//      c
					RotateR(parent);
					RotateL(grandfather);

					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
	}
	_root->_col = BLACK;
	return true;
}

代码解释：

  • 向红黑树中插入一个key-value，如果是空树插入，则直接根据kv来new一个节点，然后赋值给_root，记得将根节点的颜色置为黑；
  • 如果是非空树的插入，首先利用cur指针找到kv应该插入的位置，在此过程中也需要一个parent来记录cur的父亲，找到位置后，new节点赋值给cur，置节点颜色为红，这个时候还不能直接链接cur与parent，得先判断插入parent的左边还是右边，插入后记得修改cur的_parent指针。
  • 接着就该判断插入节点cur与parent的颜色有没有发生冲突，如果parent的颜色是红色，那么就需要进行处理，可以说处理颜色冲突是红黑树插入的最重要操作。
  • 首先得用grandfather来记录parent的父亲，然后得判断parent是grandfather的左节点还是右节点从而知道uncle节点的具体位置，这里就假设parent是grandfather的左节点，那么uncle就是右节点，由于uncle是左节点的情况是相对的，所以我们只需要讨论一种情况即可。
  • 若uncle存在且为红，那么将parent和uncle的颜色置黑，grandfather的颜色置红，然后将cur移动到grandfather，重新记录parent，继续向上更新颜色。
  • 继续更新颜色导致了uncle存在或者uncle存在且为黑的情况，分场景触发单旋+变色或双旋+变色，如果cur是parent的左节点就是parent和cur相较于grandfather偏向左边，左单旋+变色处理；cur是右边，左右双旋+变色。
  • 注意触发单旋+变色或双旋+变色后，cur已经变成parent和grandfather的父亲了，记得break出循环，因为这时候以cur为根节点的子树已经是合法的红黑树，继续向上循环的话，cur就会变色了，你的处理就白忙活了。

红黑树的查找

跟二叉搜索树一样，不过多叙述。

Node* Find(const K& key)
{
	Node* cur = _root;

	while (cur)
	{
		if (key > cur->_kv.first)
			cur = cur->_right;
		else if (key < cur->_kv.first)
			cur = cur->_left;
		else
			return cur;
	}

	return nullptr;
}

红黑树的验证

对于红黑树的验证，只需要验证4条颜色规则就行了，这样就保证了最长路径1不超过最短路径的2倍。

  • 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
  • 规则2根节点是否为黑色直接检查根即可
  • 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不⼀定存在，反过来检查父亲的颜色是否为红就方便多了。
  • 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum（黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了⼀条路径的黑色结点数量。将其作为任意⼀条路径黑色结点数量的参考值，依次比较即可。
bool Check(Node* root, int blackNum, int refNum)
{
	if (root == nullptr)
	{
		//检查是否与参考值相等
		if (refNum != blackNum)
		{
			cout << "存在黑色结点的数量不相等的路径" << endl;
			return false;
		}
		return true;
	}

	//出现连续的红色节点返回false
	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << root->_kv.first << "存在连续的红色结点" << endl;
		return false;
	}

	//遇到黑色节点，blackNum++
	if (root->_col == BLACK)
		blackNum++;
	
	return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

bool IsRBTree()
{
	//空树也是REBTree
	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);
}

红黑树的测试

void test_RBTree1()
{
	RBTree<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.IsRBTree() << endl;
}

随机数测试

void test_RBTree2()
{
	srand((unsigned int)time(0));
	int N = 10000000;
	vector<int> v(N);
	v.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		v.push_back(rand() + i);
	}

	size_t begin = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert({ e, e });
	}
	size_t end = clock();
	cout << "Insert: " << end - begin << "ms" << endl;
	cout << t.IsRBTree() << endl;
}

 拜拜，下期再见😏

摸鱼ing😴✨🎞


http://www.kler.cn/a/384596.html

相关文章：

  • 爬虫-------字体反爬
  • Kafka 源码 KRaft 模式本地运行
  • 道可云人工智能元宇宙每日资讯｜2024国际虚拟现实创新大会将在青岛举办
  • 删除的域名购买还能使用嘛？
  • Zabbix监控架构
  • 分布式和微服务的区别
  • SpringMVC学习记录（二）之接收数据
  • 【JS】字符串方法速览
  • Android——网络请求
  • 大模型落地场景及价值思考
  • ubuntu 20.04 安装使用 nvidia gdrcopy
  • 使用Matlab神经网络工具箱
  • 智能化运维的未来：AI和机器学习在运维中的应用
  • 内网学习一：windows基础
  • Python进程管理：创建和协调多进程的深入指南
  • 远翔升压恒流芯片FP7209X与FP7209M什么区别？做以下应用市场摄影补光灯、便携灯、智能家居（调光）市场、太阳能、车灯、洗墙灯、舞台灯必看！
  • Hive 操作基础（进阶篇☝️）
  • Spring框架之单例模式 (Singleton Pattern)
  • Java对象、类、接口——针对实习面试
  • 探索Python视频处理的瑞士军刀：ffmpeg-python库
  • 在JS中, 0 == [0] 吗
  • 5g通信系统用到的crc码
  • 解析Eureka的架构
  • 996引擎 - 活捉NPC
  • 如何开发查找附近地点的微信小程序
  • 书生实战营第四期-基础岛第三关-浦语提示词工程实践