数据结构-红黑树
1.容器
容器用于容纳元素集合,并对元素集合进行管理和维护.
传统意义上的管理和维护就是:增,删,改,查.
我们分析每种类型容器时,主要分析其增,删,改,查动作实现,及复杂度.
2.红黑树
2.1.结构
2.1.1.图解
红黑树是容器类型.
其元素组织采用二叉树结构.

上图是一个包含五个元素的二叉树.
二叉树容器内元素间具备兄弟,父子关系.这种关系通过每个节点内三个指针来维护,它们是:
(1). 指向节点父节点指针
(2). 指向节点左孩子节点指针
(3). 指向节点右孩子节点指针
为了发挥出这类容器的优势,红黑树在二叉树基础上增加了多个一致性约束.这些一致性约束可分为两种类型.
一种类型为了元素有序,一种类型为了树中任意节点左子树,右子树的高度平衡.
(1). 服务于元素有序的一致性约束
对树中任意节点p.
若p的左孩子节点lp存在,则以lp为根子树中所有节点内元素均小于p节点内元素.
若p的右孩子节点rp存在,则rp为根子树中所有节点内元素均大于p节点内元素.
通过这个一致性约束,我们保证了二叉树的有序性,但这个性质给我们带来的好处是什么呢?
通过该性质,在二叉树中查找元素时候,我们可以运用二分查找加快查找速度.

上述二叉树满足有序的约束.我们若在其中查找值为5的元素.
二分查找过程如下:
(1). 初始查找节点为根节点
(2). 判断当前节点p和5关系.
a. p中元素小于5,由于有序性质,只能将当前节点p设置为p的右孩子继续查找.
b. p中元素大于5,由于有序性质,只能将当前节点p设置为p的左孩子继续查找.
c. p中元素等于5,则找到,停止迭代.
d. p为空指针,查找结束,树中不存在匹配节点.
(2). 服务于树中任意节点左子树,右子树高度平衡的一致性约束.
a. 任意节点需要携带颜色标记,颜色标记要么为红色,要么为黑色.
b. 树的根节点的颜色标记必须为黑色.
c. 对树中任意节点p,若p的父节点pp存在且颜色标记为红色,则p的颜色标记必须为黑色.
d. 对树中任意节点p,p的左子树的黑高和p的右子树的黑高必须一致.

上图是一个包含五个元素的红黑树.
首先,这棵树是一颗二叉树.
然后,这棵树满足有序的一致性约束.
最后,这棵树满足关于高度平衡的一致性约束.
如何确定树的黑高:
由于红黑树一致性约束规定了树中任意节点的左子树,右子树黑高一致.
为了得到树的黑高,我们只需确定一条从根节点到叶子节点的路径,然后统计此路径上颜色标记为黑色的节点个数即可.
通过平衡性的一致性约束,可以带给我们什么好处呢?
给定一个红黑树.
a. 其根节点为p,p的左孩子为lp,p的右孩子为rp.
b. 容器内元素总数为n.
c. 树的黑高为h.
对一个黑高为h的树来说,极端情况下,该树内所有节点颜色标记均为黑色下,该树中的节点数量最少.
由于任意节点左,右子树黑高一致的约束.此时,树中节点全黑的树,只能是一颗满二叉树.
满二叉树下,给定高度h,可以计算树中节点总数= 2 0 2^{0} 20 + 2 1 2^{1} 21 + … + 2 h − 1 2^{h-1} 2h−1= 2 h 2^{h} 2h-1.
这样存在h和n之间存在下面的关系: 2 h 2^{h} 2h-1 <= n
可以简化为h <= log以2为底n+1的对数.
又因为父节点颜色标记为红色,子节点颜色标记必须为黑色的约束.
所以,给定一颗黑高为h的红黑树,从根节点到叶子节点理论上最长的一条路径只能是,路径上交替出现黑色-红色这样的情况.此情况下,理论上根节点到叶子节点最长路径的高度为:2h.
这样,当我们满足平衡约束时,我们获得的好处是:
可以确定根节点到叶子节点最长的一条路径高度小于等于2*log以2为底n+1的对数.
2.1.2.存在一致性约束容器特点
(1). 插入无需提供位置信息.
(2). 不支持直接原地修改.一般分解为移除,添加两个过程.
(3). 由于元素值决定其位置,这类容器一般插入元素时,一般以std::pair<key, value>形式插入.即元素包含键,值两部分.键用来实现一致性约束.值是此键关联的实际内容.
相关文章:
数据结构-红黑树
1.容器 容器用于容纳元素集合,并对元素集合进行管理和维护. 传统意义上的管理和维护就是:增,删,改,查. 我们分析每种类型容器时,主要分析其增,删,改ÿ…...
双指针、bfs与图论
1238. 日志统计 - AcWing题库 import java.util.*;class PII implements Comparable<PII>{int x, y;public PII(int x, int y){this.x x;this.y y;}public int compareTo(PII o){return Integer.compare(x, o.x);} }public class Main{static int N 100010, D, K;st…...
RabbitMQ高级-高级特性
1.消息可靠性传递 在使用RabbitMQ的时候,作为消息发送方希望杜绝任何消息丢失或者投递失败场景。RabbitMQ为我们提供了两种方式来控制消息的投递可靠性模式 1.confirm 确认模式 确认模式是由exchange决定的 2.return 退回模式 回退模式是由routing…...
Word粘贴时出现“运行时错误53,文件未找到:MathPage.WLL“的解决方案
在安装完MathType后,打开word复制粘贴时报错“运行时错误53,文件未找到:MathPage.WLL” 首先确定自己电脑的位数(这里默认32位) 右击MathType桌面图标,点击“打开文件所在位置”, 然后分别找到MathPage.W…...
html元素基本使用
前言 大家好,我是jiantaoyab,第一次学习前端的html,写一篇笔记总结常用的元素 语义化 例如只要是 不管字体的大小是怎么样,有没有加粗都是标题,元素显示到页面中的效果应该由css决定,这就是语义化。 文…...
PHP+golang开源办公系统CRM管理系统
基于ThinkPHP6 Layui MySQL的企业办公系统。集成系统设置、人事管理、消息管理、审批管理、日常办公、客户管理、合同管理、项目管理、财务管理、电销接口集成、在线签章等模块。系统简约,易于功能扩展,方便二次开发。 服务器运行环境要求 PHP > 7.…...
smartmontools-5.43交叉编译Smartctl
嵌入式系统的sata盘经常故障,需要使用smatctl工具监控和诊断sata故障。 1. 从网上下载开源smartmontools-5.43包。 2. 修改makefile进行交叉编译。 由于软件包中已经包含Makefile.am,Makefile.in。直接运行 automake --add-missing 生成Makefile。 3.…...
idea找不到或无法加载主类
前言 今天在运行项目的时候突然出了这样一个错误:IDEA 错误 找不到或无法加载主类,相信只要是用过IDEA的朋友都 遇到过它吧,但是每次遇到都是一顿焦头烂额、抓耳挠腮、急赤白咧!咋整呢?听我给你吹~ 瞧我这张嘴~ 问题报错 找不…...
2.二进制的方式读写文件
文章目录 写入文件代码运行结果 读出文件代码运行结果 文件打开模式标记(查表) 写入文件 ------写文件一共五步:------ 第一步:包含头文件 第二步:创建流对象 第三步:指定方式打开文件 第四步:…...
Seata的详细解释
什么是seata Seata(Simple Extensible Autonomous Transaction Architecture)是一个开源的分布式事务解决方案。它是由阿里巴巴集团开发的,旨在解决分布式系统中的事务一致性问题。 Seata提供了一种简单易用的方式来实现跨多个数据库和服务的…...
JS手写实现洋葱圈模型
解释洋葱圈模型: 当我们执行第一个中间件时,首先输出1,然后调用next(),那么此时它会等第二个中间件执行完毕才会继续执行第一个中间件。然后执行第二个中间件,输出3,调用next(),执行第三中间件…...
3.Windows下安装MongoDB和Compass教程
Windows下安装MongoDB 总体体验下来,,要比MySQL的安装简单了许多,没有过多的配置,直接就上手了! 1、下载 进入官方的下载页面https://www.mongodb.com/try/download/community,如下选择,我选…...
go反射实战
文章目录 demo1 数据类型判断demo2 打印任意类型数据 demo1 数据类型判断 使用reflect.TypeOf()方法打印go中数据类型,可参考go官方API文档;使用格式化参数%T也能打印数据类型。 package mainimport "fmt" import "reflect" import "io&…...
Docker 中 MySQL 的部署与管理
目录 一、Docker 中部署 MySQL1.1 部署 MySQL1.2 进入容器并创建数据库1.3 Navicat 可视化工具连接 二、可能存在的问题2.1 1130 - Host ‘172.17.0.1‘ is not allowed to connect to this MySQL server 参考资料 一、Docker 中部署 MySQL 1.1 部署 MySQL 首先,从…...
基础练习题之函数
前言 这些题目来自与一些刷题网站,以及c primer plus,继续练习 第一题 给你一个数,让他进行巴啦啦能量,沙鲁沙鲁,小魔仙大变身,如果进行变身的数不满足条件的话,就继续让他变身。。。直到满足条件为止。 巴啦啦能量…...
Java NIO浅析
NIO(Non-blocking I/O,在Java领域,也称为New I/O),是一种同步非阻塞的I/O模型,也是I/O多路复用的基础,已经被越来越多地应用到大型应用服务器,成为解决高并发与大量连接、I/O处理问题…...
数据挖掘与大数据的结合
随着大数据技术的不断发展和普及,数据挖掘在大数据环境下的应用也变得更加广泛和深入。以下将探讨大数据技术对数据挖掘的影响,以及如何利用大数据技术处理海量数据并进行有效的数据挖掘,同时分析大数据环境下的数据挖掘挑战和解决方案。 1.…...
分布式链路追踪(一)SkyWalking(2)使用
一、使用方法 1、简介 agent探针可以让我们不修改代码的情况下,对Java应用上使用到的组件进行动态监控,获取运行数据发送到OAP上进行统计和存储。agent探针在Java使用中是使用Java agent技术实现。不需要更改任何代码,Java agent会通过虚拟…...
【QT入门】VS2019+QT的开发环境配置
声明:该专栏为本人学习Qt知识点时候的笔记汇总,希望能给初学的朋友们一点帮助(加油!) 往期回顾: 【QT入门】什么是qt,发展历史,特征,应用,QtCreator-CSDN博客【QT入门】Windows平台下…...
RTP 控制协议 (RTCP) 反馈用于拥塞控制
摘要 有效的 RTP 拥塞控制算法,需要比标准 RTP 控制协议(RTCP)发送方报告(SR)和接收方报告(RR)数据包提供的关于数据包丢失、定时和显式拥塞通知 (ECN) 标记的更细粒度的反馈。 本文档描述了 RTCP 反馈消息,旨在使用 RTP 对交互式实时流量启用拥塞控制…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
