当前位置: 首页 > 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读取数据及数据操作行操作添加一行删除一行列操作增加一列删除一列通过标签选择数据条件选…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...