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

详解红黑树【C++实现】

news 来源：原创 2024/5/2 12:11:38

前言

之前介绍的AVL树由于严格要求左右子树高度差不能＞1，因此这势必导致需要经过许多次的旋转，导致效率降低。
而红黑树通过巧妙的设计，能有效避免多次旋转也能达到平衡。
维基百科的介绍

概念

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

也就是最长路径不超过最短路径2倍。

在这里插入图片描述

性质

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

满足上述性质，就能保证红黑树的最长路径不超过最短路径2倍。
最短：全黑。
最长：一黑一红间隔。
由于要保证每条路径的黑色节点数量相等，又最长的是一黑一红间隔，因此最长节点数量最多就是最短的2倍。

红黑树节点

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)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

在节点的定义中，为什么要将节点的默认颜色给成红色的？
这跟新增节点新增红色的一样。👇

插入

新增节点，新增黑色还是红色？
1、新增红色，可能破坏规则3
2、新增黑色，一定破坏规则4，并且规则4很难维护。

二叉搜索树

红黑树是在二叉搜索树的基础上加上其平衡限制条件而产生的。
因此，第一步是按照二叉搜索树的规则插入新节点。

template<class K, class V>
struct RBTree
{
	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* 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; // 插入黑色一定会破坏规则4，而且规则4很难维护
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else
			parent->_left = cur;
		cur->_parent = parent;
		// 红黑树处理 ...
		
		_root->_col = BLACK; // 最后要确保根节点为黑色
		return true;
	}

private:
	Node* _root = nullptr;
};

检测是否破坏红黑树

第二步，检测新插入节点是否破坏红黑树性质。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论。
约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一

cur为红，p为红，g为黑，u存在且为红。
解决方式：将p、u改为黑，g改为红，然后把g当成cur，继续向上调整。
在这里插入图片描述

情况二(单旋)

cur为红，p为红，g为黑，u不存在或者u存在且为黑。
解决方式：单旋加变色

在这里插入图片描述

情况三(双旋)

cur为红，p为红，g为黑，u不存在/u存在且为黑。
其实就是形成了g p cur 的折线，针对折线，我们在AVL树中也处理过了，其实就是2次单旋。
需要注意的是：
情况二和情况三旋转+变色之后，这颗子树已经不违反红黑树规则了，并且相比新增节点前，黑色节点数量不变，也就是不影响上层。
在这里插入图片描述

上述3种情况都是考虑 parent 是在 grandfather 左边的情况，右边的情况也是类似的。

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; // 插入黑色一定会破坏规则4，而且规则4很难维护
	if (parent->_kv.first < kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;
	cur->_parent = parent;
	// 红黑树处理 ...
	while (parent != nullptr && parent->_col == RED) // 存在连续红色节点
	{
		Node* grandFather = parent->_parent;
		if (parent == grandFather->_left)
		{
			Node* uncle = grandFather->_right;

			if (uncle && uncle->_col == RED) // 情况一 存在且为红
			{
				parent->_col = uncle->_col = BLACK; // 变色
				grandFather->_col = RED;
				cur = grandFather; // 继续向上处理
				parent = cur->_parent;
			}
			else // uncle 不存在或者 存在且为黑  旋转处理
			{
				if (cur == parent->_left) // 单旋
				{
					//     g
					//   p
					// c
					RotateR(grandFather);
					parent->_col = BLACK;
					grandFather->_col = RED;
				}
				else // 双旋
				{
					//     g
					//   p
					//     c
					RotateL(parent);
					RotateR(grandFather);
					cur->_col = BLACK;
					grandFather->_col = RED;
				}
				break; // 旋转完成不需要再处理了
			}
		}
		else // parent == grandFather->_right
		{
			Node* uncle = grandFather->_left;

			if (uncle && uncle->_col == RED) // 情况一 存在且为红
			{
				parent->_col = uncle->_col = BLACK; // 变色
				grandFather->_col = RED;
				cur = grandFather; // 继续向上处理
				parent = cur->_parent;
			}
			else // uncle 不存在或者 存在且为黑  旋转处理
			{
				if (cur == parent->_right) // 单旋
				{
					// g
					//   p
					//     c
					RotateL(grandFather);
					parent->_col = BLACK;
					grandFather->_col = RED;
				}
				else // 双旋
				{
					// g
					//   p
					// c
					RotateR(parent);
					RotateL(grandFather);
					cur->_col = BLACK;
					grandFather->_col = RED;
				}
				break; // 旋转完成不需要再处理了
			}
		}
	}
	_root->_col = BLACK; // 最后要确保根节点为黑色
	return true;
}

判断是否为红黑树

bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
	// 走到null之后，判断k和black是否相等
	if (nullptr == pRoot)
	{
		if (k != blackCount)
		{
			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
			return false;
		}
		return true;
	}

	// 统计黑色节点的个数
	if (BLACK == pRoot->_col)
		++k;

	// 检测当前节点与其双亲是否都为红色
	if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
	{
		cout << "违反性质三：存在连在一起的红色节点" << endl;
		return false;
	}

	return _IsValidRBTree(pRoot->_left, k, blackCount) &&
		_IsValidRBTree(pRoot->_right, k, blackCount);
}
bool IsValidRBTree() // 检查当前红黑树是否满足红黑树的几条规则
{
	// 空树也是红黑树
	if (nullptr == _root)
		return true;

	// 检测根节点是否满足情况
	if (BLACK != _root->_col)
	{
		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
		return false;
	}

	// 获取任意一条路径中黑色节点的个数 -- 作为比较的基准值
	size_t blackCount = 0;
	Node* pCur = _root;
	while (pCur)
	{
		if (BLACK == pCur->_col)
			blackCount++;

		pCur = pCur->_left; // 取最左路径黑色节点个数作为基准值
	}

	// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
	size_t k = 0;
	return _IsValidRBTree(_root, k, blackCount);
}

求高度

void Height()
{
	cout << "最长路径:" << _maxHeight(_root) << endl;
	cout << "最短路径:" << _minHeight(_root) << endl;
}
int _maxHeight(Node* root)
{
	if (root == nullptr)
		return 0;
	int lh = _maxHeight(root->_left);
	int rh = _maxHeight(root->_right);
	return lh > rh ? lh + 1 : rh + 1;
}

int _minHeight(Node* root)
{
	if (root == nullptr)
		return 0;
	int lh = _minHeight(root->_left);
	int rh = _minHeight(root->_right);
	return lh < rh ? lh + 1 : rh + 1;
}

测试

void TestRBTree1()
{
	//int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
	int a[] = { 30, 29, 28, 27, 26, 25, 24, 11, 8, 7, 6, 5, 4, 3, 2, 1 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.levelOrder();
	t.InOrder();
	t.Height();
}

在这里插入图片描述

void TestRBTree2()
{
	const size_t N = 1024 * 1024;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand());
		v.push_back(i);
	}

	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}

	//t.levelOrder();
	//cout << endl;
	cout << "是否平衡?" << t.IsValidRBTree() << endl;
	t.Height();

	//t.InOrder();
}

在这里插入图片描述

AVL&红黑树比较

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

尾声

🌹🌹🌹

写文不易，如果有帮助烦请点个赞~ 👍👍👍

Thanks♪(･ω･)ﾉ🌹🌹🌹

😘😘😘

👀👀由于笔者水平有限，在今后的博文中难免会出现错误之处，本人非常希望您如果发现错误，恳请留言批评斧正，希望和大家一起学习，一起进步ヽ(￣ω￣(￣ω￣〃)ゝ，期待您的留言评论。
附GitHub仓库链接

相关文章：

  • Flask的一些简单代码
  • 链路追踪 - SkyWalking
  • 基于NFS共享存储实现KVM虚拟主机动态迁移
  • MySQL之常用存储引擎
  • 动手学习深度学习 02：预备知识
  • dockerkubernets篇（二十六）
  • 9.synchronized的三把锁
  • 为什么开发人员正在成为供应链攻击中的最薄弱环节
  • MySQL之事务、锁
  • 项目第二天
  • Windows与网络基础-10-windows用户管理
  • 计算机网络笔记（王道考研） 第三章：数据链路层
  • apifox 提取cookie字段添加自动鉴权
  • ATF启动（一）：整体启动流程
  • 25. Python 字符串的切片方法
  • JS中 map, filter, some, every, forEach, for in, for of 用法总结
  • 0基础学习移动端适配
  • Apache的基本使用
  • ES6简单总结（搭配简单的讲解和小案例）
  • hadoop集群管理系统搭建规划说明
  • Java 最常见的 200+ 面试题：面试必备
  • java多线程
  • js继承的实现方法
  • 阿里云爬虫风险管理产品商业化，为云端流量保驾护航
  • 面试总结JavaScript篇
  • 你不可错过的前端面试题（一）
  • 前端每日实战 2018 年 7 月份项目汇总（共 29 个项目）
  • 浅谈JavaScript的面向对象和它的封装、继承、多态
  • 使用Maven插件构建SpringBoot项目,生成Docker镜像push到DockerHub上
  • 要让cordova项目适配iphoneX + ios11.4，总共要几步？三步
  • 一加3T解锁OEM、刷入TWRP、第三方ROM以及ROOT
  • 转载：[译] 内容加速黑科技趣谈
  • （8）STL算法之替换
  • （9）YOLO-Pose:使用对象关键点相似性损失增强多人姿态估计的增强版YOLO
  • (强烈推荐)移动端音视频从零到上手（下）
  • （四）汇编语言——简单程序
  • (原創) 系統分析和系統設計有什麼差別? (OO)
  • .locked1、locked勒索病毒解密方法|勒索病毒解决|勒索病毒恢复|数据库修复
  • .net core MVC 通过 Filters 过滤器拦截请求及响应内容
  • .NET Framework杂记
  • .NET 读取 JSON格式的数据
  • .NET/C# 编译期能确定的字符串会在字符串暂存池中不会被 GC 垃圾回收掉
  • .NET/C# 在 64 位进程中读取 32 位进程重定向后的注册表
  • .net分布式压力测试工具(Beetle.DT)
  • .NET开源快速、强大、免费的电子表格组件
  • .NET企业级应用架构设计系列之技术选型
  • .net生成的类，跨工程调用显示注释
  • @property python知乎_Python3基础之：property
  • [145] 二叉树的后序遍历 js
  • [ANT] 项目中应用ANT
  • [C# WPF] DataGrid选中行或选中单元格的背景和字体颜色修改
  • [CTO札记]如何测试用户接受度？
  • [GDMEC-无人机遥感研究小组]无人机遥感小组-000-数据集制备
  • [HackMyVM]靶场 Wild
  • [HTML]Web前端开发技术28（HTML5、CSS3、JavaScript ）JavaScript基础——喵喵画网页