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

【高阶数据结构】红黑树

文章目录

    • 1. 使用场景
    • 2. 性质
    • 3. 结点定义
    • 4. 结点旋转
    • 5. 结点插入

1. 使用场景

  • Linux进程调度CFS
  • Nginx Timer事件管理
  • Epoll事件块的管理

2. 性质

  • 每一个节点是红色或者黑色
  • 根节点一定是黑色
  • 每个叶子节点是黑色
  • 如果一个节点是红色,那么它的两个儿子节点都是黑色
  • 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

3. 结点定义

typedef int KEY_TYPE;typedef struct _rbtree_node
{unsigned char color;struct _rbtree_node *left;struct _rbtree_node *right;struct _rbtree_node *parent;KEY_TYPE key;void *value;
}rbtree_node;

4. 结点旋转

在这里插入图片描述

左旋实现

void _left_rotate(rbtree *T, rbtree_node *x)
{rbtree_node *y = x->right;x->right = y->left;if (y->left != T->nil){y->left->parent = x;}y->parent = x->parent;if (x->parent == T->nil){T->root == y;}else if (x == x->parent->left){x->parent->left = y;}else if (x == x->parent->right){x->parent->right = y;}y->left = x;x->parent = y;
}

右旋实现

void _right_rotate(rbtree *T, rbtree_node *y)
{rbtree_node *x = y->left;y->left = x->right;if (x->right != T->nil){x->right->parent = y;}x->parent = y->parent;if (y->parent == T->nil){T->root = x;}else if (y == y->parent->left){y->parent->left = x;}else if (y == y->parent->right){y->parent->right = x;}x->right = y;y->parent = x;
}

5. 结点插入

  1. 将新节点的颜色设为红色,然后按照二叉查找树的规则插入到合适的位置

    如果设置成黑色的话,则必定会违反上述五条性质中的第五条

  2. 如果新节点是根节点,那么将其颜色改为黑色,结束

  3. 如果新节点的父节点是黑色,那么不需要做任何调整,结束

  4. 如果新节点的父节点和叔叔节点(父节点的兄弟节点)都是红色,那么将它们的颜色改为黑色,将祖父节点(父节点的父节点)的颜色改为红色,然后把祖父节点作为新的当前节点,重复步骤2和3

  5. 如果新节点的父节点是红色,但叔叔节点是黑色或不存在,那么分四种情况进行旋转和变色操作:

    • 新节点是父节点的左子节点,且父节点是祖父节点的左子节点(左左情况),那么对祖父节点进行右旋,并交换祖父和父亲的颜色
    • 新节点是父节点的右子节点,且父节点是祖父节点的左子节点(左右情况),那么对父亲节点进行左旋,并交换新节点和父亲节点的颜色,然后把新节点作为当前节点,转化为左左情况处理
    • 新节点是父亲节点的右子节点,且父亲节点是祖父节点的右子节点(右右情况),那么对祖父节点进行左旋,并交换祖父和父亲的颜色
    • 新节点是父亲节点的左子节点,且父亲节点是祖父节点的右子节点(右左情况),那么对父亲节点进行右旋,并交换新节点和父亲节点的颜色,然后把新节点作为当前节点,转化为右右情况处理
int key_compare(KEY_TYPE *a, KEY_TYPE *b)
{//TODO
}void rbtree_insert_fixup(rbtree *T, rbtree_node *z)
{while (z->parent->color == RED){if (z->parent == z->parent->parent->left){rbtree_node *y = z->parent->parent->right;if (y->color == RED){z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;}else{if (z == z->parent->right){z = z->parent;_left_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;_right_rotate(T, z->parent->parent);}}}T->root->color = BLACK;
}void rbtree_insert(rbtree *T, rbtree_node *z)
{rbtree_node *x = T->root;rbtree_node *y = T->nil;while (x != T->nil){y = x;// 如果是自定义类型,可以实现key_compare接口来进行比较if (x->key > z->key){x = x->right;}else if (x->key < z->key){x = x->left;}else{return;}}z->parent = y;if (y == T->nil){T->root = z;}else if (z->key > y->key){y->right = z;}else{y->left = z;}z->left = T->nil;z->right = T->nil;z->color = RED;rbtree_insert_fixup(T, z);
}

相关文章:

【高阶数据结构】红黑树

文章目录1. 使用场景2. 性质3. 结点定义4. 结点旋转5. 结点插入1. 使用场景 Linux进程调度CFSNginx Timer事件管理Epoll事件块的管理 2. 性质 每一个节点是红色或者黑色根节点一定是黑色每个叶子节点是黑色如果一个节点是红色&#xff0c;那么它的两个儿子节点都是黑色从任意…...

网络协议分析期末复习(二)

目录 12. 端口的定义及常见应用对应的端口号 13. UDP协议概述 14.UDP数据报格式及各字段意义 15. UDP-Lite协议概述 16. TCP数据报格式及各字段意义 17. TCP连接建立及协商参数的过程 18. TCP连接释放过程 19. 路由协议分类及各类的具体协议 20. 路由算法常用的度量 2…...

【C++】STL简介 及 string的使用

文章目录1. STL简介1.1 什么是STL1.2 STL的版本1.3 STL的六大组件2. string类的使用2.1 C语言中的字符串2.2 标准库中的string类2.3 string类的常用接口说明1. string类对象的常见构造2. string类对象的容量操作3. string类对象的修改操作4. resize和reserve5. 认识迭代器&…...

MySQL事务详解

&#x1f3c6;今日学习目标&#xff1a; &#x1f340;Spring事务和MySQL事务详解 ✅创作者&#xff1a;林在闪闪发光 ⏰预计时间&#xff1a;30分钟 &#x1f389;个人主页&#xff1a;林在闪闪发光的个人主页 &#x1f341;林在闪闪发光的个人社区&#xff0c;欢迎你的加入: …...

ChatGPT背后的技术和多模态异构数据处理的未来展望——我与一位资深工程师的走心探讨

上周&#xff0c;我和一位从业三十余年的工程师聊到ChatGPT。 作为一名人工智能领域研究者&#xff0c;我也一直对对话式大型语言模型非常感兴趣&#xff0c;在讨论中&#xff0c;我向他解释这个技术时&#xff0c;他瞬间被其中惊人之处所吸引&#x1f64c;&#xff0c;我们深…...

iOS-砸壳篇(两种砸壳方式)

CrackerXI砸壳呢&#xff0c;当时你要是使用 frida-ios-dump 也是可以的&#xff1b; https://github.com/AloneMonkey/frida-ios-dump frida-ios-dump: 代码中需要更改的&#xff1a;手机中的内网ip 密码 等 最后放到我的砸壳路径里&#xff1a; python dump.py -l查看应用…...

linux 基础

1.Shell 命令的格式如下&#xff1a;command -options [argument]command: Shell 命令名称。options&#xff1a; 选项&#xff0c;同一种命令可能有不同的选项&#xff0c;不同的选项其实现的功能不同。argument&#xff1a; Shell 命令是可以带参数的&#xff0c;也可以不带参…...

Java:SpringBoot给Controller添加统一路由前缀

网上的文章五花八门&#xff0c;不写SpringBoot的版本号&#xff0c;导致代码拿来主义不好使了。 本文采用的版本 SpringBoot 2.7.7 Java 1.8目录1、默认访问路径2、整个项目增加路由前缀3、通过注解方式增加路由前缀4、按照目录结构添加前缀参考文章1、默认访问路径 packag…...

Java 基于 JAVE 库 实现 视频转音频的批量转换

文章目录 Java 基于 JAVE 库 实现 视频转音频的批量转换Maven:方案一:代码优化:方案二:示例代码:代码优化:结语Java 基于 JAVE 库 实现 视频转音频的批量转换 实现视频转音频的功能需要使用到一个第三方的 Java 库,叫做 JAVE。JAVE 是一个开源的 Java 库,提供了视频和音频转换…...

Spring容器——基于XML注入

1. 容器&#xff1a;IOC IoC 是 Inversion of Control 的简写&#xff0c;译为“控制反转”&#xff0c;它不是一门技术&#xff0c;而是一种设计思想&#xff0c;是一个重要的面向对象编程法则&#xff0c;能够指导我们如何设计出松耦合、更优良的程序 Spring 通过 IoC 容器来…...

设计模式(二十一)----行为型模式之状态模式

1 概述 【例】通过按钮来控制一个电梯的状态&#xff0c;一个电梯有开门状态&#xff0c;关门状态&#xff0c;停止状态&#xff0c;运行状态。每一种状态改变&#xff0c;都有可能要根据其他状态来更新处理。例如&#xff0c;如果电梯门现在处于运行时状态&#xff0c;就不能…...

一分钟理解 AP(Affinity Propagation) 亲和⼒传播算法

从来没有一个算法让我研究好几天都搞不明白&#xff0c;AP算法算是第一个。弄了好几天&#xff0c;打草纸用了几十页&#xff0c;反复琢磨&#xff0c;最后都怀疑人生了。我觉得网上那么多介绍 AP 的文章&#xff0c;基本上没有一篇能讲明白的。最后我都觉得 AP 的作者可能都没…...

使用mybatis的映射文件操作存储过程

先随便创建一个存储过程 DELIMITER $$ CREATE PROCEDURE getUserNameById (IN i_id BIGINT, OUT o_name VARCHAR(10)) BEGINSELECT u.name INTO o_name FROM tb_user u WHERE id i_id; END $$delimiter $$ : 是将sql语句的结束符号先替换成$$的意思&#xff0c;因为sql是遇到…...

世界上最完美的两个软件,太厉害了!

今天给大家介绍两个软件&#xff0c;一个体现了人类在软件开发流程上的极致&#xff0c;另外一个则体现了程序员个体能力的巅峰。01航天飞机飞控软件先来说第一个&#xff0c;航天飞机飞行控制软件&#xff0c;就是下图这个大家伙。航天飞机重达120吨&#xff0c;还携带着2000吨…...

教你成为比卡卡西还牛逼的全能忍者,全拷贝与分割函数

如何成为一个集雷切&#xff0c;写轮眼侦查和拷贝与一身的卡卡西&#xff0c;下面教你&#xff01; 目录 第一式——雷切&#xff01; strtok 第二式——写轮眼侦查&#xff01; strerror函数 第三式——写轮眼拷贝&#xff01; memcpy 模拟实现memcpy函数 &#x1f60e;…...

【LeetCode】剑指 Offer(24)

目录 题目&#xff1a;剑指 Offer 47. 礼物的最大价值 - 力扣&#xff08;Leetcode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 写在最后&#xff1a; 题目&#xff1a;剑指 Offer 47. 礼物的…...

javaEE 初阶 — CSS 元素的显示模式与盒模型

文章目录1. 元素的显示模式1.1 块级元素1.2 行内元素1.3 行内元素和块级元素的区别1.4 改变显示模式2. 盒模型2.1 边框2.1.1 边框的粗细2.1.2 边框的颜色2.1.3 边框的风格2.2 内边距2.3 外边距2.3.1 margin 的特殊情况1. 元素的显示模式 1.1 块级元素 常见的元素: h1 - h6 、…...

新星计划-我为什么要写博客?写博客的意义是什么

CSDN的各位友友们你们好,今天千泽要和大家交流一下写博客的意义,并且鼓励大家参加CSDN官方举办的新星计划,这个可以让我们更快的成长,十分有价值.接下来让我们一起开始吧!如果对您有帮助的话希望能够得到您的支持和帮助,我会持续更新的!&#x1f6a9;part1:自我介绍我是一名来自…...

嵌入式学习笔记——STM32的USART收发字符串及串口中断

USART收发字符串及串口中断前言字符串的收发发送一个字符串接收字符串需求利用串口实现printf中断中断是什么前言 上一篇中&#xff0c;介绍了串口收发相关的寄存器&#xff0c;通过代码实现了一个字节的收发&#xff0c;本文接着上面的内容&#xff0c;通过功能函数实现字符串…...

数据分析之Pandas(1)

3.Pandas 文章目录3.Pandas3.1 Pandas基本介绍3.1.1 Pandas的基本数据结构3.1.1.1 Pandas库的Series类型3.1.1.2 Pandas库的DataFrame类型DataFrame初始化DataFrame查看数据3.1.2 Pandas读取数据及数据操作行操作添加一行删除一行列操作增加一列删除一列通过标签选择数据条件选…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...