[数据结构]红黑树的原理及其实现

文章目录

  • 红黑树的特性
  • 红黑树的时间复杂度
    • 推导：
    • 结论
    • 红黑树与AVL树比较
  • 红黑树的插入
    • 红黑树的节点定义
    • 调整策略
      • 思考情况2：
      • 思考情况3：
  • 代码实现
    • myBTRee.h
    • test.cpp

红黑树的特性

红黑树最常用的平衡二叉搜索树。跟AVL树不同的是，红黑树是依靠节点的颜色来维护平衡的。虽然任意节点不具备严格平衡，但是数据的查找、插入、删除等操作效率依旧出色。下面是红黑树的一些特性：

  1. 每个节点的颜色要么是红色要么是黑色
  2. 根节点的颜色是黑色
  3. 如果一个节点的颜色是红色的，那么它的两个孩子节点的颜色一定是黑色的
  4. 任意节点到其所能到达的叶子节点之间的黑色节点的数量相同
  5. 叶节点是黑色的空节点

根据以上红黑树的特性，我们可以总结出以下结论：

结论：红黑树中最长路径的节点数量不超过最短路径节点数量的2倍
证明：假设每条路径黑色节点的数量为n（假设不包括空叶子节点），则红色节点的数量最多是n。任意路径节点数量最少为n（只有黑节点），最多为2*n。

这样一来，任意一条路径的长度之差都保证在了一个有限的范围内，这也是红黑树具有平衡性的原因。

红黑树的时间复杂度

由于红黑树底层还是一颗二叉搜索树，根据二叉搜索树的特性：查找的效率取决于树的高度。

推导：

现假设红黑树的某一路径黑色节点数量为bh。由于任意路径黑色节点数目相同，我们可以把路径上所有的红色节点删除，将删除节点的父节点和其子节点相连，于是我们得到了一颗纯黑色节点的树（四叉树），如下图：
在这里插入图片描述
（该图截自b站动画讲编程）
这颗黑树的高度显然就是bh,且我们可以得到之前红黑树的节点数最少为2^bh-1（最少就是全是黑色）。假设这棵红黑树的节点总数为N,则N>=2^bh-1,两边取对数得bh<=log(N+1)(以2为底)。

设h为红黑树得最大高度，则有h=2*hb=2log(N+1)(最长路径节点数是2*bh)

结论

红黑树的高度最大为2log(N+1)，N表示树的节点总数。这个证明基于红黑树的性质。
得到了节点数与树的高度的关系，我们也就能得到红黑树查找数据的效率为O(logN)。此外，红黑树的插入效率和删除效率取决于查找效率，也是O(logN)。

红黑树与AVL树比较

相对来说，红黑树的内部实现细节没有AVL树这么复杂，虽然AVL树保证具备严格平衡性，但是其插入元素时调整平衡的操作相对也就繁琐。插入和删除的时候，AVL树可能会进行更多的旋转操作来维持平衡，导致实际的执行时间可能高于红黑树。

总的来说，红黑树适用于读写均衡的场景，插入和删除操作较为高效。而AVL树适用于查询频繁的场景，查询效率更高，但是插入和删除的维护成本较高。即使是这样，两者的差别依旧不大，查找、删除、插入的时间复杂度都是OlogN。

红黑树的插入

上面我们已经了解了红黑树的特性，接下来谈谈红黑树插入数据时是如何维护上述特性的。

红黑树的节点定义

与AVL实现类似，红黑树的节点依旧有三个指针分别指向父节点、左孩子节点、右孩子节点。且有一个变量表示当前节点的颜色。初始默认是红色。为什么默认设置为红色呢？这是因为插入节点时，新节点一定与空叶子节点相邻。而根据红黑树的性质，空叶子节点的颜色是黑色，这就使得，如果新插入节点是黑色，那么每插入一次这条路径就一定会多出来一个黑色节点，即一定要调整。虽然新节点是红色也可能会需要调整，但影响会少很多。

template<class K,class V>
struct RBTreeNode {
	RBTreeNode<T, V>* _parent;
	RBTreeNode<T, V>* _left;
	RBTreeNode<T, V>* _right;
	pair<K, V> _kv;//键值对

	Colour _col;//颜色

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

	}
};

调整策略

如果新插入一个节点，破坏了红黑树的性质，那么我们需要进行调整。具体需要调整的情况如下：

  1. 如果插入节点是根节点：那么只需要将根节点变黑
  2. 插入节点的叔叔节点是红色：父亲节点和叔叔节点变成黑色，爷爷变成红色，且爷爷节点变成新插入节点
  3. 插入节点的叔叔节点是黑色（为空也是黑色）：需要先旋转，然后变色

上述2，3情况一定是出现两个相邻节点是红色。

思考情况2：

为什么我们要把父亲节点和叔叔节点变成黑色，爷爷变成红色，且爷爷节点变成新插入节点？为什么这样做一定能维护红黑树的性质呢？
在这里插入图片描述

  • 首先，把父亲节点变黑是因为相邻两个节点是红色，那为什么要把叔叔节点也变色呢？
    这是因为新节点插入的这条路径可能会多一个黑色节点。为了让所有路径黑色节点数都能加一，每次调节父节点颜色的同时，也要调节叔叔节点颜色。这样一来，即使最后新节点插入的这条路径黑色节点数加一，其它所有路径的黑色节点也能同步加一。

  • 其实将爷爷节点变色也是为了维护所有路径黑色节点数一致这一特性。
    设想我们不将爷爷节点变成红色，此时整个红黑树确实没有出现“相邻的红色节点”，但是经过爷爷节点的路径的黑色节点数目就会比其它路径黑色节点数目多（parent和uncle都是变黑了）。除非此时爷爷节点是根节点（所有路径都经过根节点）。所以我们选择继续向上调整，把爷爷节点变成红色，并更新cur指针指向grandparent节点，看是否还会出现“红红”的俩节点。把爷爷节点变红是基于贪心思路：先不让路径的黑色节点数加一试试能不能平衡。

在这里插入图片描述

什么时候停止调整呢？父节点的颜色是黑色为止。此时红黑树平衡。

思考情况3：

如果叔叔节点本来就是黑色的呢？（空节点也是黑色）此时无论如何调节叔叔节点颜色，都有可能使得其它路径（比如叔叔这条路径）黑色节点数少于当前新节点插入路径的黑色节点数。此时考虑旋转。旋转的方式和AVL树是一致的。
旋转一共有四种方式：左旋、右旋、左右双旋、右左双旋。
细分情况3，一共有以下四种情况：
1.cur是parent的左孩子，parent是grandparent的左孩子。
在这里插入图片描述
将grandparent节点右旋转，旋转之后parent顶替了原来的grandparent,并变成黑色。grandparent成为parent的右孩子，变成红色。
在这里插入图片描述
旋转是不会改变二叉搜索树的特性的。那么思考这样一个问题，旋转之后还是平衡的红黑树吗？答案是–是的。因为我们观察旋转之后经过parent的所有路径的黑色节点数压根就没有变。

2.cur是parent的右孩子，parent是grandparent的右孩子
这种情况和情况1一样，只不过方向相反，是左旋。不做过多徐述。
在这里插入图片描述
3.cur是parent的右孩子，parent是grandparent的左孩子

此时这种情况对grandparent节点进行左单旋还是右单旋都不能保证红黑树平衡，于是考虑双旋，即旋转两次。
在这里插入图片描述
先对parent节点左旋，发现左旋之后就变成了情况1
在这里插入图片描述
此时我们就可以像情况1一样，对grandparent进行右旋，对cur节点和grandparent节点进行变色。
在这里插入图片描述
这样红黑树就平衡了，整个过程并没有增加路径的黑色节点的数量，因此也就不需要继续向上调整。

  1. cur是parent的左孩子，parent是grandparent的右孩子
    思路跟情况3一致，只不过旋转方向相反。向对parent节点进行右旋，再对grandparent节点进行左旋，再对cur和grandparent节点进行变色。

在这里插入图片描述

代码实现

myBTRee.h

封装了红黑树的类模板，包括各种功能的声明于定义

#pragma once

#include<vector>
#include<iostream>
using namespace std;

enum Colour{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode {
	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	pair<K, V> _kv;//键值对

	Colour _col;//颜色

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

	}
};

template<class K,class V>
class RBTree {
	typedef RBTreeNode<K, V> Node;
	typedef Node* pNode;
public:
	bool Insert(const pair<K, V>& kv) {
		if (_root == nullptr) {
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		//找到一个合适的插入位置
		pNode cur = _root;
		pNode parent = nullptr;
		while (cur) {
			if (cur->_kv.first > kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else {
				return false;
			}
		}
		//此时cur为nullptr
		cur = new Node(kv);
		if (cur->_kv.first < parent->_kv.first) {//插入节点
			parent->_left = cur;
			cur->_parent = parent;
		}
		else {
			parent->_right = cur;
			cur->_parent = parent;
		}

		//插入之后需要调节颜色平衡

		while (parent && parent->_col == RED) {
			//找叔叔节点
			pNode grandparent = parent->_parent;//祖父节点一定不为空，因为父节点为红色
			if (parent == grandparent->_left) {//如果叔叔在右边
				pNode uncle = grandparent->_right;
				//叔叔存在且为红，直接都变成黑色
				if (uncle && uncle->_col == RED) {
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续往上处理
					cur = grandparent;//cur往上跳两个节点
					parent = cur->_parent;
				}//叔叔节点不存在或者为黑色
				else {
					if (cur == parent->_left) {
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else if (cur == parent->_right) {
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}
		    //如果叔叔在左边
			if (parent == grandparent->_right) {
				pNode uncle = grandparent->_left;
				//叔叔存在且为红，直接都变成黑色
				if (uncle && uncle->_col == RED) {
					parent->_col = BLACK;
					uncle->_col = BLACK;

					//继续往上处理
					grandparent->_col = RED;
					cur = grandparent;//cur往上跳两个节点
					parent = cur->_parent;
				}//叔叔节点不存在或者为黑色
				else {
					if (cur == parent->_left) {
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col= RED;
					}
					else if (cur == parent->_right) {
						RotateL(grandparent);
						parent->_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;

		subL->_right = parent;

		Node* ppNode = parent->_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 RotateL(Node* parent)//左旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent= nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode;
		}
	}
	bool IsBalance() {
		if (_root->_col == RED)return false;

		int targetnum = 0;
		pNode cur = _root;
		while (cur) {
			if (cur->_col == BLACK)targetnum++;
			cur = cur->_left;
		}
		return _Check(_root, targetnum, 0);
	}
	void InOrder() {
		_InOrder(_root);
	}
private:

	bool _Check(pNode root,int targetnum,int blacknum) {
		if (root == nullptr) {
			if (blacknum != targetnum) {//路径的黑色节点数不相等
				return false;
			}
			else return true;
		}
		if (root->_left && root->_col == RED && root->_left->_col == RED)return false;
		if (root->_right && root->_col == RED && root->_right->_col == RED)return false;
		
		if (root->_col == BLACK)blacknum++;

		return _Check(root->_left,targetnum,blacknum) && _Check(root->_right,targetnum,blacknum);
	}

	void _InOrder(pNode root) {
		if (root == nullptr) {
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << " " << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	pNode _root=nullptr;

};

test.cpp

用于测试代码的正确性。给出一组随机数，插入到红黑树中之后进行平衡检查。平衡检查内容为，检查是否出现连个相邻的红色节点，且所有路径的黑节点·数目是否相等。
代码：

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

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

	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << t.IsBalance() << endl;
}

在这里插入图片描述

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

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

相关文章

基于springboot+vue+Mysql的交流互动系统

基于springboot+vue+Mysql的交流互动系统

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…
阅读更多...
【RAG 论文】IRCoT：基于 CoT 的交叉检索解决多步骤问题

【RAG 论文】IRCoT：基于 CoT 的交叉检索解决多步骤问题

论文&#xff1a;Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions ⭐⭐⭐⭐ ACL 2023, arXiv:2212.10509 Code: github.com/stonybrooknlp/ircot 论文速读 大多数 RAG 都是一次检索来辅助 LLM 生成&#xff0c;但是面对…
阅读更多...
品鉴中的艺术审美：如何将红酒品鉴提升为一种艺术体验

品鉴中的艺术审美：如何将红酒品鉴提升为一种艺术体验

品鉴云仓酒庄雷盛红酒不仅仅是对酒本身的体验&#xff0c;更是一种艺术和审美的过程。将品鉴提升为一种艺术体验&#xff0c;需要我们用更细腻的感官、情感和认知去感受葡萄酒的魅力。 首先&#xff0c;我们要意识到品鉴葡萄酒是一种多感官的体验。除了基本的视觉、嗅觉和味觉…
阅读更多...
利用管道通信(pipe)测量进程间的上下文切换(context switch)开销

利用管道通信(pipe)测量进程间的上下文切换(context switch)开销

利用管道通信(pipe)测量进程间的上下文切换(context switch)开销 《https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-mechanisms.pdf》 Measuring the cost of a context switch is a little trickier. The lmbench benchmark does so by running two processes on a single CPU…
阅读更多...
Vditor集成于VUE笔记

Vditor集成于VUE笔记

文章目录 前言一、安装Vditor二、渲染markdown三、options3.1 自建CDN3.2 outline大纲不显示、不跳转问题3.3 upload 图片/视频上传3.4 toolbar提示位置点击事件more中文字 3.5 sv分屏渲染模式隐藏编辑框3.6 after中的insertValue或者setValue 前言 Vditor是一款易于使用的 Ma…
阅读更多...
3D Web轻量化引擎HOOPS Communicator如何处理DWG文件中的图纸？

3D Web轻量化引擎HOOPS Communicator如何处理DWG文件中的图纸？

在当今工程设计和建筑领域&#xff0c;数字化技术已经成为不可或缺的一部分。HOOPS Communicator作为一种强大的三维数据可视化工具&#xff0c;被广泛应用于处理各种CAD文件&#xff0c;其中包括AutoCAD的DWG格式。在这篇文章中&#xff0c;我们将探讨HOOPS Communicator是如何…
阅读更多...
DRF 跨域问题

DRF 跨域问题

【一】说明 CORS&#xff08;跨来源资源共享&#xff0c;Cross-Origin Resource Sharing&#xff09;是一种浏览器技术的规范&#xff0c;旨在解决浏览器同源策略&#xff08;Same-Origin Policy&#xff09;的限制&#xff0c;使得Web服务可以从不同的网域&#xff08;源&…
阅读更多...
org.springframework.jdbc.BadSqlGrammarException

org.springframework.jdbc.BadSqlGrammarException

Cause: java.sql.SQLSyntaxErrorException: Table ‘web.emp’ doesn’t exist 产生原因&#xff1a;web表找不到&#xff0c;所以可能数据库配置错误 spring.datasource.urljdbc:mysql://localhost:3306/web02 更改完成后运行成功
阅读更多...
Web浏览器的兼容性测试需要考虑哪些测试点？

Web浏览器的兼容性测试需要考虑哪些测试点？

测试web网站兼容性时&#xff0c;可以使用各种测试用例来确保网站在不同浏览器中的良好兼容性。以下是一些常见的兼容性测试用例示例&#xff1a; 1. 页面加载测试&#xff1a; - 确保网站在不同浏览器中正常加载&#xff0c;没有加载错误。 - 检查页面加载时间&#xff0c;…
阅读更多...
场景文本检测识别学习 day09（SSM、S4、Mamba、S6）

场景文本检测识别学习 day09（SSM、S4、Mamba、S6）

SSM&#xff08;State Space Model&#xff09; SSM是一个针对连续函数的模型&#xff0c;即输入是连续函数&#xff0c;输出也是连续函数。上图为状态方程和输出方程&#xff0c;其中h(t)是当前时刻的状态&#xff0c;x(t)是当前时刻的输入&#xff0c;h’(t)是下一个时刻的状…
阅读更多...
应用TRIZ创新原理解决技术矛盾的步骤是什么样的？

应用TRIZ创新原理解决技术矛盾的步骤是什么样的？

如何在有限的时间和资源下&#xff0c;高效地解决技术矛盾&#xff0c;推动技术的进步和创新呢&#xff1f;答案就隐藏在TRIZ创新原理之中。 首先&#xff0c;我们需要了解什么是TRIZ创新原理。TRIZ&#xff0c;即发明问题解决理论&#xff0c;是一套系统的创新方法论&#xff…
阅读更多...
程序验证之Dafny--证明霍尔逻辑的半自动化利器

程序验证之Dafny--证明霍尔逻辑的半自动化利器

一、What is Dafny?【来自官网介绍 Dafny 】 1)介绍 Dafny 是一种支持验证的编程语言&#xff0c;配备了一个静态程序验证器。 通过将复杂的自动推理与熟悉的编程习语和工具相结合&#xff0c;使开发者能够编写可证明正确的代码&#xff08;相对于 {P}&#xff33;{Q} 这种…
阅读更多...
uniapp微信小程序通过萤石云接入海康摄像机

uniapp微信小程序通过萤石云接入海康摄像机

需求&#xff1a;在uniapp微信小程序上查看海康威视的摄像机监控视频和和操作摄像机拍摄方向 在萤石云接入海康摄像机设备&#xff0c;由于不同品牌设备在不同时间段接入方式可能不一致&#xff0c;具体接入方式查看官方文档或咨询官方客服。 海康摄像机官方客服热线&#xf…
阅读更多...
web学习笔记（五十五）

web学习笔记（五十五）

目录 1. 配置代码片段的步骤 2. 条件判断 2.1 v-if、v-else、v-else-if 2.2 v-show 2.3 v-show和v-if的区别 1. 配置代码片段的步骤 在Visual Studio Code中我们可以将常用的代码配置成代码片段&#xff0c;这样就可以在页面上快速输入大段代码了。 &#xff08;1&#…
阅读更多...
JavaScript-基本数据类型和变量

JavaScript-基本数据类型和变量

基本数据类型 JavaScript支持数字、字符串和布尔值3种基本数据类型 字符串型 字符串型是JavaScript用来表示文本的数据类型&#xff0c;字符串通常由单引号或双引号括起来&#xff0c;如果字符串存在特殊字符&#xff0c;可以用转义字符代替 数字型 数字型也是JavaScript中的基…
阅读更多...
pytest教程-46-钩子函数-pytest_sessionstart

pytest教程-46-钩子函数-pytest_sessionstart

领取资料&#xff0c;咨询答疑&#xff0c;请➕wei: June__Go 上一小节我们学习了pytest_report_testitemFinished钩子函数的使用方法&#xff0c;本小节我们讲解一下pytest_sessionstart钩子函数的使用方法。 pytest_sessionstart 是 Pytest 提供的一个钩子函数&#xff0c…
阅读更多...
U盘中毒文件变乱码？揭秘原因与高效恢复方法！

U盘中毒文件变乱码？揭秘原因与高效恢复方法！

在日常使用U盘的过程中&#xff0c;有时我们会遭遇到一个非常棘手的问题——文件突然出现乱码。当你满怀期待地插入U盘&#xff0c;准备打开某个重要文件时&#xff0c;却发现文件名或内容变成了一堆无法识别的字符&#xff0c;这种心情无异于晴天霹雳。乱码文件不仅影响了我们…
阅读更多...
数据结构------二叉树经典习题1

数据结构------二叉树经典习题1

博主主页: 码农派大星. 关注博主带你了解更多数据结构知识 1判断相同的树 OJ链接 这道题相对简单,运用我们常规的递归写法就能轻松写出 所以我们解题思路应该这样想: 1.如果p为空&#xff0c;q为空&#xff0c;那么就是两颗空树肯定相等 2.如果一个树为空另一棵树不为空那么…
阅读更多...
Android 应用开发-实现将公共存储空间内的文件复制到应用的私用存储空间中

Android 应用开发-实现将公共存储空间内的文件复制到应用的私用存储空间中

一、前言 几个月前&#xff0c;我用Android Studio给公司销售部门的同事开发了一款手机app&#xff0c;让同事们用自己的手机就能进行商品的扫码盘点操作&#xff0c;帮他们提高了工作效率&#xff0c;他们用了一段时间&#xff0c;反映还不错。不过前几天&#xff0c;销售部门…
阅读更多...
洗衣洗鞋店做小程序有什么优势？

洗衣洗鞋店做小程序有什么优势？

互联网洗衣洗鞋小程序闪亮登场&#xff0c;想知道这款小程序有何魅力吗&#xff1f; 如今&#xff0c;众多商家纷纷推出预约上门洗鞋服务&#xff0c;&#x1f481;‍♀️并倾力打造洗鞋小程序&#xff0c;旨在拓展线上销售渠道。&#x1f31f;那么&#xff0c;这款洗鞋小程序究…
阅读更多...
最新文章

Copyright @ 2022~2023