当前位置: 首页 > news >正文

红黑树的概念和模拟实现[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 。
总之,红黑树作为一种高效且强大的数据结构,对于优化程序性能和提高数据管理效率具有重要意义。深入理解和掌握红黑树,将为我们在计算机科学领域的探索提供有力的支持。

相关文章:

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

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

网络安全应急响应概述

前言 在网络安全领域&#xff0c;有一句广为人知的话&#xff1a;“没有绝对的安全”。这意味着任何系统都有可能被攻破。安全攻击的发生并不可怕&#xff0c;可怕的是从头到尾都毫无察觉。当系统遭遇攻击时&#xff0c;企业的安全人员需要立即进行应急响应&#xff0c;以将影响…...

【C++】链表操作技巧综合:重排链表(带你理顺链表的做题思路)

1.题目 2.算法思路 这是一道关于链表的综合题&#xff0c;一共涉及到三个步骤&#xff0c;其中每个步骤单拎出来就可以当一道单独的题目。所以需要大家对链表的操作十分熟悉&#xff0c;否则可能需要大量的时间做这道题目&#xff0c;而且还要很多的bug。 第一个步骤&#xf…...

行为型设计模式2:观察者/职责链/中介者/访问者

设计模式&#xff1a;观察者/职责链/中介者/访问者 (qq.com)...

叛逆,批判

1、对以往说法的批判之一&#xff08;第一次这么公开批判是2004-2005年&#xff09;&#xff1a; 这部英文版的《数学百科全书》似乎是从俄语版翻译过来的&#xff1f;我查了三本引用的图书文献&#xff0c;都没有关于“nonsingular”和“singular”的类似下面的说法&#xff…...

Linux 命令,mkdir说明与使用

1&#xff1a;mkdir命令功用&#xff1a; 用于创建一个或多个目录&#xff0c;创建目录&#xff0c;必须在父目录中写上权限。 新目录的默认模式为0777&#xff0c;可以由系统或用的umask来修改。 2&#xff1a;命令构件: mkdir [options] directories 3:参数选项: -m&#x…...

24. 两两交换链表中的节点(Java)

目录 题目描述&#xff1a;示例 &#xff1a;代码实现&#xff1a; 题目描述&#xff1a; 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&am…...

linux虚拟机设置固定ip

修改/etc/sysconfig/network-scripts目录下ifcfg-eth0文件&#xff0c;各虚拟机这个文件名不一致&#xff0c;ifcfg-XX格式 vim /etc/sysconfig/network-scripts/ifcfg-eth0BOOTPROTO设置为static&#xff0c;然后在最后添加固定IP地址和默认网关、DNS等配置&#xff0c;IP地址…...

mysql问题解决

1.etl数据同步时&#xff0c;发现连接不上要同步的数据库 解决方法&#xff1a;关闭mysql的ssl&#xff0c;步骤如下&#xff1a; 在MySQL中禁用SSL连接涉及修改服务器的配置文件&#xff08;通常是my.cnf或my.ini&#xff0c;取决于你的操作系统和MySQL版本&#xff09;。以…...

类和对象(下)C++

1.初始化列表 1.为什么有初始化列表&#xff0c;它的作用&#xff1f; ->初始化列表&#xff0c;是构造函数初始化的另一种形式。 ->在语法上面理解&#xff0c;初始化列表可以认定为是每个成员变量定义初始化的地方. ->引用成员变量&#xff0c;const成员变量&am…...

常用在线 Webshell 查杀工具推荐

一、简介 这篇文章将介绍几款常用的在线 Webshell 查杀工具&#xff0c;包括长亭牧云、微步在线云沙箱、河马和VirusTotal。每个工具都有其独特的特点和优势&#xff0c;用于帮助用户有效检测和清除各类恶意 Webshell&#xff0c;保障网站和服务器的安全。文章将深入探讨它们的…...

RPC远程调用框架Dubbo

一、分布式服务调用_什么是RPC RPC(Remote Procedure Call)远程过程调用&#xff0c;它是一种通过网络从远程计算机程序上请求服务。 大白话理解就是&#xff1a;RPC让你用别人家的东西就像自己家的一样。 RPC两个作用&#xff1a; 屏蔽远程调用跟本地调用的区别&#xff0c…...

基于STM32的智能灌溉系统

目录 引言环境准备工作 硬件准备软件安装与配置系统设计 系统架构硬件连接代码实现 初始化代码传感器读取和控制代码应用场景 农业灌溉花园自动灌溉常见问题及解决方案 常见问题解决方案结论 1. 引言 智能灌溉系统通过实时监测土壤湿度和环境温度&#xff0c;自动控制灌溉设…...

Datawhale AI 夏令营 Task3(半成品,仍在学习理解

课程链接 / 知识点整理 &#xff08;一&#xff09;...

细腻呵护静音生活缓冲器,家具中的隐形侍者

在忙碌的生活节奏中&#xff0c;家是我们寻找宁静与放松的避风港。而家具缓冲器&#xff0c;就像一位隐形的侍者&#xff0c;在不经意间为我们营造出温馨、宁静的居住环境。它们静静地工作&#xff0c;细腻地呵护着每一处细节&#xff0c;让家的每一次触碰成为一次尊享体验。 细…...

【MATLAB源码-第243期】基于simulink的CUK斩波电路仿真,输出各节点波形。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 CUK电路是一种高效的直流-直流转换器&#xff0c;它以其独特的能量传递方式和高效的电压转换能力&#xff0c;在许多电力电子应用中得到了广泛的使用。下面将详细描述CUK电路的工作原理、各个组成部分以及其在实际应用中的优…...

springboot项目不能同时跑junit4和junit5的解决方法

springboot项目的maven test只会跑junit4 RunWith注解的测试类&#xff0c;而不会跑junit5 ExtendWith的测试类 解决方法&#xff1a;pom加上以下plugin&#xff0c;版本号需要3.0.0-M5及以上 <plugin><groupId>org.apache.maven.plugins</groupId><art…...

【IO】使用消息队列完成两个进程之间相互通信

目录 1、使用消息队列完成两个进程之间相互通信 2、共享内存实现两个进程之间的通信 3、思维导图 1、使用消息队列完成两个进程之间相互通信 //msgsnd.c #include <myhead.h>// 要发送的消息类型 struct msgbuf {long mtype;char mtext[1024]; };// 定义一个宏&#…...

Web开发:用C#的逻辑理解VUE语法(VUE + Webapi小白开发笔记)

适用阅读对象&#xff1a;需要兼顾前端的C#后端开发人员&#xff08;基础笔记&#xff09; 目录 一、后端交互-获取实体数据 二、变量 1.声明 2.作用域 三、字符串的处理 四、数组(列表)的处理 1.数组中的SELECT语法&#xff08;提取特定字段到新数组&#xff09; 2.数…...

操作系统文件位置指针

文件位置指针 与标准IO的文件读写位置指针一样&#xff0c;系统IO时也会有一个表示位置的指针在移动&#xff0c;会随着读写操作的执行向后自动移动 当需要随机位置进行读写操作时&#xff0c;那么需要移动位置指针的位置 off_t lseek(int fd, off_t offset, int whence); 功…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

JS设计模式(5): 发布订阅模式

解锁JavaScript发布订阅模式&#xff1a;让代码沟通更优雅 在JavaScript的世界里&#xff0c;我们常常会遇到这样的场景&#xff1a;多个模块之间需要相互通信&#xff0c;但是又不想让它们产生过于紧密的耦合。这时候&#xff0c;发布订阅模式就像一位优雅的信使&#xff0c;…...