红黑树模拟实现

概念

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

下面就是一个红黑树： 

注：从根节点到NIL节点才是才算是一条路径。

性质

1.每个结点不是红色就是黑色

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

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

 通过上面的代码不难发现，我们将新创建的节点设置为红色，为什么不设置成黑色呢？

根据红黑树的性质4，我们知道，每条路径上黑色节点的数目是相等的，倘若我们在插入节点时，插入的是黑色节点，那么将影响整棵树；插入的是红色节点，不至于影响整棵树，因为如果新插入节点的父节点是黑色，将不需要进行调整；如果新插入节点的父节点是红色，只需要进行相关调整即可。

总的来说，新插入节点是红色，影响范围更小，利于编码实现，更方便。

红黑树的插入

1.按照二叉搜索树的规则插入节点；

2.判断红黑树的结构是否被破坏。

因为新节点的默认颜色是红色，因此：如果其父节点是黑色，就没有违反红黑树任何行者，则不需要调整；但当新插入节点的父节点是红色时，就违反了性质三（不能出现连续的红色节点），此时需要对红黑树分情况来讨论：

【约定】：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

情况一：cur为红，p为红，g为黑，u存在且为红

解决方式：将p，u改为黑，g改为红，然后把g改为cur，继续向上调整。

情况二：cur为红，p为红，g为黑，u不存在 / u存在且为黑

解决方式：p为g的左孩子，cur为p的左孩子，则进行右单旋，p改为黑色，g改为红色；

                  p为g的右孩子，cur为p的右孩子，则进行左单旋，p改为黑色，g改为红色。

此时u有两种情况：

1.u节点不存在，此时cur一定是新增节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色的，就不满足性质四（每条路径黑色节点个数相同）。

2.u节点存在，则其一定是黑色的.

情况三：cur为红，p为红，g为黑，u不存在 / u存在且为黑

解决方式：p为g的左孩子，cur为p的右孩子，则进行左单旋，再右单旋,  p改为黑色，g改为红色；

                  p为g的右孩子，cur为p的左孩子，则进行右单旋，再左单旋,  p改为黑色，g改为红色。

此时u有两种情况：

1.u节点不存在，此时cur一定是新增节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色的，就不满足性质四（每条路径黑色节点个数相同）。

2.u节点存在，则其一定是黑色的.

插入代码实现 

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;
	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_left = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			//     g
			//   p   u
			// c
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上更新处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				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
		{
			//     g
			//   u   p 
			//          c
			//
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_right)
				{
					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;
}
完整代码
#pragma once

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


template<class K, class V>
class 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;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				//     g
				//   p   u
				// c
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上更新处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					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
			{
				//     g
				//   u   p 
				//          c
				//
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						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;
	}

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

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

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

	// 根节点->当前节点这条路径的黑色节点的数量
	bool Check(Node* root, int blacknum, const int refVal)
	{
		if (root == nullptr)
		{
			//cout << balcknum << endl;
			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()
	{
		if (_root == nullptr)
			return true;

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

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

			cur = cur->_left;
		}

		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}

private:
	Node* _root = nullptr;
};

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

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

相关文章

昇思25天学习打卡营第20天|RNN实现情感分类

昇思25天学习打卡营第20天|RNN实现情感分类

数据准备 使用IMDB影评数据集&#xff0c;包含Positive和Negative两类。 数据下载 import os import shutil import requests import tempfile from tqdm import tqdm from typing import IO from pathlib import Path# 指定保存路径为 home_path/.mindspore_examples cache…
阅读更多...
蚓链实践告诉你“企业确保达成数字化营销效果的方法”

蚓链实践告诉你“企业确保达成数字化营销效果的方法”

在如今这个数字化盛行的时代&#xff0c;企业想在激烈的市场竞争里崭露头角&#xff0c;确保数字营销效果那可是至关重要&#xff01;今天就来给大家聊聊实现这一目标的基本条件&#xff0c;来自蚓链数字化营销系统的广大用户体验总结。 一、精准的目标定位 企业一定要清楚地知…
阅读更多...
第一作者讲述《生态系统架构：人工智能时代从业者的新思维》背后的故事：Episode One

第一作者讲述《生态系统架构：人工智能时代从业者的新思维》背后的故事：Episode One

当前&#xff0c;人工智能技术正不断渗透到各行各业&#xff0c;对企业和组织的系统和流程带来深刻的影响。生态系统架构可以帮助企业进行更好的规划和管理人工智能系统&#xff0c;使人工智能技术能够更好地为企业所用&#xff0c;从而实现企业的数字化转型和更好的商业表现。…
阅读更多...
信号量——Linux并发之魂

信号量——Linux并发之魂

欢迎来到 破晓的历程的 博客 引言 今天&#xff0c;我们继续学习Linux线程本分&#xff0c;在Linux条件变量中&#xff0c;我们对条件变量的做了详细的说明&#xff0c;今天我们要利用条件变量来引出我们的另一个话题——信号量内容的学习。 1.复习条件变量 在上一期博客中&…
阅读更多...
HTML5实现我的音乐网站源码

HTML5实现我的音乐网站源码

文章目录 作者&#xff1a;[xcLeigh](https://blog.csdn.net/weixin_43151418) 1.设计来源1.1 界面效果1.2 轮播图界面1.3 音乐播放界面1.4 视频播放界面 2.效果和源码2.1 动态效果2.2 源代码 源码下载万套模板&#xff0c;程序开发&#xff0c;在线开发&#xff0c;在线沟通 作…
阅读更多...
DAY22-力扣刷题

DAY22-力扣刷题

1.被围绕的区域 方法一&#xff1a;深度优先搜索 class Solution {int n, m;public void solve(char[][] board) {n board.length;if (n 0) {return;}m board[0].length;for (int i 0; i < n; i) {dfs(board, i, 0);dfs(board, i, m - 1);}for (int i 1; i < m - 1…
阅读更多...
项目方案：社会视频资源整合接入汇聚系统解决方案(九)-视频监控汇聚应用案例

项目方案：社会视频资源整合接入汇聚系统解决方案(九)-视频监控汇聚应用案例

目录 一、概述 1.1 应用背景 1.2 总体目标 1.3 设计原则 1.4 设计依据 1.5 术语解释 二、需求分析 2.1 政策分析 2.2 业务分析 2.3 系统需求 三、系统总体设计 3.1设计思路 3.2总体架构 3.3联网技术要求 四、视频整合及汇聚接入 4.1设计概述 4.2社会视频资源分…
阅读更多...
5.opencv深浅拷贝

5.opencv深浅拷贝

图像处理的复制操作 深浅拷贝 图像复制分成两种&#xff0c;第一种假复制&#xff0c;从原图片选择一部分图片拿出来观察&#xff0c;此时新生成的图片和原图实际上是同一张图片&#xff0c;即浅拷贝 将图片的一部分复制下来&#xff0c;放到新的内存中&#xff0c;即两张完全…
阅读更多...
AI视频教程下载-使用ChatGPT成为全栈JavaScript开发者

AI视频教程下载-使用ChatGPT成为全栈JavaScript开发者

学习使用Express JS和React JS进行全栈JavaScript开发 ChatGPT Express JS MongoDB React JS Tailwind 解锁全栈网页开发的世界&#xff0c;我们为初学者和中级学习者设计了全面的课程。在这段沉浸式的旅程中&#xff0c;你将深入前端和后端开发的基本概念&#xff0c;为自…
阅读更多...
【DataSophon】DataSophon1.2.1 ranger usersync整合

【DataSophon】DataSophon1.2.1 ranger usersync整合

目录 一、简介 二、实现步骤 2.1 ranger-usersync包下载编译 2.2 构建压缩包 2.3 编辑元数据文件 2.4 修改源码 三、重新安装 一、简介 如下是DDP1.2.1默认有的rangerAdmin&#xff0c; 我们需要将rangerusersync整合进来 ,实现将Linux机器上的用户和组信息同步到Ranger…
阅读更多...
【Linux】线程（轻量级进程）

【Linux】线程（轻量级进程）

目录 一、线程概念 二、线程特性 2.1 进程更加轻量化 2.2 线程的优点 2.3 线程的缺点 2.4 线程的异常 2.5 线程用途 三、进程和线程 四、线程控制 4.1 包含线程的编译链接 4.2 创建线程 4.3 获得线程自身的ID 4.4 线程终止 4.5 线程等待 4.6 线程分离 4.6 线程…
阅读更多...
Java数据结构9-排序

Java数据结构9-排序

1. 排序的概念及引用 1.1 排序的概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的记录…
阅读更多...
【Java】垃圾回收学习笔记（一）：Root Search 根可达算法+垃圾回收的起点

【Java】垃圾回收学习笔记（一）：Root Search 根可达算法+垃圾回收的起点

文章目录 1. 引用计数法优点缺点 2. 可达性分析 Root Search2.1 那些对象是GC Roots2.2 引用的分类2.3 回收方法区 3. 实现细节3.1 GC的起点&#xff1a;节点枚举OopMap&#xff1a;帮助高效的根节点枚举 3.2 何时开始GC&#xff1a;安全点与安全区域如何选取安全点如何让程序进…
阅读更多...
在mac下 Vue2和Vue3并存 全局Vue2环境创建Vue3新项目（Vue cli2和Vue cli4）

在mac下 Vue2和Vue3并存 全局Vue2环境创建Vue3新项目（Vue cli2和Vue cli4）

全局安装vue2 npm install vue-cli -g自行在任意位置创建一个文件夹vue3&#xff0c;局部安装vue3,注意不要带-g npm install vue/cli安装完成后&#xff0c;进入目录&#xff0c;修改vue为vue3 找到vue3/node-moudles/.bin/vue&#xff0c;把vue改成vue3。 对环境变量进行配置…
阅读更多...
web安全基础名词概念

web安全基础名词概念

本节内容根据小迪安全讲解制作 第一天 域名&#xff1a; 1.1什么是域名&#xff1f; 网域名称(英语&#xff1a;Domain Name&#xff0c;简称&#xff1a;Domain)&#xff0c;简称域名、网域&#xff0c;是由一串用点分隔的字符组成的互联网上某一台计算机或计算机组的名称&a…
阅读更多...
java核心-泛型

java核心-泛型

目录 概述什么是泛型分类泛型类泛型接口泛型方法 泛型通配符分类 泛型类型擦除分类无限制类型擦除有限制类型擦除 问题需求第一种第二种 概述 了解泛型有利于学习 jdk 、中间件的源码&#xff0c;提升代码抽象能力&#xff0c;封装通用性更强的组件。 什么是泛型 在定义类、接…
阅读更多...
存储过程编程-创建（CREATE PROCEDURE）、执行（EXEC）、删除（DROP PROCEDURE）

存储过程编程-创建（CREATE PROCEDURE）、执行（EXEC）、删除（DROP PROCEDURE）

一、定义 1、存储过程是在SQL服务器上存储的已经编译过的SQL语句组。 2、存储过程分为三类&#xff1a;系统提供的存储过程、用户定义的存储过程和扩展存储过程 &#xff08;1&#xff09;系统提供的存储过程&#xff1a;在安装SQL Server时&#xff0c;系统创建了很多系统存…
阅读更多...
Kafka（一）基础介绍

Kafka（一）基础介绍

一&#xff0c;Kafka集群 一个典型的 Kafka 体系架构包括若Producer、Broker、Consumer&#xff0c;以及一个ZooKeeper集群&#xff0c;如图所示。 ZooKeeper&#xff1a;Kafka负责集群元数据的管理、控制器的选举等操作的&#xff1b; Producer&#xff1a;将消息发送到Broker…
阅读更多...
MySQL事务隔离

MySQL事务隔离

MySQL事务隔离 前言锁共享锁&#xff08;Shared Lock&#xff09;排他锁&#xff08;Exclusive Lock&#xff09;行级锁&#xff08;Row-Level Lock&#xff09;表级锁&#xff08;Table-Level Lock&#xff09;快照读和当前读查看锁 事务事务的四个特性事务的并发问题事务的隔…
阅读更多...
Chrome 127内置AI大模型攻略

Chrome 127内置AI大模型攻略

Chrome 127 集成Gemini：本地AI功能 Google将Gemini大模型整合进Chrome浏览器，带来全新免费的本地AI体验： 完全免费、无限制使用支持离线运行，摆脱网络依赖功能涵盖图像识别、自然语言处理、智能推荐等中国大陆需要借助魔法，懂都懂。 安装部署步骤： 1. Chrome V127 dev …
阅读更多...
最新文章

Copyright @ 2022~2023