C++之红黑树模拟实现

目录

红黑树的概念

红黑树的性质

红黑树的查找效率

红黑树的实现 

红黑树的定义

红黑树节点的插入

红黑树的平衡调整

判断红黑树是否平衡 

红黑树整体代码 

测试代码

上期我们学习了AVL树的模拟实现，在此基础上，我们本期将学习另一个数据结构------红黑树。我们知道，AVL树的插入伴随着节点的旋转，那么红黑树是否在插入节点时也要进行旋转呢？这便是我们本期要学习的内容。

红黑树的概念

红黑树和AVL树一样，也是一种二叉搜索树，红黑树的每一个节点存储一个数据，表示该节点的颜色，为红色或者黑色。通过红黑树的性质作为约束，红黑树的最长路径的长度不会超过最短路径长度的二倍。红黑树图示如下。

红黑树的性质

  1. 红黑树的节点，不是红色就是黑色。
  2. 红黑树的根节点一定是黑色的。
  3. 红黑树中，如果一个节点是红色的，那么它的孩子节点一定是黑色的。（也就是说，红黑树中不能出现连续的两个红色节点）
  4. 红黑树的任意一个节点到其所有叶子节点的所有路径上的黑色节点的个数一定是相同的。
  5. 红黑树的叶子节点一定是黑色的。（这个叶子节点不是传统意义的叶子节点，而是如上图所示的NIL空节点）

 Q1:为什么通过红黑树的上述性质作为约束，能够保证红黑树的最长路径的长度不超过最短路径长度的2倍呢？

A1:其实决定上述条件的是红黑树性质中的3和4条。假设红黑树的每个路径的黑色节点的个数是4，极端情况下，红色树的最短路径就是4个黑色节点，最长路径就是1黑1红，总共4组，8个节点，所以就可以推出，红黑树的最长路径的长度不超过最短路径长度的2倍。

红黑树的查找效率与AVL树的比较

再学习AVL树时，我们知道了AVL树理想条件下其实就是一颗完全二叉树，所以对于有N个节点的完全二叉树，它的高度为logN，所以对于AVL树而言，它的查找效率是logN。

对于红黑树而言，假设红黑树的每条路径的黑色节点的个数为X，所以红黑树的高度h的范围为X<=h<=2X。假设红黑树的节点的个数为N，则N的范围为2^X-1<=N<=2^2X-1,从而得到X的取值范围为1/2logN<=X<=logN。所以对于具有N个节点的红黑树而言，红黑树的高度最高为2logN，红黑树也是搜索二叉树，所以红黑树的查找效率为2logN。

通过上述比较，不难看出，红黑树的查找效率远不及AVL树，所以我们应该是经常使用AVL树的。嗯？真的是我们想的这样吗，真的是AVL树的使用更为广泛吗？

实际上并不是这样，AVL树的查找效率固然很高，但是查找效率高的同时带来的代价也是很大的，因为AVL是高度平衡的二叉树，有时候插入一个元素往往需要旋转多次，但是对于红黑树而言，只要插入的节点的颜色不违反红黑树的性质，我们是不用进行旋转的。我们可以认为，AVL树和红黑树在插入节点时，AVL树中插入节点更容易违反性质，所以AVL插入元素时旋转的概率是远远比红黑树要高的，所以即使AVL树的查找效率更高，但是对于以数亿次运算的CPU看来，logN和2logN几乎是没有差异的，所以一般情况下，我们应用红黑树的场景更多。

红黑树的实现 

红黑树的定义

代码如下。

//枚举类型，代表红黑树节点的颜色。
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:RBTree():_root(nullptr){}private:Node* _root;};

红黑树节点的插入

查找合适的位置进行节点的插入，代码如下。

//如果当前红黑树为空，则直接插入即可if (_root == nullptr){_root = new Node(pair);_root->_col = BLACK;return true;}//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入Node* cur = _root;Node* parent = _root->_parent;while (cur){if (cur->_kv.first > pair.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < pair.first){parent = cur;cur = cur->_right;}else{return false;printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");}}cur = new Node(pair);cur->_col = RED;cur->_parent = parent;if (cur->_kv.first > parent->_kv.first){parent->_right= cur ;}else{parent->_left= cur ;}

红黑树的平衡调整

在插入一个结点时，为了对整个红黑树的影响最小，一般我们插入的都是红色节点。但是在插入红色节点时，可能会遇到很多情景，大致分为三种。

我们将插入的节点称为cur节点，将cur节点的父亲称为parent节点，将cur节点的叔叔称为uncle节点，将cur节点的祖父称为grandfather节点。在此基础上我们展开分析。

情景1：uncle节点存在且为红。

代码如下。 

情景2和3，uncle节点存在为黑色或者uncle节点不存在。

 代码如下。

	while (parent&& parent->_col == RED){Node* grandfather = parent->_parent;//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡if (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{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_right;if (uncle&& uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}

判断红黑树是否平衡 

代码如下。

bool IsBalance(){if (_root && _root->_col == RED){cout<<"根节点的颜色是红色，不符合红黑树的性质";return false;}int banchmark = 0;//选取最左侧的路径的黑色节点的个数为基准值Node* left = _root;while (left){if (left->_col == BLACK){banchmark++;}left = left->_left;}int blackcount = 0;return _IsBalance(_root, banchmark, blackcount);}bool _IsBalance(Node* root, int banchmark, int blackcount){if (root == nullptr){if (banchmark != blackcount){return false;}return  true;}if (root->_col == RED && root->_parent->_col == RED){cout<<"出现两个连续的红节点，不符和红黑树的性质" << endl;return false;}if (root->_col == BLACK){blackcount++;}return _IsBalance(root->_left, banchmark, blackcount) && _IsBalance(root->_right,banchmark, blackcount);}

红黑树整体代码 

 红黑树实现代码如下。

#include<time.h>
#include<iostream>
#include<vector>
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>
class RBTree 
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}//红黑树节点的插入bool Insert(const pair<K, V>& pair){//如果当前红黑树为空，则直接插入即可if (_root == nullptr){_root = new Node(pair);_root->_col = BLACK;return true;}//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入Node* cur = _root;Node* parent = _root->_parent;while (cur){if (cur->_kv.first > pair.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < pair.first){parent = cur;cur = cur->_right;}else{return false;printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");}}cur = new Node(pair);cur->_col = RED;cur->_parent = parent;if (cur->_kv.first > parent->_kv.first){parent->_right= cur ;}else{parent->_left= cur ;}//调整平衡while (parent&& parent->_col == RED){Node* grandfather = parent->_parent;//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡if (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{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_right;if (uncle&& uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(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;if (subRL){subRL->_parent = parent;}Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_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 (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == NULL)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root;};

测试代码

void TestRBTree()
{RBTree<int, int> t;vector<int> v;srand(time(0));int N = 10;for (int i = 0; i < N; ++i){v.push_back(rand());}for (auto e : v){t.Insert(make_pair(e, e));}t.InOrder();cout<< t.IsBalance() << endl;}

运行结果如下。

运行结果符合预期。 

以上便是红黑树的所有内容，较于AVL树，红黑树的应用较为广泛，后续的容器map和set以及哈希结构都是使用红黑树实现的。这些都是我们下几期要重点研究的。 

本期内容到此结束^_^

 

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

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

相关文章

SDMTSP：粒子群优化算法PSO求解单仓库多旅行商问题，可以更改数据集和起点（MATLAB代码）

SDMTSP：粒子群优化算法PSO求解单仓库多旅行商问题，可以更改数据集和起点（MATLAB代码）

一、单仓库多旅行商问题 单仓库多旅行商问题&#xff08;Single-Depot Multiple Travelling Salesman Problem, SD-MTSP&#xff09;&#xff1a;&#x1d45a;个推销员从同一座中心城市出发&#xff0c;访问其中一定数量的城市并且每座城市只能被某一个推销员访问一次&#x…
阅读更多...
【Yonghong 企业日常问题 06】上传的文件不在白名单，修改allow.jar.digest属性添加允许上传的文件SH256值？

【Yonghong 企业日常问题 06】上传的文件不在白名单，修改allow.jar.digest属性添加允许上传的文件SH256值？

文章目录 前言问题描述问题分析问题解决1.允许所有用户上传驱动文件2.如果是想只上传白名单的驱动 前言 该方法适合永洪BI系列产品&#xff0c;包括不限于vividime desktop&#xff0c;vividime z-suit&#xff0c;vividime x-suit产品。 问题描述 当我们连接数据源的时候&a…
阅读更多...
决策树（理论知识3）

决策树（理论知识3）

目录 评选算法信息增益&#xff08; ID3 算法选用的评估标准&#xff09;信息增益率&#xff08; C4.5 算法选用的评估标准&#xff09;基尼系数&#xff08; CART 算法选用的评估标准&#xff09;基尼增益基尼增益率 评选算法 决策树学习的关键在于&#xff1a;如何选择最优划…
阅读更多...
Echarts连接数据库，实时绘制图表详解

Echarts连接数据库，实时绘制图表详解

文章目录 Echarts连接数据库&#xff0c;实时绘制图表详解一、引言二、步骤一&#xff1a;环境准备与数据库连接1、环境搭建2、数据库连接 三、步骤二&#xff1a;数据获取与处理1、查询数据库2、数据处理 四、步骤三&#xff1a;ECharts图表配置与渲染1、配置ECharts选项2、动…
阅读更多...
Odoo 免费开源 ERP：通过 JavaScript 创建对话框窗口的技术实践分享

Odoo 免费开源 ERP：通过 JavaScript 创建对话框窗口的技术实践分享

作者 | 老杨 出品 | 上海开源智造软件有限公司&#xff08;OSCG&#xff09; 概述 在本文中&#xff0c;我们将深入研讨如何于 Odoo 18 中构建 JavaScript&#xff08;JS&#xff09;对话框或弹出窗口。对话框乃是展现重要讯息、确认用户操作以及警示用户留意警告或错误的行…
阅读更多...
flask-admin的modelview 实现list列表视图中扩展修改状态按钮

flask-admin的modelview 实现list列表视图中扩展修改状态按钮

背景&#xff1a; 在flask-admin的模型视图&#xff08;modelview 及其子类&#xff09;中如果不想重构UI视图&#xff0c;那么就不可避免的出现默认视图无法很好满足需求的情况&#xff0c;如默认视图中只有“新增”&#xff0c;“编辑”&#xff0c;“选中的”三个按钮。 材…
阅读更多...
低空经济的地理信息支撑：构建安全、高效的飞行管理体系

低空经济的地理信息支撑：构建安全、高效的飞行管理体系

随着无人机等低空飞行器的广泛应用&#xff0c;低空空域管理的重要性日益凸显。地理信息技术作为低空空域管理的重要支撑&#xff0c;对于保障低空经济的健康发展具有不可替代的作用。 地理信息技术在低空空域管理中的作用 地理信息技术在低空空域管理中扮演着关键角色&#x…
阅读更多...
圣诞节文化交流会在洛杉矶成功举办

圣诞节文化交流会在洛杉矶成功举办

洛杉矶——12月21日&#xff0c;备受期待的“圣诞节文化交流会&#xff08;Christmas Art and Cultural Exchange Fair&#xff09;”在尔湾成功举办。本次活动由M.A.D, ACSDA Youth Committee, GlowStar Art Foundation共同举办&#xff0c;此次活动以文化交流为主题&#xff…
阅读更多...
007-spring-bean的相关配置（重要）

007-spring-bean的相关配置（重要）

spring-bean的相关配置
阅读更多...
什么样的LabVIEW控制算自动控制？

什么样的LabVIEW控制算自动控制？

自动控制是指系统通过预先设计的算法和逻辑&#xff0c;在无人工干预的情况下对被控对象的状态进行实时监测、决策和调整&#xff0c;达到预期目标的过程。LabVIEW作为一种图形化编程工具&#xff0c;非常适合开发自动控制系统。那么&#xff0c;什么样的LabVIEW控制算作“自动…
阅读更多...
打造独特的博客封面：动态封面设置指南

打造独特的博客封面：动态封面设置指南

如何设置你的专属封面 1先找到一个好的壁纸 以下是好用的壁纸网站 花瓣网 千图网 包图网 WallHere 壁纸 浏览器搜索可画 可画 或者是下载可画的PC端软件 我这里使用的是可画的PC端软件 我们选择这个 单图海报(横板 - 1200 * 726 像素) 这是我们进入的页面 我们点击…
阅读更多...
快速解决oracle 11g中exp无法导出空表的问题

快速解决oracle 11g中exp无法导出空表的问题

在一些生产系统中&#xff0c;有些时候我们为了进行oracle数据库部分数据的备份和迁移&#xff0c;会使用exp进行数据的导出。但在实际导出的时候&#xff0c;我们发现导出的时候&#xff0c;发现很多空表未进行导出。今天我们给出一个快速解决该问题的办法。 一、问题复现 我…
阅读更多...
机器人加装电主轴【铣削、钻孔、打磨、去毛刺】更高效

机器人加装电主轴【铣削、钻孔、打磨、去毛刺】更高效

机器人加装电主轴进行铣削、钻孔、打磨、去毛刺等作业&#xff0c;展现出显著的优势&#xff0c;并能实现高效加工。 1. 高精度与高效率 电主轴特点&#xff1a;高速电主轴德国SycoTec的产品&#xff0c;转速可达100000rpm&#xff0c;功率范围广&#xff0c;精度≤1μm&#…
阅读更多...
详细介绍如何使用rapidjson读取json文件

详细介绍如何使用rapidjson读取json文件

本文主要详细介绍如何使用rapidjson库来实现.json文件的读取&#xff0c;分为相关基础介绍、结合简单示例进行基础介绍、结合复杂示例进行详细的函数实现介绍等三部分。 一、相关基础 1、Json文件中的{} 和 [] 在 JSON 文件中&#xff0c;{} 和 [] 分别表示不同的数据结构&…
阅读更多...
TGRS | 可变形傅里叶卷积用于遥感道路分割

TGRS | 可变形傅里叶卷积用于遥感道路分割

题目&#xff1a;Fourier-Deformable Convolution Network for Road Segmentation From Remote Sensing Images 期刊&#xff1a;IEEE Transactions on Geoscience and Remote Sensing 论文&#xff1a;https://ieeexplore.ieee.org/document/10707598/ 代码&#xff1a;htt…
阅读更多...
Linux复习4——shell与文本处理

Linux复习4——shell与文本处理

认识vim编辑器 #基本语法格式&#xff1a; vim 文件名 •如果文件存在&#xff0c;进入编辑状态对其进行编辑 •如果文件不存在&#xff0c;创建文件并进入编辑状态 例&#xff1a; [rootlocalhosttest]# vim practice.txt #Vim 编辑器三种模式&#xff1a; 命令模式&a…
阅读更多...
GIT与github的链接（同步本地与远程仓库）

GIT与github的链接（同步本地与远程仓库）

1.官网下载GIT Git - 安装 Git 2.GIT生成密钥 2.1 打开gitbash配置邮箱与用户名&#xff08;非初次使用GIT跳过这一步&#xff09; git config --global user.name "你的用户名" git config --global user.email "你的邮箱" 2.2 生成ssh密匙 1&#xff0…
阅读更多...
小程序租赁系统开发指南与实现策略

小程序租赁系统开发指南与实现策略

内容概要 在如今这个快节奏的时代&#xff0c;小程序租赁系统的开发正逐渐成为许多商家提升服务质量与效率的重要选择。在设计这样一个系统时&#xff0c;首先要明白它的核心目标&#xff1a;便捷、安全。用户希望在最短的时间内找到需要的物品&#xff0c;而商家则希望通过这…
阅读更多...
深度学习之超分辨率算法——FRCNN

深度学习之超分辨率算法——FRCNN

– 对之前SRCNN算法的改进 输出层采用转置卷积层放大尺寸&#xff0c;这样可以直接将低分辨率图片输入模型中&#xff0c;解决了输入尺度问题。改变特征维数&#xff0c;使用更小的卷积核和使用更多的映射层。卷积核更小&#xff0c;加入了更多的激活层。共享其中的映射层&…
阅读更多...
vue3项目history路由模式部署上线405、刷新404问题(包括部分页面刷新404问题)

vue3项目history路由模式部署上线405、刷新404问题(包括部分页面刷新404问题)

一、找不到js模块 解决方法&#xff1a;配置Nginx配置文件&#xff1a; // root /your/program/path/dist root /www/wwwroot/my_manage_backend_v1/dist;二、刷新页面导致404问题(Not found) 经过一系列配置后发现进入页面一切正常&#xff0c;包括路由前进和回退&#xff0…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023