目录

一、红黑树概述

二、红黑树节点设计

  (1)枚举红黑

（2）红黑树的节点设计

三、红黑树核心实现:Insert

1.首先将节点遍历到对应位置创建对应节点并插入到二叉搜索树对应的位置

2.本文重点的重点

（1）parent为黑时直接插入即可

（2）uncle存在且为红

（3）uncle不存在

（4）uncle存在且为黑

四、红黑树检查代码

五、总代码

1.RBTree.h

2.Test.c代码

一、红黑树概述

学完AVL树之后对我来说，红黑树可能更容易理解，还有水了这么多篇，该认真写一篇了，哈哈哈哈。

红黑树顾名思义就是得有红色和黑色的树，红黑树利用红色和黑色节点来创建二叉平衡搜索树

红黑树的5条核心特点：

（1）每个节点是红色或黑色

（2）根节点必须是黑色

（3）所有叶子节点（NIL/空节点）是黑色（NIL节点是红黑树中所有空指针的替代节点，表示树的

叶子位置。）

（4）红色节点的子节点必须是黑色（即不能有连续的黑色节点）

（5）从任意节点到其所有叶子节点的路径上，黑色节点的数量相同

二、红黑树节点设计

  (1)枚举红黑

enum Colour
{RED,BLACK
};

（2）红黑树的节点设计

1.其中的三叉链是指_left _right _parent ,在我的理解中_left和_right是为了前进，而_parent是为了后退

2.kv是储存的值，set中储存的V是与K一样的类型，map中储存的是<const K ,V>

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

三、红黑树核心实现:Insert

二叉树的核心操作就是插入，插入分为三种情况:

（1）uncle存在且为红

（2）uncle不存在

（3）uncle存在且为黑

1.首先将节点遍历到对应位置创建对应节点并插入到二叉搜索树对应的位置

	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;}}//这里是创建一个初始化_kv(kv)的新节点，并别把颜色初始化为红色cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;

2.本文重点的重点

注：给出的图画是以 parent == grandfather->_left 条件下进行的,panret==grandfather->_right同理，最后有完整代码可参考

（1）parent为黑时直接插入即可

！！！下面都是parent为红的情况

（2）uncle存在且为红

在parent和uncle为红的情况我们，让我们grandfatehr变成红，让parent和uncle变成黑

然后让cur=grandfatehr ,parent=cur->_parent,grandfather=parent->_parent

继续向上处理：

（一） .grandfather没有父亲，就是根，grandfatehr变黑即可

（二）.grandfather有父亲，父亲时黑色，就结束了

（三）.grandfather有父亲，父亲是红色，和上面一样处理

继续像刚才一样的操作

因为grandfatehr 是根节点，因为根节点只能是红，最后让根节点的颜色变成红                  

最后有完整代码，现在给出对应部分代码

Node* uncle = grandfather->_right;
//uncle存在且为红
if (uncle && uncle->_col == RED)
{//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;//grandfather = parent->_parent; 
}
（3）uncle不存在

这里是grandfather->_left且parent是红色节点的前提，这里有两种情况

情况一：parent->_left=cur

在grandfather节点进行右旋，让grandfather的颜色变成红色，让parent的颜色变成黑色

情况二:parent->_right=cur

在parent节点进行左旋

再在grandfather哪里进行右旋

旋转完之后，grandfather的颜色变红，cur的颜色变黑

代码：

现在给出对应部分代码，左旋，右旋，左右旋，右左旋代码也在最后的完整代码中

else//uncle不存在或uncle存在且为黑
{//这是什么意思？这里我自己判断了if (cur == parent->_left ){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED; }break;
}
（4）uncle存在且为黑

这里是grandfather->_right且parent是红色节点的前提，与（3）的以grandfather->_left情况相反了

这种情况有点特殊，要操作一步才能得到

按照（2）变成，变成我们（4）所需要的状态

情况一：parent->_right=cur

然后对grandfather进行左旋

grandfather的颜色变红，parent的颜色变黑

情况二：parent->_left=cur

首先要在parent进行右旋操作

再对grandparent进行左旋，让grandfather的颜色变红，cur的颜色变黑

代码：

现在给出对应部分代码，左旋，右旋，左右旋，右左旋代码也在最后的完整代码中

if (cur == parent->_right)
{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;
}
else
{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED;
}
break;

四、红黑树检查代码

1.通过递归得出高度的代码

int Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

2.根据红节点的父亲是否是红色来判断红黑树是否有误

//为什么不是int & blacknum，因为要利用栈帧，保存当前形式下，blackanum的值
bool CheckColour(Node* root, int blacknum,int benchmark)
{if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent &&root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left,blacknum,benchmark)&& CheckColour(root->_right, blacknum, benchmark);
}

3.利用左边的那条支路创建黑高的基准值，再在checkcolour把所有节点黑高节点检查一遍得出结果

bool IsBalance()
{return IsBalance(_root);
}
bool IsBalance(Node* root)
{if (root == nullptr)return true;if (root->_col != BLACK)return false;
//	return CheckColour(root);//基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++benchmark;  }//这里是以最左路径为标准cur = cur->_left;}return  CheckColour(root, 0, benchmark);
}

五、总代码

1.RBTree.h

#pragma once
#include<iostream>
#include<stdio.h>
using namespace std;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>
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){//Node* parent = 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;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;while (parent&&parent->_col==RED){Node* grandfather = parent->_parent;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;//grandfather = parent->_parent; }else//uncle不存在或uncle存在且为黑{//这是什么意思？这里我自己判断了if (cur == parent->_left ){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED; }break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;//grandfather = parent->_parent;}else{//我觉得案按理来说得判断，这是叔叔不存在的情况？if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){//这是AVL树第一集的末尾了Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){//这是AVL树第一集的末尾了Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}Node* ppnode = parent->_parent;cur->_right = parent;//Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_right == parent){ppnode->_right = cur;}else{ppnode->_left = cur;}cur->_parent = ppnode;}}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;//int bf = cur->_left->_bf;RotateR(parent->_right);RotateL(parent);}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;//	int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}//为什么不是int & blacknum，因为要利用栈帧，保存当前形式下，blackanum的值bool CheckColour(Node* root, int blacknum,int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent &&root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left,blacknum,benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;//	return CheckColour(root);//基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++benchmark;  }//这里是以最左路径为标准cur = cur->_left;}return  CheckColour(root, 0, benchmark);}
private:Node* _root = nullptr;
};

2.Test.c代码

插入10000个随机数进行测试

#include"RBTree.h"
#include<vector>
#include<time.h>
//int main()
//{
//	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
//	RBTree<int, int> t;
//	for (auto e : a)
//	{
//		t.Insert(make_pair(e, e));
//		cout << "Insert:" << e << "->"<<t.IsBalance() << endl;
//	}
//	return 0;
//}int main()
{const int N = 10000;vector<int> v;v.reserve(N);srand(time(0));for (int i = 0;i < N;i++){v.push_back(rand());}RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));cout << "Insert:" << e << "->" << t.IsBalance() << endl;}return 0;
}

谢谢观众老爷的观看！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/89726.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/89726.shtml
英文地址，请注明出处：http://en.pswp.cn/web/89726.shtml

如若内容造成侵权/违法违规/事实不符，请联系英文站点网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【黄山派-SF32LB52】—硬件原理图学习笔记

【黄山派-SF32LB52】—硬件原理图学习笔记

目录 一、硬件介绍 二、芯片主控 1.模组介绍 2.原理图介绍 3.模组供电电路 三、电源转换部分 1.OVP过压保护电路 2.CHG充电电路 3.系统电源桥接电路 4.LDO电路 四、Debug电路 1.一键下载电路 五、QSPI屏幕 六、SD卡 七、AUDIO音频 八、GPIO电路 1.按键部分…
阅读更多...
从五次方程到计算机：数学抽象如何塑造现代计算

从五次方程到计算机：数学抽象如何塑造现代计算

引言 数学的发展往往始于一个具体的问题&#xff0c;而后在寻求解答的过程中&#xff0c;催生出深刻的抽象理论。从五次方程的求解到抽象代数&#xff0c;再到范畴论和λ演算&#xff0c;最终影响图灵机和现代计算机的设计&#xff0c;这一历程展现了数学如何从实际问题演变为通…
阅读更多...
剧本杀小程序开发：科技赋能，重塑推理娱乐新形态

剧本杀小程序开发：科技赋能，重塑推理娱乐新形态

在科技飞速发展的今天&#xff0c;各个行业都在积极探索与科技的融合&#xff0c;以实现创新发展。剧本杀行业也不例外&#xff0c;剧本杀小程序的开发&#xff0c;正是科技赋能传统娱乐的生动体现&#xff0c;它重塑了推理娱乐的新形态&#xff0c;为玩家带来了前所未有的游戏…
阅读更多...
机器学习sklearn入门：归一化和标准化

机器学习sklearn入门：归一化和标准化

bg&#xff1a;归一化&#xff08;Normalization&#xff09;通常指将数据按比例缩放至某个特定范围&#xff0c;但具体范围并不一定是固定的 0到1。标准化是将数据转换成均值为0&#xff0c;标准差为1的分布。使用场景&#xff1a;用归一化&#xff1a;需要严格限定范围&#…
阅读更多...
【Project】kafka+flume+davinci广告点击实时分析系统

【Project】kafka+flume+davinci广告点击实时分析系统

一、项目需求分析 某电商平台需实现广告实时点击分析系统&#xff0c;核心需求为实时统计以下内容的Top10&#xff1a; 各个广告的点击量各个省份的广告点击量各个城市的广告点击量 通过实时掌握广告投放效果&#xff0c;为广告投放策略调整和大规模投入提供依据&#xff0c;以…
阅读更多...
JAVA后端开发——success(data) vs toAjax(rows): 何时用

JAVA后端开发——success(data) vs toAjax(rows): 何时用

toAjax(int rows)用途&#xff1a;用于不返回任何数据的 “写” 操作&#xff08;增、删、改&#xff09;。工作原理&#xff1a;它只接收一个 int 类型的参数&#xff08;通常是数据库操作影响的行数&#xff09;。它只关心这个数字是不是大于0&#xff0c;然后返回一个通用的…
阅读更多...
pdf格式怎么提取其中一部分张页？

pdf格式怎么提取其中一部分张页？

想从PDF里提取几个页面&#xff0c;办法还挺多的&#xff0c;下面给你唠唠常见的几种&#xff0c;保准你一看就懂。一、用专业PDF编辑软件提取 像Adobe Acrobat&#xff0c;这可是PDF编辑界的“老手”了。你先把要处理的PDF文件在Adobe Acrobat里打开&#xff0c;接着找到菜单栏…
阅读更多...
Spring监听器

Spring监听器

1、监听器的原理 ApplicationListener<T>是Spring框架中基于观察者模式实现的事件监听接口&#xff0c;用于监听应用程序中特定类型的事件。该接口是一个函数式接口&#xff0c;从Spring 4.2开始支持Lambda表达式实现。 接口定义如下&#xff1a; FunctionalInterface …
阅读更多...
基于Rust游戏引擎实践（Game）

基于Rust游戏引擎实践（Game）

Rust游戏引擎推荐 以下是一些流行的Rust游戏引擎，适用于不同开发需求： Bevy 特点：数据驱动、模块化设计，支持ECS架构，适合初学者和复杂项目。 适用场景：2D/3D游戏、原型开发。 Amethyst 特点：成熟的ECS框架，支持多线程，社区活跃。 适用场景：大型游戏或高性能应用。…
阅读更多...
PyTorch 数据加载实战：从 CSV 到图像的全流程解析

PyTorch 数据加载实战：从 CSV 到图像的全流程解析

目录 一、PyTorch 数据加载的核心组件 1.1 Dataset 类的核心方法 1.2 DataLoader 的作用 二、加载 CSV 数据实战 2.1 自定义 CSV 数据集 2.2 使用 TensorDataset 快速加载 三、加载图像数据实战 3.1 自定义图像数据集 3.2 使用 ImageFolder 快速加载 四、加载官方数据…
阅读更多...
程序人生，开启2025下半年

程序人生，开启2025下半年

时光匆匆&#xff0c;2025年已然过去一半。转眼来到了7月份。 回望过去上半年&#xff0c;可能你也经历了职场的浮沉、生活的跌宕、家庭的变故。 而下半年&#xff0c;生活依旧充满了各种变数。 大环境的起起伏伏、生活节奏的加快&#xff0c;都让未来的不确定性愈发凸显。 在这…
阅读更多...
在 .NET Core 中创建 Web Socket API

在 .NET Core 中创建 Web Socket API

要在 ASP.NET Core 中创建 WebSocket API&#xff0c;您可以按照以下步骤操作&#xff1a;设置新的 ASP.NET Core 项目打开 Visual Studio 或您喜欢的 IDE。 创建一个新的 ASP.NET Core Web 应用程序项目。 选择API模板&#xff0c;因为这将成为您的 WebSocket API 的基础。在启…
阅读更多...
Python 之地址编码识别

Python 之地址编码识别

根据输入地址&#xff0c;利用已有的地址编码文件&#xff0c;构造处理规则策略识别地址的编码。 lib/address.json 地址编码文件&#xff08;这个文件太大&#xff0c;博客里放不下&#xff0c;需要的话可以到 gitcode 仓库获取&#xff1a;https://gitcode.com/TomorrowAndT…
阅读更多...
kafka的部署

kafka的部署

目录 一、kafka简介 1.1、概述 1.2、消息系统介绍 1.3、点对点消息传递模式 1.4、发布-订阅消息传递模式 二、kafka术语解释 2.1、结构概述 2.2、broker 2.3、topic 2.4、producer 2.5、consumer 2.6、consumer group 2.7、leader 2.8、follower 2.9、partition…
阅读更多...
小语种OCR识别技术实现原理

小语种OCR识别技术实现原理

小语种OCR&#xff08;光学字符识别&#xff09;技术的实现原理涉及计算机视觉、自然语言处理&#xff08;NLP&#xff09;和深度学习等多个领域的融合&#xff0c;其核心目标是让计算机能够准确识别并理解不同语言的印刷或手写文本。以下是其关键技术实现原理的详细解析&#…
阅读更多...
GPT：让机器拥有“创造力”的语言引擎

GPT：让机器拥有“创造力”的语言引擎

当ChatGPT写出莎士比亚风格的十四行诗&#xff0c;当GitHub Copilot自动生成编程代码&#xff0c;背后都源于同一项革命性技术——**GPT&#xff08;Generative Pre-trained Transformer&#xff09;**。今天&#xff0c;我们将揭开这项“语言魔术”背后的科学原理&#xff01;…
阅读更多...
LeetCode｜Day19｜14. 最长公共前缀｜Python刷题笔记

LeetCode｜Day19｜14. 最长公共前缀｜Python刷题笔记

LeetCode&#xff5c;Day19&#xff5c;14. 最长公共前缀&#xff5c;Python刷题笔记 &#x1f5d3;️ 本文属于【LeetCode 简单题百日计划】系列 &#x1f449; 点击查看系列总目录 >> &#x1f4cc; 题目简介 题号&#xff1a;14. 最长公共前缀 难度&#xff1a;简单…
阅读更多...
安全事件响应分析--基础命令

安全事件响应分析--基础命令

----万能密码oror1 or # 1or11 1 or 11安全事件响应分析------***windoes***------方法开机启动有无异常文件 【开始】➜【运行】➜【msconfig】文件排查 各个盘下的temp(tmp)相关目录下查看有无异常文件 &#xff1a;Windows产生的 临时文件 可以通过查看日志且通过筛…
阅读更多...
基于C#+SQL Server实现（Web）学生选课管理系统

基于C#+SQL Server实现（Web）学生选课管理系统

学生选课管理系统的设计与开发一、项目背景学生选课管理系统是一个学校不可缺少的部分&#xff0c;传统的人工管理档案的方式存在着很多的缺点&#xff0c;如&#xff1a;效率低、保密性差等&#xff0c;所以开发一套综合教务系统管理软件很有必要&#xff0c;它应该具有传统的…
阅读更多...
垃圾回收(GC)

垃圾回收(GC)

内存管理策略&#xff0c;在业务进程运行的过程中&#xff0c;由垃圾收集器以类似守护协程的方式在后台运行&#xff0c;按照指定策略回收不再被使用的对象&#xff0c;释放内存空间进行回收 优势&#xff1a; 屏蔽内存回收的细节&#xff1a;屏蔽复杂的内存管理工作&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023