红黑树的概念和模拟实现[C++]

文章目录

  • 红黑树的概念
    • 一、红黑树的性质
    • 红黑树原理
    • 二、红黑树的优势和比较
  • 红黑树的模拟实现
    • 构建红黑树的数据结构定义节点的基本结构和初始化方式
    • 插入新节点
      • 插入新节点的颜色
      • 调整颜色和结构以满足红黑树性质
  • 红黑树的应用场景

红黑树的概念

一、红黑树的性质

在这里插入图片描述
红黑树是一种自平衡的二叉搜索树。它的节点被标记为红色或黑色,通过特定的规则来保持树的近似平衡(最长路径不超过最短路径的二倍)。其主要规则:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点是黑色的。
  3. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。[每条路径的黑色节点的数量是相等的]
  4. 如果一个节点是红色的,那么它的两个子节点都是黑色的。[也就是一条路径中,没有连续的红色节点]
  5. 每个叶子节点(NIL 节点)是黑色的。[如图中所示,就是将所有空节点当作是黑色节点,不是很重要]
    :在数路径的时候要以空节点为结束去数路径,如图有11条路经

红黑树原理

那么红黑树是如何凭借颜色来控制平衡的呢?
我们想在不违反红黑树规则,极端情况如下图【注:这种情况不一定出现,用来方便 理解】
在这里插入图片描述
最短的路径:全是黑色 最长的路径:一黑一红

那么我们设最短路径为n,最长路径也就是2n,即这张图中最长路径就是最短路径的2倍。

而还可以是这种情况如下图
在这里插入图片描述
这种情况就是最短路径的2倍大于最长路径。

所以这就是红黑树的近似平衡(即最长路径不超过最短路径的二倍
而我们这里的最长最短路径是在红黑树规则理论上而言,实际的红黑 树中最长最短不要低估是上米娜的图所示。

二、红黑树的优势和比较

红黑树之所以在众多数据结构中脱颖而出,是因为它在插入和删除操作时能够在 O(log n) 的时间复杂度内自动调整,保持平衡,从而保证了高效的查找、插入和删除性能。

以AVL树做对比:
平衡机制

  • AVL 树通过严格的平衡条件(左右子树的高度差绝对值不超过 1)来保持平衡。每次插入或删除操作后,如果导致树不平衡,需要进行复杂的旋转操作来重新平衡树。
  • 红黑树的平衡条件相对宽松,通过节点颜色的约束(红黑规则)来保持大致平衡。插入或删除操作后,调整平衡的操作相对较简单。

性能

  • 在频繁插入和删除操作的情况下,红黑树的性能通常优于 AVL 树。因为 AVL 树的平衡调整更为频繁且复杂,可能导致更多的开销。
  • 对于查找操作,AVL 树由于其更严格的平衡特性,可能会稍微快一些。

空间复杂度

  • AVL 树的每个节点需要额外存储平衡因子信息,空间复杂度相对较高。
  • 红黑树只需存储颜色信息,空间复杂度相对较低。

红黑树的模拟实现

构建红黑树的数据结构定义节点的基本结构和初始化方式

enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;//值 RBTreeNode<K, V>* _left;//该节点的左孩子RBTreeNode<K, V>* _right;//该节点的右孩子RBTreeNode<K, V>* _parent;//该节点的父节点Color _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};

先定义一个枚举类型 Color 和一个模板结构体 RBTreeNode

  • 枚举类型储存红黑两种颜色。

  • pair<K, V> _kv :用于存储键值对数据。

  • RBTreeNode<K, V>* _leftRBTreeNode<K, V>* _rightRBTreeNode<K, V>* _parent :分别指向该节点的左孩子、右孩子和父节点,构建了树结构中的节点关系。

  • Color _col :使用前面定义的枚举类型来表示节点的颜色属性。

  • 结构体中的构造函数 RBTreeNode(const pair<K, V>& kv) 用于初始化节点对象,将传入的键值对赋值给 _kv,并将指针 _left_right_parent 初始化为 nullptr

插入新节点

插入新节点的颜色

首先,按照二叉搜索树的插入规则,将新节点插入到合适的位置。
新插入的节点默认是红色,原因:
如果我们插入红色节点我们破坏规则4(如果一个节点是红色的,那么它的两个子节点都是黑色的,也就是一条路径中,没有连续的红色节点)如果我们插入黑色节点我们破坏规则3(从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点)那么我们插入黑色节点的时候规则3必然会被破坏,而插入红色节点如果父节点是黑色则没有事情,如果父节点是红色才会破坏规则4==,所以相比之下插入红色节点更好。

调整颜色和结构以满足红黑树性质

  • 如果插入节点的父节点是黑色,那么无需做任何调整,树已经满足红黑树的性质。
    • 如果插入节点的父节点是红色,那么会出现违反红黑树性质的情况,需要进行调整。
      • 情况一:父节点的兄弟节点是黑色,且父节点是祖父节点的左孩子
        • 情况 1.1:插入节点是父节点的右孩子
          对父节点进行左旋,将当前情况转换为情况 1.2。
        • 情况 1.2:插入节点是父节点的左孩子
          将父节点染成黑色,祖父节点染成红色,对祖父节点进行右旋。
      • 情况二:父节点的兄弟节点是黑色,且父节点是祖父节点的右孩子
        • 情况 2.1:插入节点是父节点的左孩子
          对父节点进行右旋,将当前情况转换为情况 2.2。
        • 情况 2.2:插入节点是父节点的右孩子
          将父节点染成黑色,祖父节点染成红色,对祖父节点进行左旋。
      • 情况三:父节点的兄弟节点是红色
        将父节点和兄弟节点染成黑色,祖父节点染成红色,以祖父节点为新的插入节点继续调整。
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;}else{parent->_left = cur;}cur->_parent = parent;//进行变色和旋转调整while (parent && parent->_col == RED){//如果u存在,cur和parent都是红,grandfather是黑//p,u变成黑,g变成红,g当成cur向上调整//u存在且是红 -> 变色进行调整Node* grandfather = parent->_parent;//p在g的左边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{//u存在且为黑或者不存在 -> 旋转加变色if (cur == parent->_left){//单旋//      g//   p      u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//双旋//      g//   p      u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//u在g的左边//     g//  u     pNode* uncle = grandfather->_left;//u存在且为红 -> 直接变色if (uncle&&uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u存在且为黑或者不存在 -> 旋转加变色if (cur == parent->_right){//单旋//      g//   u      p//             cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//双旋//      g//   u      p//        cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

红黑树的应用场景

红黑树在许多领域都有广泛的应用,比如:
数据库中的索引结构。
各种编程语言的标准库中,如 Java 中的 TreeMap 和 TreeSet 。
总之,红黑树作为一种高效且强大的数据结构,对于优化程序性能和提高数据管理效率具有重要意义。深入理解和掌握红黑树,将为我们在计算机科学领域的探索提供有力的支持。

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

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

相关文章

Redis系列之Redis Sentinel

概述 Redis主从集群&#xff0c;一主多从模式&#xff0c;包括一个Master节点和多个Slave节点。Master负责数据的读写&#xff0c;Slave节点负责数据的查询。Master上收到的数据变更&#xff0c;会同步到Slave节点上实现数据的同步。通过这种架构实现可以Redis的读写分离&…

工具|阅读PDF时鼠标显示为小手中有向下箭头解决方法

由于工作中&#xff0c;会大量阅读PDF文档&#xff0c;如手册&#xff0c;规格书&#xff0c;各种图纸等&#xff0c;因此好用的PDF工具必不可少。我主要习惯用福昕阅读器&#xff0c;标注比较方便。 所以&#xff0c;本文主要以福昕阅读器为主&#xff0c;当然也适用于其他的阅…

Docker Volume(存储卷)

一、认识 1.1 概念 存储卷就是将宿主机的本地文件系统中存在的某个目录直接与容器内部的文件系统上的某一目录建立绑定关系。这意味着&#xff0c;在容器中的这个目录下写入数据时&#xff0c;容器会将内容直接写入到宿主机上与此容器建立了绑定关系的目录 在宿主机上的这个…

实验8-1-6 在数组中查找指定元素

本题要求实现一个在数组中查找指定元素的简单函数。 函数接口定义&#xff1a; int search( int list[], int n, int x );其中list[]是用户传入的数组&#xff1b;n&#xff08;≥0&#xff09;是list[]中元素的个数&#xff1b;x是待查找的元素。如果找到 则函数search返回…

基于Golang实现Kubernetes边车模式

本文介绍了如何基于 Go 语言实现 Kubernetes Sidecar 模式&#xff0c;并通过实际示例演示创建 Golang 实现的微服务服务、Docker 容器化以及在 Kubernetes 上的部署和管理。原文: Sidecar Pattern with Kubernetes and Go[1] 在这篇文章中&#xff0c;我们会介绍 Sidecar 模式…

软件测试学习笔记

测试学习 1. 测试流程2. Bug的提出什么是bugbug 的描述bug 级别 3. 测试用例的设计什么是测试用例测试用例应如何设计基于需求的设计方法等价类边界值场景法正交表法判定表法错误猜测法 4. 自动化测试回归测试自动化分类 5. 安装 webdriver-manager 和 selenium第一个web自动化…

链表List

简介 STL中的List与顺序表vector类似&#xff0c;同样是一种序列式容器&#xff0c;其原型是带头节点的双向循环链表。 List的使用 list中的接口比较多&#xff0c;此处类似&#xff0c;只需要掌握如何正确的使用&#xff0c;然后再去深入研究背后的原理&#xff0c;已达到可…

基于R语言生物信息学大数据分析与绘图

随着高通量测序以及生物信息学的发展&#xff0c;R语言在生物大数据分析以及数据挖掘中发挥着越来越重要的作用。想要成为一名优秀的生物数据分析者与科研团队不可或缺的人才&#xff0c;除了掌握对生物大数据挖掘与分析技能之外&#xff0c;还要具备一定的统计分析能力与SCI论…

CSDN 僵尸粉 机器人

CSDN 僵尸粉 机器人 1. 前言 不知道什么时候开始每天创作2篇就有1500流量爆光&#xff0c;每次都能收获一些关注和收藏&#xff0c;感觉还是挻开心的感觉CSDN人气还是挻可以的以前各把月一个收藏和关注都没有写的动力了。 2. 正文 后面又连接做了2天的每日创建2篇任务&…

JVM(九)深入解析Java字节码技术与执行模型

这篇文章深入探讨了Java字节码技术&#xff0c;包括字节码的简介、获取字节码清单的方法、解读字节码清单、查看class文件中的常量池信息、查看方法信息、线程栈与字节码执行模型、方法体中的字节码解读、对象初始化指令、栈内存操作指令、局部变量表、流程控制指令、算术运算指…

简单的docker学习 第3章 docker镜像

第3章 Docker 镜像 3.1镜像基础 3.1.1 镜像简介 ​ 镜像是一种轻量级、可执行的独立软件包&#xff0c;也可以说是一个精简的操作系统。镜像中包含应用软件及应用软件的运行环境。具体来说镜像包含运行某个软件所需的所有内容&#xff0c;包括代码、库、环境变量和配置文件等…

加密软件中的RSA和ECC的主要区别是什么

在加密软件中&#xff0c;RSA&#xff08;Rivest-Shamir-Adleman&#xff09;和ECC&#xff08;Elliptic Curve Cryptography&#xff0c;椭圆曲线密码学&#xff09;是两种广泛使用的非对称加密算法&#xff0c;它们之间存在多个关键区别。 1. 算法基础 RSA&#xff1a;基于大…

汽车网络安全 -- MAC介绍:CMAC与CBC-MAC不能混为一谈

目录 1.什么是MAC 2.CMAC 3.HMAC 4.小结 1.什么是MAC MAC全称Message authentication code&#xff0c;是经过特定算法后产生的一小段数据信息&#xff0c;用于校验某数据的完整性和真实性。在数据传递过程中&#xff0c;可检查其内容是否被更改过&#xff0c;不管更改的原…

Webpack入门基础知识及案例

webpack相信大家都已经不陌生了&#xff0c;应用程序的静态模块打包工具。前面我们总结了vue&#xff0c;react入门基础知识&#xff0c;也分别做了vue3的实战小案例&#xff0c;react的实战案例&#xff0c;那么我们如何使用webpack对项目进行模块化打包呢&#xff1f; 话不多…

路由器IP互联无线对讲系统解决方案

一、项目概况 随着信息化的全面深入发展&#xff0c;各行各业的通信需求日益增长&#xff0c;传统的通信方式无法满足跨网络、跨系统、跨媒介的通信互联互通&#xff0c;打破信息孤岛、提高协同效率&#xff0c;成为当前各行业融合通信的首要任务。尤其大型企业、学校、医院等…

模型优化学习笔记—对比各种梯度下降算法

import mathimport numpy as np from opt_utils import * import matplotlib.pyplot as plt# 标准梯度下降 def update_parameters_with_gd(parameters, grads, learning_rate):L len(parameters) // 2for l in range(1, L 1):parameters[f"W{l}"] parameters[f&q…

自己动手实现scikit库中的fit和transform方法

文本分析第一步要解决的是如何将文本非结构化信息转化为结构化信息&#xff0c;其中最关键的是特征抽取&#xff0c;我们使用scikit-learn库fit和tranform方法实现了文本数据的特征抽取。 但是对于fit和transform&#xff0c;大家可能还是有点迷糊。最近又将《Applied Text An…

如何用一个以太网回环短接器激活以太网接口:以太网短接口制作

在非常特殊的情况下&#xff0c;我们需要在没有接以太网的情况下&#xff0c;使用本地的以太网&#xff08;有些程序、代码必须上网才能运行&#xff09;。这时候需要插上一个以太网短接口&#xff0c;骗系统已经插上网线。 制作以太网短接口 以太网短接口的制作非常简单&…

Linux OS:基于阻塞队列的生产者消费者模型

Linux OS&#xff1a;基于阻塞队列的生产者消费者模型 前言一、阻塞队列的大致框架二、生产者向阻塞队列中生产数据三、消费者获取阻塞队列中数据四、总体生产和消费思路及测试代码4.1 单生产单消费4.2 多生产多消费 五、所以代码 前言 阻塞队列是一种常用于实现生产者消费者模…

低代码: 系统开发准备之确定一般开发流程,需求分析,复杂度分析,标准开发流程

概述 低代码系统开发之前&#xff0c;我们首先要进行一些准备我们首先知道我们软件开发的一般流程同时&#xff0c;我们还要知道&#xff0c;我们整个系统平台的需求如何之后&#xff0c;我们要基于需求进行设计&#xff0c;包含UI设计与系统架构设计 一般开发流程 系统开发…