红黑树(RBTree)

news/2024/7/24 13:50:09/

红黑树的基本性质
(1)红黑树是每个结点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉搜索树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 结点是红色或黑色。 

性质2. 根结点是黑色。 

性质3. 所有叶子都是黑色。(叶子是NIL结点) 

性质4. 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。 

     这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。 

性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长。 

因为红黑树是一种特化二叉查找树,所以红黑树上的只读操作与普通二叉查找树相同。 

结点设置和初始化:

typedef enum {RED = 0,BLACK = 1}ColorType;
typedef int KeyType;typedef struct rb_node
{rb_node* leftchild;rb_node* parent;rb_node* rightchild;ColorType color;KeyType key;
}rbnode;
typedef struct
{struct rb_node *root;struct rb_node* Nil;//哨兵结点int cursize;
}RBTree;
rb_node* Buynode(rb_node* parg, ColorType carg)
{rb_node* s = (rb_node*)calloc(1,sizeof(rb_node));if (s == nullptr)exit(1);s->color = carg;s->parent = parg;return s;
}
void Freenode(rb_node* p)
{free(p);
}
void InitRBTree(RBTree* ptree)
{assert(ptree != nullptr);ptree->Nil = Buynode(nullptr, BLACK);ptree->root = ptree->Nil;ptree->cursize = 0;
}

插入

插入过程首先是根据一般二叉查找树的插入步骤, 把新结点 插入到 某个叶结点的位置上,然后将 新节点着为红色。 为了保证红黑树的性质能继续保持,再对有关结点重点着色并旋转,其插入算法如下: 

1 按二叉查找树的插入步骤将结点新节点插入到 树tree中;

2 如果前面没有节点,则置为根节点(结束);

3 找到插入的位置,判断是双亲结点的左孩子还是右孩子;

4 从插入节点开始回溯,调整红黑树的结构使其满足上述五个性质;
 


bool Insert(rb_node*& tree, KeyType kx)
{assert(tree!= nullptr);rb_node* pa = nullptr;rb_node* p = tree;while (p != nullptr && p->key != kx)//找到插入位置{pa = p;p = kx < p->key ? p->leftchild : p->rightchild;}if (p != nullptr && p->key == kx) return false;p = Buynode();//购买节点p->key = kx;p->parent = pa;if (kx < pa->key)//判断是左右那个孩子{pa->leftchild = p;}else{pa->rightchild = p;}PassRBTree(tree, p);return true;
}
void PassRBTree(rb_node*& tree, rb_node* p)//左旋右旋函数与AVL树相同
{rb_node* _X = nullptr;for (; p != tree && p->parent->color == RED;){if (p->parent->parent->rightchild == p->parent)	 // ringht{_X = p->parent->parent->leftchild;if (_X->color == RED){_X->color = BLACK;p->parent->color = BLACK;p->parent->parent->color = RED;p = p->parent->parent;}else{if (p->parent->leftchild == p){p = p->parent;RotateRight(tree, p);}p->parent->color = BLACK;p->parent->parent->color = RED;RotateLeft(tree, p->parent->parent);}}else{_X = p->parent->parent->rightchild;if (_X->color == RED){_X->color = BLACK;p->parent->color = BLACK;p->parent->parent->color = RED;p = p->parent->parent;}else{if (p->parent->rightchild == p){p = p->parent;RotateLeft(tree, p);}p->parent->color = BLACK;p->parent->parent->color = RED;RotateRight(tree, p->parent->parent);}}}tree->color = BLACK;
}


http://www.ppmy.cn/news/70456.html

相关文章

包管理工具:pnpm | 京东云技术团队

作者&#xff1a;京东零售 杨秀竹 pnpm 是什么 pnpm&#xff08; performant npm &#xff09;指的是高性能的 npm&#xff0c;与 npm 和 yarn 一样是一款包管理工具&#xff0c;其根据自身独特的包管理方法解决了 npm、yarn 内部潜在的安全及性能问题&#xff0c;在多数情况…

SQL 常用函数总结(二)

字符串处理函数 1. CONCAT() 函数功能&#xff1a;将两个或多个字符串合并成一个字符串。 函数语法&#xff1a; CONCAT(string1, string2, ...)string1、string2 等的数量可以是零个或多个&#xff0c;分别表示需要合并的字符串。 使用示例&#xff1a; 假设现在有一个名…

软件测试工程师的职业发展方向

一、软件测试工程师大致有4个发展方向: 1 资深软件测试工程师 一般情况&#xff0c;软件测试工程师可分为测试工程师、高级测试工程师和资深测试工程师三个等级。 达到这个水平比较困难&#xff0c;这需要了解很多知识&#xff0c;例如C语言&#xff0c;JAVA语言&#xff0c…

多尺度样本熵

多尺度样本熵及其MATLAB实现方法 随着人们对信号处理技术的不断深入研究和发展&#xff0c;在信号非线性、非高斯的情况下&#xff0c;熵的概念成为一种很重要的测量信号复杂度的度量方式。多尺度熵是指在多个尺度范围内测量信号复杂度的一种方法。本文将介绍多尺度样本熵的概…

什么是前端宏任务,什么又是前端微任务呢?一文读懂前端微任务宏任务。

在前端中&#xff0c;宏任务和微任务是异步任务的两种不同类型。 前端有很多中异步任务类型。 可以分为三类&#xff1a; 宏任务 定时器任务用户交互事件任务&#xff08;鼠标事件、键盘事件&#xff09;网络请求任务I/O操作任务&#xff08;读写文件&#xff09; 微任务 Pro…

TPC 网络通信基础(二)

文件下载利用 tcp原理 Ubuntu 20.04 python3.7 三个python文件 客户端.py 服务器.py 文件.py 客户端充当用户 服务器充当提供下载的服务端 客户端代码&#xff1a; import socketdef main():# 创建套接字tcp_socket socket.socket(socket.AF_INET,socket.SOCKET_…

String StringBuilder常用方法总结

在java中String类不可变的&#xff0c;创建一个String对象后不能更改它的值。所以如果需要对原字符串进行一些改动操作&#xff0c;就需要用StringBuilder类或者StringBuffer类&#xff0c;StringBuilder比StringBuffer更快一些&#xff0c;缺点是StringBuilder不是线程安全的&…

JAVA面试-语法基础- A01

语法基础 面向对象封装继承多态 面向对象 面向对象特性 封装 利用抽象数据类型将数据和基于数据的操作封装在一起&#xff0c;使其构成一个不可分隔的独立实体&#xff0c;数据被保护在抽象数据类型的内部&#xff0c;尽可能的隐藏内部的细节&#xff0c;只保留一些对外的接口…

前端通信-服务端发送事件: SSE(Server-Sent Events)

在日常开发中&#xff0c;我们经常会遇到需要实时获取数据的情况&#xff0c;之前实现这种相似的功能通常都是用ajax长轮询&#xff0c;在HTML5规范中定义了新的通信方式&#xff0c;WebSocket和SSE。websocket相对SSE更常用一些&#xff0c;本文着重来介绍SSE的应用。 SSE AP…

滨州申请专利需要准备哪些材料?

如果你想保护你的一些发明和设计&#xff0c;你可以申请专利。申请专利时&#xff0c;需要提前了解程序和相关流程。那么&#xff0c;申请专利需要准备哪些材料呢&#xff1f;让我们一起仔细看看。 首先&#xff0c;申请专利需要准备哪些材料&#xff1f; (1)外观专利&#xff…

C++学习 Day14

目录 1. 泛型编程 2. 函数模板 2.1 函数模板概念 2.2 函数模板格式 2.3 函数模板的原理 2.4 函数模板的实例化 2.5 模板参数的匹配原则 3. 类模板 3.1 类模板的定义格式 3.2 类模板的实例化 1. 泛型编程 如何实现一个通用的交换函数呢&#xff1f; void Swap(int&a…

德尔玛IPO首日破发,市值蒸发超4亿

今日&#xff08;5月18日&#xff09;&#xff0c;小米“代工厂”广东德尔玛科技股份有限公司&#xff08;下称“德尔玛”&#xff0c;301332.SZ&#xff09;正式在深交所挂牌上市。 德尔玛此次IPO募资净额为12.31亿元&#xff0c;开盘价为14.81元/股&#xff0c;与发行价持平…

【Linux内核解析-linux-5.14.10】文件系统知识点以及解答(建议收藏)

什么是Linux文件系统&#xff1f; 答&#xff1a;Linux文件系统是一种用于管理和组织计算机上数据的方法。它提供了一个层次结构&#xff0c;使用户能够轻松地访问他们的数据&#xff0c;并且支持对数据进行备份、恢复和保护。 Linux中有哪些常见的文件系统类型&#xff1f; 答…

使用 SpringBoot 访问 MySQL 数据库

一、目标 创建一个 MySQL 数据库&#xff0c;构建一个 Spring 应用程序&#xff0c;并将其连接到新创建的数据库。 二、准备工作 1、最喜欢的文本编辑器或 IDE 2、Java 17或更高版本 3、Gradle 7.5或Maven 3.5 三、初始化项目 1、 导航到https://start.spring.io。该服务…

HTTPTomcatServlet学习

HTTP&Tomcat 今日目标&#xff1a; 了解JavaWeb开发的技术栈理解HTTP协议和HTTP请求与响应数据的格式掌握Tomcat的使用掌握在IDEA中使用Tomcat插件理解Servlet的执行流程和生命周期掌握Servlet的使用和相关配置 1. Web概述 1.1 Web和JavaWeb的概念 Web是全球广域网&…

freeswitch的2833和inband对接方案

概述 freeswitch支持三种模式的DTMF传输方式&#xff0c;分别时inband、INFO、2833。 在传统的PSTN网络中&#xff0c;所有的DTMF码都是inband模式&#xff0c;所以VOIP网络和PSTN网络对接中&#xff0c;需要将DTMF码做格式转换&#xff0c;通常是2833和inband之间的转换。 …

Makefile 简易教程

如果你是命令行重度使用者&#xff0c;学习 Makefile 将可以大大提高你的开发效率&#xff0c;下面简单介绍一下 Makefile 的知识和使用方式。 Makefile 是一种包含一组指令来编译和构建软件项目的文件。 Makefile 文件通常包含一组规则和依赖关系&#xff0c;以指定如何将源…

Netty核心组件模块(一)

1.Bootstrap和ServerBootstrap 1>.Bootstrap意思是引导,一个Netty应用通常由一个Bootstrap开始,主要作用是配置整个Netty程序,串联各个组件,Netty中Bootstrap类是客户端程序的启动引导类,ServerBootstrap是服务端启动引导类; 2>.常见的方法有: ①.public ServerBootstr…

【笔试强训选择题】Day13.习题(错题)解析

作者简介&#xff1a;大家好&#xff0c;我是未央&#xff1b; 博客首页&#xff1a;未央.303 系列专栏&#xff1a;笔试强训选择题 每日一句&#xff1a;人的一生&#xff0c;可以有所作为的时机只有一次&#xff0c;那就是现在&#xff01;&#xff01;&#xff01; 文章目录…

spring项目里的大事务优化

编程型事务更加灵活 声明式事务只需要加在方法头加Transactional注解即可开启事务&#xff0c;但是还是不太灵活&#xff0c;意味着整个方法所进行对数据库操作都要加进事务&#xff0c;当然一次查询也要进入事务&#xff0c;这并不是我们想要的&#xff0c;我们在update、ins…