红黑树

一、红黑树用在哪里

  • HashMap。
  • Linux 进程调度 CFS。
  • Epoll 事件块的管理。
  • Nginx Timer 事件管理。
  • （key，value）的形式，并且中序遍历是顺序的，红黑树是二叉排序树。

二、红黑树性质

  • 每个节点是红色或者黑色。
  • 根节点是黑色的。
  • 所有叶子节点都隐藏，并且为黑色。
  • 如果一个节点是红色的，则它的两个儿子都是黑色的 → 红色节点不相邻。
  • 对每个节点，从该节点到其子孙节点的所有路径上的包含相同数目的黑节点 → 黑色节点高度一样。
    • 从根节点到叶子节点的最大深度和最小深度的关系是 2n - 1 : n

在这里插入图片描述

三、红黑树代码

typedef struct _rbtree_node {int key;void *value;struct _rbtree_node *right;struct _rbtree_node *left;struct _rbtree_node *parent;unsigned char color;
} rbtree_node;struct _rbtree {struct _rbtree_node root;struct _rbtree_node *nil; // 所有叶子节点都隐藏，并且为黑色
} rbtree;

// 改进（如果一个结构体里有多棵红黑树）
// 减少冗余代码
#define RBTREE_ENTRY(name, type) struct name {struct type *right;struct type *left;struct type *parent;unsigned char color;}typedef int KEY_TYPE;typedef struct _my_thread{KEY_TYPE key;void *value;RBTREE_ENTRY(, _my_thread) ready;RBTREE_ENTRY(, _my_thread) wait;RBTREE_ENTRY(, _my_thread) sleep;RBTREE_ENTRY(, _my_thread) exit;
} my_thread;

四、红黑树旋转

  • 当红黑树性质被破坏的时候，需要调整 → 左旋，右旋。
  • 红黑树的插入或者删除最多旋转树的高度次就可以达到平衡。

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

void rbtree_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){ // x 为根节点T->root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}// 第三步y->left = x;x->parent = y;
}void rbtree_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->parentl;if (y->parent == T->nil) { // y 为根节点T->root = x;} else if (y == y->parent->right) {y->parent->right= x; } else {y->parent->left= x;}x->right = y;y->parent = x;
}

五、红黑树插入

  • 红黑树在插入节点以前，它已经是一棵红黑树了。
  • 插入节点上色为红色，因为不会改变黑色节点高度
  • 父节点是祖父节点的左子树

    • 叔节点是红色的。
      在这里插入图片描述

    • 叔节点是黑色的，并且当前节点是右子树。
      在这里插入图片描述

    • 叔节点是黑色的，并且当前节点是左子树。
      在这里插入图片描述

#define RED 0
#define BLACK 1void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {while (z->parent->color == RED) { //z ---> REDif (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; //z --> RED} else {if (z == z->parent->right) {z = z->parent;rbtree_left_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_right_rotate(T, z->parent->parent);}} else {rbtree_node *y = z->parent->parent->left;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent; //z --> RED} else {if (z == z->parent->left) {z = z->parent;rbtree_right_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_left_rotate(T, z->parent->parent);}}}T->root->color = BLACK;
}void rbtree_insert(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->root;while (x != T->nil) {y = x;if (z->key < x->key) {x = x->left;} else if (z->key > x->key) {x = x->right;} else { //Exist 由业务场景决定return ;}}z->parent = y;if (y == T->nil) {T->root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}z->left = T->nil;z->right = T->nil;z->color = RED;rbtree_insert_fixup(T, z);
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define RED             1
#define BLACK           2typedef int KEY_TYPE;typedef struct _rbtree_node {unsigned char color;struct _rbtree_node *right;struct _rbtree_node *left;struct _rbtree_node *parent;KEY_TYPE key;void *value;
} rbtree_node;typedef struct _rbtree {rbtree_node *root;rbtree_node *nil;
} rbtree;rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {while (x->left != T->nil) {x = x->left;}return x;
}rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {while (x->right != T->nil) {x = x->right;}return x;
}rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {rbtree_node *y = x->parent;if (x->right != T->nil) {return rbtree_mini(T, x->right);}while ((y != T->nil) && (x == y->right)) {x = y;y = y->parent;}return y;
}void rbtree_left_rotate(rbtree *T, rbtree_node *x) {rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> rightx->right = y->left; //1 1if (y->left != T->nil) { //1 2y->left->parent = x;}y->parent = x->parent; //1 3if (x->parent == T->nil) { //1 4T->root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x; //1 5x->parent = y; //1 6
}void rbtree_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->right) {y->parent->right = x;} else {y->parent->left = x;}x->right = y;y->parent = x;
}void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {while (z->parent->color == RED) { //z ---> REDif (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; //z --> RED} else {if (z == z->parent->right) {z = z->parent;rbtree_left_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_right_rotate(T, z->parent->parent);}}else {rbtree_node *y = z->parent->parent->left;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent; //z --> RED} else {if (z == z->parent->left) {z = z->parent;rbtree_right_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_left_rotate(T, z->parent->parent);}}}T->root->color = BLACK;
}void rbtree_insert(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->root;while (x != T->nil) {y = x;if (z->key < x->key) {x = x->left;} else if (z->key > x->key) {x = x->right;} else { //Existreturn ;}}z->parent = y;if (y == T->nil) {T->root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}z->left = T->nil;z->right = T->nil;z->color = RED;rbtree_insert_fixup(T, z);
}void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {while ((x != T->root) && (x->color == BLACK)) {if (x == x->parent->left) {rbtree_node *w= x->parent->right;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rbtree_left_rotate(T, x->parent);w = x->parent->right;}if ((w->left->color == BLACK) && (w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (w->right->color == BLACK) {w->left->color = BLACK;w->color = RED;rbtree_right_rotate(T, w);w = x->parent->right;}w->color = x->parent->color;x->parent->color = BLACK;w->right->color = BLACK;rbtree_left_rotate(T, x->parent);x = T->root;}} else {rbtree_node *w = x->parent->left;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rbtree_right_rotate(T, x->parent);w = x->parent->left;}if ((w->left->color == BLACK) && (w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (w->left->color == BLACK) {w->right->color = BLACK;w->color = RED;rbtree_left_rotate(T, w);w = x->parent->left;}w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;rbtree_right_rotate(T, x->parent);x = T->root;}}}x->color = BLACK;
}rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->nil;if ((z->left == T->nil) || (z->right == T->nil)) {y = z;} else {y = rbtree_successor(T, z);}if (y->left != T->nil) {x = y->left;} else if (y->right != T->nil) {x = y->right;}x->parent = y->parent;if (y->parent == T->nil) {T->root = x;} else if (y == y->parent->left) {y->parent->left = x;} else {y->parent->right = x;}if (y != z) {z->key = y->key;z->value = y->value;}if (y->color == BLACK) {rbtree_delete_fixup(T, x);}return y;
}rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {rbtree_node *node = T->root;while (node != T->nil) {if (key < node->key) {node = node->left;} else if (key > node->key) {node = node->right;} else {return node;}   }return T->nil;
}void rbtree_traversal(rbtree *T, rbtree_node *node) {if (node != T->nil) {rbtree_traversal(T, node->left);printf("key:%d, color:%d\n", node->key, node->color);rbtree_traversal(T, node->right);}
}int main() {int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};rbtree *T = (rbtree *)malloc(sizeof(rbtree));if (T == NULL) {printf("malloc failed\n");return -1;}T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));T->nil->color = BLACK;T->root = T->nil;rbtree_node *node = T->nil;int i = 0;for (i = 0;i < 20;i ++) {node = (rbtree_node*)malloc(sizeof(rbtree_node));node->key = keyArray[i];node->value = NULL;rbtree_insert(T, node);}rbtree_traversal(T, T->root);printf("----------------------------------------\n");for (i = 0;i < 20;i ++) {rbtree_node *node = rbtree_search(T, keyArray[i]);rbtree_node *cur = rbtree_delete(T, node);free(cur);rbtree_traversal(T, T->root);printf("----------------------------------------\n");}
}

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

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

相关文章

C++构造函数和析构函数的调用顺序

C++构造函数和析构函数的调用顺序

一般情况下&#xff0c;调用析构函数的次序正好与调用构造函数的次序相反&#xff0c;也就是最先被调用的构造函数&#xff0c;其对应的析构函数最后被调用&#xff0c;而最后被调用的构造函数&#xff0c;其对应的析构函数最先被调用。 当然对象的构造函数和析构函数调用时机和…
阅读更多...
【软件开发规范篇】JAVA后端开发编程规范

【软件开发规范篇】JAVA后端开发编程规范

作者介绍&#xff1a;本人笔名姑苏老陈&#xff0c;从事JAVA开发工作十多年了&#xff0c;带过大学刚毕业的实习生&#xff0c;也带过技术团队。最近有个朋友的表弟&#xff0c;马上要大学毕业了&#xff0c;想从事JAVA开发工作&#xff0c;但不知道从何处入手。于是&#xff0…
阅读更多...
电子取证平航杯的复现

电子取证平航杯的复现

闻早起部分&#xff1a; 一、闻早起的windows10电脑 &#xff08;1&#xff09;.“闻早起”所使用的笔记本电脑使用何种加密程式&#xff1f; 1.在EFI文件中找到加密程式 &#xff08;2&#xff09; 教徒“闻早起”所使用的笔记本电脑中安装了一款还原软件&#xff0c;其版本…
阅读更多...
Llama 3 ——开源大模型Llama 3从概念到使用

Llama 3 ——开源大模型Llama 3从概念到使用

概述 Meta公司自豪地宣布推出其最新的开源大型语言模型——Llama 3&#xff0c;这是一款专为未来AI挑战而设计的先进工具。Llama 3包含两个不同参数规模的版本&#xff0c;以满足多样化的计算需求&#xff1a; 8B版本&#xff1a;优化了在消费级GPU上的部署和开发流程&#xf…
阅读更多...
低代码工业组态数字孪生平台

低代码工业组态数字孪生平台

2024 两会热词「新质生产力」凭借其主要特征——高科技、高效能及高质量&#xff0c;引发各界关注。在探索构建新质生产力的重要议题中&#xff0c;数据要素被视为土地、劳动力、资本和技术之后的第五大生产要素。数据要素赋能新质生产力发展主要体现为&#xff1a;生产力由生产…
阅读更多...
【StarRocks系列】 Trino 方言支持

【StarRocks系列】 Trino 方言支持

我们在之前的文章中&#xff0c;介绍了 Doris 官方提供的两种方言转换工具&#xff0c;分别是 sql convertor 和方言 plugin。StarRocks 目前同样也提供了类似的方言转换功能。本文我们就一起来看一下这个功能的实现与 Doris 相比有何不同。 一、Trino 方言验证 我们可以通过…
阅读更多...
论文精读-存内计算芯片研究进展及应用

论文精读-存内计算芯片研究进展及应用

文章目录 论文精读-存内计算芯片研究进展及应用概述背景介绍前人工作 存内计算3.1 SRAM存内计算3.2 DRAM存内计算3.3 ReRAM/PCM存内计算3.4 MRAM存内计算3.5 NOR Flash存内计算3.6 基于其他介质的存内计算3.7 存内计算芯片应用场景 总结QA 论文精读-存内计算芯片研究进展及应用…
阅读更多...
服务攻防-数据库安全RedisCouchDBH2database未授权访问CVE漏洞

服务攻防-数据库安全RedisCouchDBH2database未授权访问CVE漏洞

#知识点&#xff1a; 1、数据库-Redis-未授权RCE&CVE 2、数据库-Couchdb-未授权RCE&CVE 3、数据库-H2database-未授权RCE&CVE#章节点&#xff1a; 1、目标判断-端口扫描&组合判断&信息来源 2、安全问题-配置不当&CVE漏洞&弱口令爆破 3、复现对象-数…
阅读更多...
第08章 IP分类编址和无分类编址

第08章 IP分类编址和无分类编址

8.1 本章目标 了解IP地址的用途和种类了解分类编址和无分类编址区别掌握IP地址、子网掩码、网关概念及使用掌握子网划分及超网划分方法掌握无分类编址的改变和使用 8.2 IP地址的用途和种类 分类编址&#xff1a;造成地址的浪费&#xff0c;以及地址不够用&#xff1b;无分类编…
阅读更多...
3.栈和队列（汇总版）

3.栈和队列（汇总版）

目录 1.栈&#xff08;一端插和删&#xff09; 2.队列&#xff08;一端插另一段删&#xff09; 2.1队列的概念及结构 2.2 队列的实现 队列的接口 1.初始化队列 2.销毁队列 3.插入元素 4.出队列&#xff08;头删&#xff09; 5.访问对头 6.访问队尾 7.判断队列是否为…
阅读更多...
美特CRM upload.jsp 文件上传致RCE漏洞复现(CNVD-2023-06971)

美特CRM upload.jsp 文件上传致RCE漏洞复现(CNVD-2023-06971)

0x01 产品简介 MetaCRM是一款智能平台化CRM软件,通过提升企业管理和协同办公,全面提高企业管理水平和运营效率,帮助企业实现卓越管理。美特软件开创性地在CRM领域中引入用户级产品平台MetaCRM V5/V6，多年来一直在持续地为客户创造价值，大幅提升了用户需求满足度与使用的满意…
阅读更多...
workminer之dht通信部分

workminer之dht通信部分

workminer是通过SSH爆破传播的挖矿木马&#xff0c;感染后会释放xmrig挖矿程序利用主机的CPU挖取北方门罗币。该样本能够执行特定的指令&#xff0c;指令保存在一个配置文件config中&#xff0c;config文件类似于xml文件&#xff0c;里面有要执行的指令和参数&#xff0c;样本中…
阅读更多...
Three.js纹理贴图

Three.js纹理贴图

偏移 旋转 重复 纹理显示的清晰度 <template><div id"webgl"></div> </template><script setup> import * as THREE from three; import { OrbitControls } from three/addons/controls/OrbitControls.js;const scene new THREE…
阅读更多...
数据库SQL语言实战（七）

数据库SQL语言实战（七）

前言 这次的有一点点难~~~~~我也写了好久 练习题 题目一 在学生表pub.student中统计名字&#xff08;姓名的第一位是姓氏&#xff0c;其余为名字&#xff0c;不考虑复姓&#xff09;的使用的频率&#xff0c;将统计结果放入表test5_01中 create table test5_01(First_name…
阅读更多...
【notes2】并发，IO，内存

【notes2】并发，IO，内存

文章目录 1.线程/协程/异步&#xff1a;并发对应硬件资源是cpu&#xff0c;线程是操作系统如何利用cpu资源的一种抽象2.并发&#xff1a;cpu&#xff0c;线程2.1 可见性&#xff1a;volatile2.2 原子性&#xff08;读写原子&#xff09;&#xff1a;AtomicInteger/synchronized…
阅读更多...
SparkSql介绍

SparkSql介绍

概述 SparkSQL&#xff0c;顾名思义&#xff0c;就是Spark生态体系中的构建在SparkCore基础之上的一个基于SQL的计算模块。SparkSQL的前身不叫SparkSQL&#xff0c;而叫Shark&#xff0c;最开始的时候底层代码优化&#xff0c;sql的解析、执行引擎等等完全基于Hive&#xff0c…
阅读更多...
React中的高阶组件的封装,高阶函数,HOC的含义及用法:

React中的高阶组件的封装,高阶函数,HOC的含义及用法:

含义及作用: 高阶函数代码案例: 调用高阶组价:
阅读更多...
软件测试与管理：黑盒测试-等价类划分法和 边界值分析法

软件测试与管理：黑盒测试-等价类划分法和 边界值分析法

知识思维导图&#xff1a; 例题1&#xff1a;日期检查功能的等价类划分 设有一个档案管理系统&#xff0c;要求用户输入以年月表示的日期。假设日期限定在1990年1月~2049年12月&#xff0c;并规定日期由6位数字字符组成&#xff0c;前4位表示年&#xff0c;后2位表示月。现用等…
阅读更多...
计算机组成原理实验一 寄存器实验

计算机组成原理实验一 寄存器实验

目录 实验目的和要求 实验环境 实验内容与过程 连接线表 将8AH写入A寄存器 将6cH写入W寄存器 实验结果与分析 实验箱主要部件 将55H写入A寄存器 将66H写入W寄存器 按住STEP脉冲键实验现象? (实验箱中有什么变化) 放开STEP 键实验现象? (实验箱中有什么变化) 数据…
阅读更多...
proxy代理面试题

proxy代理面试题

1、动态属性值 const r1add[1][2][3]4//输出10 const r2add[10][20]30//输出60 const r3add[100][200][300]400//输出1000柯里化&#xff0c;有参考下文 https://blog.csdn.net/p1967914901/article/details/127621032 add 是对象&#xff0c;通过链式传入属性求和返回结果&a…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023