【C++ RB树】

文章目录

    • 红黑树
      • 红黑树的概念
      • 红黑树的性质
      • 红黑树节点的定义
      • 红黑树的插入
      • 代码实现
      • 总结

红黑树

AVL树是一颗绝对平衡的二叉搜索树，要求每个节点的左右高度差的绝对值不超过1，这样保证查询时的高效时间复杂度O( l o g 2 N ) log_2 N) log2​N)，但是要维护其绝对平衡，旋转的次数比较多。因此，如果一颗树的结构经常修改，那么AVL树就不太合适，所以就有了红黑树。

红黑树的概念

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

红黑树的性质

  1. 每个节点不是红色就是黑色
  2. 根节点是黑色的
  3. 不存在连续的红色节点
  4. 任意一条从根到叶子的路径上的黑色节点的数量相同
    根据上面的性质，红黑树就可以确保没有一条路径会比其他路径长出两倍，因为每条路径上的黑色节点的数量相同，所以理论上最短边一定都是黑色节点，最长边一定是一黑一红的不断重复的路径。

红黑树节点的定义

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

插入新节点的颜色一定是红色，因为如果新节点的颜色是黑色，那么每条路径上的黑色节点的数量就不相同了，处理起来就比较麻烦，所以宁愿出现连续的红色节点，也不能让某一条路径上多出一个黑色节点。

红黑树的插入

1.根据二叉搜索树的规则插入新节点

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* curr = _root;
	Node* parent = nullptr;
	while (curr)
	{
		if (curr->_kv.first < kv.first)
		{
			parent = curr;
			curr = curr->_right;
		}
		else if (curr->_kv.first > kv.first)
		{
			parent = curr;
			curr = curr->_left;
		}
		else
		{
			return false;
		}
	}
	curr = new Node(kv);
	if (parent->_kv.first < kv.first)
		parent->_right = curr;
	else
		parent->_left = curr;
	curr->_parent = parent;
........

2.测新节点插入后，红黑树的性质是否造到破坏

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* curr = _root;
	Node* parent = nullptr;
	while (curr)
	{
		if (curr->_kv.first < kv.first)
		{
			parent = curr;
			curr = curr->_right;
		}
		else if (curr->_kv.first > kv.first)
		{
			parent = curr;
			curr = curr->_left;
		}
		else
		{
			return false;
		}
	}
	curr = new Node(kv);
	if (parent->_kv.first < kv.first)
		parent->_right = curr;
	else
		parent->_left = curr;
	curr->_parent = parent;

	while (parent && 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;

				curr = grandfather;
				parent = curr->_parent;
			}
			else
			{
				if (curr == parent->_left)
				{
					//      g
					//   p     u
					//c
					RotatoR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//      g
					//   p     u
					//    c
					RotatoL(parent);
					RotatoR(grandfather);
					curr->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				curr = grandfather;
				parent = curr->_parent;
			}
			else
			{
				if (curr == parent->_right)
				{
					//      g   
					//   u     p
					//           c
					RotatoL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//      g   
					//   u     p
					//        c
					RotatoR(parent);
					RotatoL(grandfather);
					curr->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		
	}
	_root->_col = BLACK;
	return true;
}
void RotatoL(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;
		subR->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
			ppnode->_left = subR;
		else
			ppnode->_right = subR;
		subR->_parent = ppnode;
	}
}
void RotatoR(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;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
			ppnode->_left = subL;
		else
			ppnode->_right = subL;
		subL->_parent = ppnode;
	}
}

代码实现

#pragma once
#include <utility>

namespace lw
{
	enum Color
	{
		RED,
		BLACK
	};
	template<class K, class V>
	struct RBTreeNode
	{
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;
		Color _col;
		pair<K, V> _kv;
		RBTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_col(RED)
			,_kv(kv)
		{}
	};
	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* curr = _root;
			Node* parent = nullptr;
			while (curr)
			{
				if (curr->_kv.first < kv.first)
				{
					parent = curr;
					curr = curr->_right;
				}
				else if (curr->_kv.first > kv.first)
				{
					parent = curr;
					curr = curr->_left;
				}
				else
				{
					return false;
				}
			}
			curr = new Node(kv);
			if (parent->_kv.first < kv.first)
				parent->_right = curr;
			else
				parent->_left = curr;
			curr->_parent = parent;

			while (parent && 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;

						curr = grandfather;
						parent = curr->_parent;
					}
					else
					{
						if (curr == parent->_left)
						{
							//      g
							//   p     u
							//c
							RotatoR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else
						{
							//      g
							//   p     u
							//    c
							RotatoL(parent);
							RotatoR(grandfather);
							curr->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
				}
				else
				{
					Node* uncle = grandfather->_left;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;

						curr = grandfather;
						parent = curr->_parent;
					}
					else
					{
						if (curr == parent->_right)
						{
							//      g   
							//   u     p
							//           c
							RotatoL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else
						{
							//      g   
							//   u     p
							//        c
							RotatoR(parent);
							RotatoL(grandfather);
							curr->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
				}
				
			}
			_root->_col = BLACK;
			return true;
		}
		void RotatoL(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;
				subR->_parent = nullptr;
			}
			else
			{
				if (ppnode->_left == parent)
					ppnode->_left = subR;
				else
					ppnode->_right = subR;
				subR->_parent = ppnode;
			}
		}
		void RotatoR(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;
				subL->_parent = nullptr;
			}
			else
			{
				if (ppnode->_left == parent)
					ppnode->_left = subL;
				else
					ppnode->_right = subL;
				subL->_parent = ppnode;
			}
		}
		void InOrder()
		{
			_InOrder(_root);
		}
		bool IsBalance()
		{
			if (_root && _root->_col == RED)
				return false;
			Node* left = _root;
			int count = 0;
			while (left)
			{
				if (left->_col == BLACK)
					count++;
				left = left->_left;
			}
			return check(_root, 0, count);
		}
	private:
		bool check(Node* root, int count, int refBlackNumber)
		{
			if (root == nullptr)
			{
				if (count == refBlackNumber)
					return true;
				else
					return false;
			}
			if (root->_col == RED && root->_parent->_col == RED)
				return false;
			if (root->_col == BLACK)
				count++;
			return check(root->_left, count, refBlackNumber)
				&& check(root->_right, count, refBlackNumber);
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_kv.first << " : " << root->_kv.second << endl;
			_InOrder(root->_right);
		}
		Node* _root = nullptr;
	};
}

总结

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

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

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

相关文章

openwrt下部署clouddrive2

openwrt下部署clouddrive2

在启动项上增加启动参数 在exit 0前面增加 mount --make-shared /mnt/data480g注意&#xff0c;后面的/mnt/data480g要替换成你设置的共享映射券。 拉取镜像 docker pull cloudnas/clouddrive2启动镜像 一定要用ssh在后台用docker run命令启动&#xff0c;因为openwrt前台…
阅读更多...
Windows 安装配置 RabbitMQ 详解

Windows 安装配置 RabbitMQ 详解

目录 1、安装前准备2、安装Erlang2.1 安装2.2 配置环境变量 3、安装RabbitMQ3.1 安装3.2 配置环境变量3.3 安装rabbitmq_management插件3.4 启动RabbitMQ服务 4、常用命令 本文将详说如何在Windows系统中安装RabbitMQ。 1、安装前准备 因为RabbitMQ服务器是用Erlang语言编写的…
阅读更多...
AQY214S固态继电器：用于控制各种应用中的模拟信号的紧凑解决方案

AQY214S固态继电器：用于控制各种应用中的模拟信号的紧凑解决方案

AQY214S是一款多功能固态继电器&#xff0c;是一款经过精心设计的精致固态继电器&#xff0c;可在多种应用中与低电平模拟信号共舞。在这次探索中&#xff0c;我们将揭开AQY214S的复杂性&#xff0c;重点介绍其独特的功能&#xff0c;并深入研究其在不同行业中的应用的迷人挂毯…
阅读更多...
MySQL MHA故障切换

MySQL MHA故障切换

目录 一、案例分析 1.1、案例概述 1.2、案例前置知识点 1&#xff09;什么是 MHA 2&#xff09;MHA 的组成 3&#xff09;MHA 的优势 4&#xff09;MHA 现状 1.3、案例环境 1&#xff09;本案例环境 ​编辑 2&#xff09;案例需求 3&#xff09;案例实现思路…
阅读更多...
基于springboot的七彩云南文化旅游网站的设计与实现(论文+源码)_kaic

基于springboot的七彩云南文化旅游网站的设计与实现(论文+源码)_kaic

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装七彩云南文化旅游网站软件来发挥其高效地信息处理的作用&am…
阅读更多...
web学习笔记（三十三）

web学习笔记（三十三）

目录 1.严格模式 1.1严格模式的概念&#xff1a; 1.2严格模式在语义上更改的地方&#xff1a; 1.3如何开启严格模式 1.4严格模式应用上的变化 2.原型链 1.严格模式 1.1严格模式的概念&#xff1a; 严格模式有点像es5向es6过渡而产生的一种模式&#xff0c;因为es6的语法…
阅读更多...
蓝桥杯决赛2023 RE CyberChef2

蓝桥杯决赛2023 RE CyberChef2

思路很清晰&#xff0c;爆IV 但是题目出的有点屎&#xff0c;六位字符串&#xff0c;62的6次方&#xff0c;要我爆到猴年马月&#xff1f; 就当练习脚本吧 #Cyber2 wp from Crypto.Cipher import DES, AES from Crypto.Util.Padding import pad, unpad key_des b0a0b0c0…
阅读更多...
从零开始利用MATLAB进行FPGA设计（三）将Simulink模型转化为定点数据类型

从零开始利用MATLAB进行FPGA设计（三）将Simulink模型转化为定点数据类型

文章灵感来源于MATLAB官方免费教程&#xff1a;HDL Coder Self-Guided Tutorial 考虑到MATLAB官网的英文看着慢&#xff0c;再加上视频讲解老印浓浓的咖喱味&#xff0c;我决定记录利用MATLAB&Simulink&SystemGenerator进行FPGA数字信号处理的学习过程。 往期回顾&am…
阅读更多...
【Miniconda】Linux系统中 .condarc 配置文件的位置一般在哪里

【Miniconda】Linux系统中 .condarc 配置文件的位置一般在哪里

【Miniconda】Linux系统中 .condarc 配置文件的位置一般在哪里 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448; 希望得到…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：Span）

鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：Span）

作为Text组件的子组件&#xff0c;用于显示行内文本的组件。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 该组件从API Version 10开始支持继承父组件Text的属性&#xff0c;即如果子组件未设置…
阅读更多...
linux内存介绍

linux内存介绍

一、linux内存框图 二、meminfo信息说明 cat /proc/meminfo MemTotal: 2017504 kB //所有可用的内存大小&#xff0c; 物理内存减去预留位和内核使用。系统从加电开始到引导完成&#xff0c;firmware/BIOS要预留一 些内存&#xff0c;内核本身要占用一些内存&#xff0…
阅读更多...
微信小程序云开发教程——墨刀原型工具入门（表单组件）

微信小程序云开发教程——墨刀原型工具入门（表单组件）

引言 作为一个小白&#xff0c;小北要怎么在短时间内快速学会微信小程序原型设计&#xff1f; “时间紧&#xff0c;任务重”&#xff0c;这意味着学习时必须把握微信小程序原型设计中的重点、难点&#xff0c;而非面面俱到。 要在短时间内理解、掌握一个工具的使用&#xf…
阅读更多...
16.旋转图像

16.旋转图像

给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&…
阅读更多...
【PyTorch】基础学习：在终端中打印当前虚拟环境下的Pytorch版本信息

【PyTorch】基础学习：在终端中打印当前虚拟环境下的Pytorch版本信息

【PyTorch】基础学习&#xff1a;在终端中打印或查看当前虚拟环境下的Pytorch版本信息 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程…
阅读更多...
springboot 动漫周边商城的设计与实现

springboot 动漫周边商城的设计与实现

摘 要 二十一世纪我们的社会进入了信息时代&#xff0c;信息管理系统的建立&#xff0c;大大提高了人们信息化水平。传统的管理方式对时间、地点的限制太多&#xff0c;而在线管理系统刚好能满足这些需求&#xff0c;在线管理系统突破了传统管理方式的局限性。于是本文针对这一…
阅读更多...
Selenium控制已运行的Edge和Chrome浏览器——在线控制 | 人机交互（详细启动步骤和bug记录）

Selenium控制已运行的Edge和Chrome浏览器——在线控制 | 人机交互（详细启动步骤和bug记录）

文章目录 前期准备1. 浏览器开启远程控制指令&#xff08;1&#xff09;Edge&#xff08;2&#xff09;Chrome 2. 执行python代码&#xff08;1&#xff09;先启动浏览器后执行代码&#xff08;2&#xff09;通过代码启动浏览器&#xff08;3&#xff09;Bug问题记录1&#xff…
阅读更多...
kubernetes部署集群

kubernetes部署集群

kubernetes部署集群 集群部署获取镜像安装docker[集群]阿里仓库下载[集群]集群部署[集群]集群环境配置[集群]关闭系统Swap[集群]安装Kubeadm包[集群]配置启动kubelet[集群]配置master节点[master]配置使用网络插件[master]node加入集群[node]后续检查[master]测试集群 集群部署…
阅读更多...
力扣面试150 两数之和 II - 输入有序数组 双指针 HashMap

力扣面试150 两数之和 II - 输入有序数组 双指针 HashMap

Problem: 167. 两数之和 II - 输入有序数组 复杂度 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code class Solution {public int[] twoSum(int[] numbers, int target) {int l 0;int r numbers.length-1;while(l < r){if(numbers[l] numbers[…
阅读更多...
Javaweb--CSS

Javaweb--CSS

一&#xff1a;概述 CSS &#xff08;Cascading Style Sheet&#xff08;层叠样式表&#xff09;&#xff09;是一门语言&#xff0c;用于控制网页表现。 W3C标准规定了网页是由以下组成&#xff1a; 结构&#xff1a;HTML 表现&#xff1a;CSS 行为&#xff1a;JavaScrip…
阅读更多...
git pull 报错: 在签出前，请清理存储库工作树

git pull 报错: 在签出前，请清理存储库工作树

问题&#xff1a; 使用vscode 用git 拉取代码&#xff0c;提示&#xff1a;在签出前&#xff0c;请清理存储库工作树** 原因&#xff1a; git仓库上的代码和本地代码存在冲突了所以会报这个报错。 解决办法&#xff1a; ①git stash 先将本地修改存储起来 ②git pull 拉取远…
阅读更多...
最新文章

Copyright @ 2022~2023