【C++ 】红黑树

1.1 红黑树的概念

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

在这里插入图片描述

2. 红黑树的性质

在这里插入图片描述

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
 RBTreeNode(const ValueType& data = ValueType(),Color color = RED)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
     , _data(data), _color(color)
 {}
 RBTreeNode<ValueType>* _pLeft;   // 节点的左孩子
 RBTreeNode<ValueType>* _pRight;  // 节点的右孩子
 RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转,为了实现简单给
出该字段)
 ValueType _data;            // 节点的值域
 Color _color;               // 节点的颜色
};

3. 红黑树结构

为了后续实现关联式容器简单,红黑树的实现中增加一个头结点,因为跟节点必须为黑色,为了
与根节点进行区分,将头结点给成黑色,并且让头结点的 pParent 域指向红黑树的根节点,pLeft
域指向红黑树中最小的节点,_pRight域指向红黑树中最大的节点,如下:

在这里插入图片描述

4. 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

  1. 按照二叉搜索的树规则插入新节点
template<class ValueType>
class RBTree
{
    //……
 bool Insert(const ValueType& data)
 {
 PNode& pRoot = GetRoot();
 if (nullptr == pRoot)
 {
 pRoot = new Node(data, BLACK);
 // 根的双亲为头节点
 pRoot->_pParent = _pHead;
            _pHead->_pParent = pRoot;
 }
 else
 {
 // 1. 按照二叉搜索的树方式插入新节点
             // 2. 检测新节点插入后,红黑树的性质是否造到破坏,
 //   若满足直接退出,否则对红黑树进行旋转着色处理
 }
 // 根节点的颜色可能被修改,将其改回黑色
 pRoot->_color = BLACK;
 _pHead->_pLeft = LeftMost();
 _pHead->_pRight = RightMost();
 return true;
 }
private:
 PNode& GetRoot(){ return _pHead->_pParent;}
 // 获取红黑树中最小节点,即最左侧节点
 PNode LeftMost();
 // 获取红黑树中最大节点,即最右侧节点
 PNode RightMost();
private:
 PNode _pHead;

在这里插入图片描述
在这里插入图片描述

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

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

相关文章

HCIP的学习(17)

BGP基础配置 使用直连接口IP地址来建立EBGP对等体关系 1、启动BGP协议 [r1]bgp 100 ----启动BGP协议&#xff0c;并且规定其AS号2、配置设备的RID数值&#xff0c;一般选择设备的loopback接口的IP地址 [r1-bgp]router-id 1.1.1.13、配置BGP对等体信息&#xff0c;包含了对等体…

庙算兵棋推演AI开发初探(4-调用AI模型)

前面讲了如何开展编写规则脚本型Agent&#xff08;智能体&#xff09;的方法&#xff0c;现在探究一下如何调用知识型&#xff08;一般而言的训练出的模型&#xff09;智能体的方法。 这次调用的是庙算平台的demo&#xff08;网址见图&#xff09; 下载了“知识强化学习型”…

ComfyUI 介绍及入门

介绍 ComfyUI 是一种用户界面&#xff0c;它采用了基于节点的流程设计&#xff0c;用于操作一种名为 Stable Diffusion 的技术。这种设计允许用户通过自定义流程来实现更精确的工作流程&#xff0c;并确保结果的可重复性。在 ComfyUI 中&#xff0c;每个模块都承担着特定的任务…

为什么质量工程师必学六西格玛?突破职业发展的瓶颈?

在质量管理领域工作多年&#xff0c;你是否曾感受到事业发展的停滞不前&#xff1f;3年、5年的职业生涯&#xff0c;薪水依旧停留在每月5000-7000&#xff0c;而同行业的其他人却能月入2-3万&#xff0c;这种差距让人不禁陷入深思。 问题究竟出在哪里&#xff1f;为什么我们的…

强化学习——马尔可夫过程的理解

目录 一、马尔可夫过程1.随机过程2.马尔可夫性质3.马尔可夫过程4.马尔可夫过程示例 参考文献 一、马尔可夫过程 1.随机过程 随机过程是概率论的“动态”版本。普通概率论研究的是固定不变的随机现象&#xff0c;而随机过程则专注于那些随时间不断变化的情况&#xff0c;比如天…

第五百零三回

文章目录 1. 概念介绍2. 使用方法2.1 普通路由2.2 命名路由 3. 示例代码4. 内容总结 我们在上一章回中介绍了"使用get显示Dialog"相关的内容&#xff0c;本章回中将介绍使用get进行路由管理.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在本章…

Github上5个实用的ChatGPT仓库

ChatGPT是一款基于聊天场景的大模型AI&#xff0c;最近火出圈。 Chat表示聊天&#xff0c;GPT表示大模型算法&#xff0c;它通过生成式的人机对话功能&#xff0c;让使用者第一次有了AI机器人‘懂我‘的感觉&#xff0c;而不是Siri、小爱那种傻瓜式的语音服务。 ChatGPT不仅仅…

M 有效算法

M 有效算法 本题考验二分知识&#xff0c;思路是二分k的取值&#xff0c;就按第一组样例来说当我们k取值为1的时候我们遍历数组想让|8-x|<k1的话x的取值范围是7-9&#xff0c;想让|3-x|<k2的话x的取值范围是1-5&#xff0c;两者x的区间不重合&#xff0c;说明肯定没有x能…

C/C++实现汉诺塔游戏和详细解

C/C实现汉诺塔游戏和详细解析 需要详细代码可联系QQ&#xff1a;3324729792 引言 汉诺塔问题是一个经典的递归问题&#xff0c;起源于一个传说中的印度寺庙。在这个问题中&#xff0c;我们需要将所有的圆盘从一个柱子移动到另一个柱子上&#xff0c;且在移动过程中&#xff…

2024审计师报名流程图解❗报名时间汇总❗

2024年审计专业技术资格考试报名正在进行中 &#x1f50d;审计报名流程 一、考生注册 打开浏览器登录中国人事考试网进行【考生注册】&#xff0c;按照提示认真填写个人注册信息&#xff0c;确保个人信息真实、完整、准确&#xff0c;并上传已处理好的照片。 二、考生报名 1⃣考…

Python中进程类Process的方法与属性的使用示例

一、示例代码&#xff1a; from multiprocessing import Process import time import osdef child_1(interval):print(子进程&#xff08;%s&#xff09;开始执行&#xff0c;父进程为&#xff08;%s&#xff09; % (os.getpid(), os.getppid()))t_start time.time()time.sle…

常用的30个linux命令总结

1、常用30个命令总结 2、具体参数用法参考网站&#xff1a; Linux命令大全(手册) – 真正好用的Linux命令在线查询网站

鸿蒙开发接口Ability框架:【AbilityMonitor】

AbilityMonitor AbilityMonitor模块提供匹配满足指定条件的受监视能力对象的方法的能力&#xff0c;最近匹配的能力对象将保存在AbilityMonitor对象中。 说明&#xff1a; 本模块首批接口从API version 9 开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起…

彩虹易支付用户中心美化主题 模版源码

简介&#xff1a; 彩虹易支付用户中心美化主题 模版源码 使用本主题前请备份官方版本文件再进行解压到user目录替换&#xff01; 点击下载

材料物理 笔记-8

原内容请参考哈尔滨工业大学何飞教授&#xff1a;https://www.bilibili.com/video/BV18b4y1Y7wd/?p12&spm_id_frompageDriver&vd_source61654d4a6e8d7941436149dd99026962 或《材料物理性能及其在材料研究中的应用》&#xff08;哈尔滨工业大学出版社&#xff09; ——…

绘制一个单级放大电路原理图过程,保姆级教程

新手在学习pads的使用最好最快的方法就是实际上手去画原理图&#xff0c;画PCB图&#xff0c;在这个过程中&#xff0c;就能够更快速得掌握PADS软件的使用。 本篇就是对于实际画原理图过程的一个记录&#xff0c;手把手教学&#xff0c;如果有纰漏或者有更好的一些技巧&#xf…

Spring Cloud 概述及项目创建

本篇主要介绍什么是Spring Cloud&#xff0c;以及Spring Cloud工程的创建 目录 一、什么是微服务&#xff1f; 集群 分布式 微服务 二、Spring Cloud 什么是Spring Cloud Spring Cloud 版本 Spring Cloud实现方案 Spring Cloud 工程创建 创建父工程 创建子工程 一、…

K8S安装并搭建集群

1. 先给每台机器安装docker环境 卸载旧的docker yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine 配置docker的yum库 yum install -y yum-utilsyum-config-manager --a…

[蓝桥杯]真题讲解:数三角(枚举+STL)

[蓝桥杯]真题讲解&#xff1a;数三角&#xff08;枚举STL&#xff09; 一、视频讲解二、正解代码1、C2、python33、Java 一、视频讲解 [蓝桥杯]真题讲解&#xff1a;数三角&#xff08;枚举STL&#xff09; 二、正解代码 1、C #include<bits/stdc.h> #define int long…

第十五篇:全面防护:构建不容侵犯的数据库安全策略与实战指南

全面防护&#xff1a;构建不容侵犯的数据库安全策略与实战指南 1. 引言&#xff1a;数据库安全的现代战略 1.1 简介&#xff1a;数据库安全在当今的数字化时代中的重要性 在数字化的浪潮中&#xff0c;数据已成为企业乃至国家的核心资产&#xff0c;其价值不亚于实体世界的黄…