【数据结构-红黑树】
文章目录
- 红黑树
- 红黑树介绍
- 红黑树的五个基本性质
- 红黑树的平衡原理
- 红黑树的操作
- 红黑树的操作
- 代码实现
- 节点实现
- 插入和查询操作
红黑树
红黑树介绍

红黑树(Red-Black Tree)是一种自平衡的二叉查找树(Binary Search Tree, BST),它在普通二叉查找树的基础上增加了一些额外的约束条件,以确保树的平衡性,从而保证在最坏情况下插入、删除和查找操作的时间复杂度为 O(logn)。
红黑树的五个基本性质
红黑树是一种特殊的二叉查找树,它满足以下五个基本性质:
1.节点是红色或黑色,每个节点都有一个颜色属性,红色或黑色。
2.根节点必须是黑色
3.叶子节点(即空节点或 null)是黑色。
4.如果一个节点是红色,则它的两个子节点都是黑色。换句话说,红色节点不能连续出现。
5.从任意节点到其每个叶子节点的所有路径上,黑色节点的数量相同。这一性质确保了树的平衡性。
红黑树的平衡原理
红黑树通过上述性质来保证树的平衡。虽然红黑树不是完全平衡的二叉树,但它能够保证最长路径和最短路径的长度不会相差太大。具体来说,红黑树的最长路径不会超过最短路径的两倍,从而保证了树的近似平衡。
红黑树的操作
红黑树的主要操作包括插入、删除和查找。这些操作在普通二叉查找树的基础上增加了颜色调整和旋转操作,以确保树的平衡。
红黑树的操作
红黑树的主要操作包括插入、删除和查找。这些操作在普通二叉查找树的基础上增加了颜色调整和旋转操作,以确保树的平衡。
插入操作
插入新节点:将新节点插入到树中,新节点默认为红色。
修复树的性质:插入后可能违反红黑树的性质,需要通过以下操作修复:
颜色翻转:改变节点的颜色。
旋转操作:包括左旋和右旋,调整树的结构。
删除操作
删除节点:删除目标节点。
修复树的性质:删除后可能违反红黑树的性质,需要通过以下操作修复:
颜色调整:改变节点的颜色。
旋转操作:调整树的结构。
查找操作
查找操作与普通二叉查找树相同,从根节点开始,根据键值的大小关系逐层向下查找,直到找到目标节点或到达叶子节点。
代码实现
节点实现
class Node<K extends Comparable<K>, V> {K key;V value;Node<K, V> left, right, parent;boolean color; // true 表示红色,false 表示黑色public Node(K key, V value) {this.key = key;this.value = value;this.color = true; // 新节点默认为红色}
}
插入和查询操作
public class RedBlackTree<K extends Comparable<K>, V> {private Node<K, V> root;// 插入操作public void insert(K key, V value) {root = insert(root, key, value);root.color = false; // 根节点必须是黑色}private Node<K, V> insert(Node<K, V> node, K key, V value) {if (node == null) {return new Node<>(key, value);}if (key.compareTo(node.key) < 0) {node.left = insert(node.left, key, value);node.left.parent = node;} else if (key.compareTo(node.key) > 0) {node.right = insert(node.right, key, value);node.right.parent = node;} else {node.value = value; // 如果键已存在,更新值}// 修复红黑树性质return fixAfterInsertion(node);}// 修复插入后的红黑树性质private Node<K, V> fixAfterInsertion(Node<K, V> node) {while (node != null && node != root && node.parent.color) {if (node.parent == node.parent.parent.left) {Node<K, V> uncle = node.parent.parent.right;if (uncle != null && uncle.color) {// 情况1:叔叔节点是红色node.parent.color = false;uncle.color = false;node.parent.parent.color = true;node = node.parent.parent;} else {if (node == node.parent.right) {// 情况2:右倾,先左旋node = node.parent;rotateLeft(node);}// 情况3:左倾,右旋node.parent.color = false;node.parent.parent.color = true;rotateRight(node.parent.parent);}} else {Node<K, V> uncle = node.parent.parent.left;if (uncle != null && uncle.color) {// 情况1:叔叔节点是红色node.parent.color = false;uncle.color = false;node.parent.parent.color = true;node = node.parent.parent;} else {if (node == node.parent.left) {// 情况2:左倾,先右旋node = node.parent;rotateRight(node);}// 情况3:右倾,左旋node.parent.color = false;node.parent.parent.color = true;rotateLeft(node.parent.parent);}}}return node;}// 左旋操作private void rotateLeft(Node<K, V> x) {Node<K, V> y = x.right;x.right = y.left;if (y.left != null) {y.left.parent = x;}y.parent = x.parent;if (x.parent == null) {root = y;} else if (x == x.parent.left) {x.parent.left = y;} else {x.parent.right = y;}y.left = x;x.parent = y;}// 右旋操作private void rotateRight(Node<K, V> x) {Node<K, V> y = x.left;x.left = y.right;if (y.right != null) {y.right.parent = x;}y.parent = x.parent;if (x.parent == null) {root = y;} else if (x == x.parent.right) {x.parent.right = y;} else {x.parent.left = y;}y.right = x;x.parent = y;}// 查找操作public V get(K key) {Node<K, V> node = root;while (node != null) {int cmp = key.compareTo(node.key);if (cmp < 0) {node = node.left;} else if (cmp > 0) {node = node.right;} else {return node.value;}}return null;}
}
代码说明
节点定义:
每个节点包含键、值、左右子节点和父节点指针,以及一个颜色属性(红色或黑色)。
插入操作:
插入新节点时,新节点默认为红色。
插入后调用 fixAfterInsertion 方法修复红黑树的性质。
修复逻辑:
根据红黑树的性质,修复插入操作可能破坏的平衡。
主要处理以下几种情况:
叔叔节点是红色:将父节点和叔叔节点改为黑色,祖父节点改为红色,继续向上检查。
叔叔节点是黑色:根据节点的位置进行旋转操作,调整树的结构。
旋转操作:
左旋:将右子节点提升为新的根节点,调整子树的连接关系。
右旋:将左子节点提升为新的根节点,调整子树的连接关系。
查找操作:
从根节点开始,根据键值的大小关系逐层向下查找,直到找到目标节点或到达叶子节点。
相关文章:
【数据结构-红黑树】
文章目录 红黑树红黑树介绍红黑树的五个基本性质红黑树的平衡原理红黑树的操作红黑树的操作 代码实现节点实现插入和查询操作 红黑树 红黑树介绍 红黑树(Red-Black Tree)是一种自平衡的二叉查找树(Binary Search Tree, BST)&…...
【STM32】舵机SG90
1.舵机原理 舵机内部有一个电位器,当转轴随电机旋转,电位器的电压会发生改变,电压会带动转一定的角度,舵机中的控制板就会电位器输出的电压所代表的角度,与输入的PWM所代表的角度进行比较,从而得出一个旋转…...
【Linux】Socket编程—TCP
🔥 个人主页:大耳朵土土垚 🔥 所属专栏:Linux系统编程 这里将会不定期更新有关Linux的内容,欢迎大家点赞,收藏,评论🥳🥳🎉🎉🎉 文章目…...
c++11 for auto不定参数
数量不定的模板参数。参数分为一个和一包两部分。 冒号的左边声明一个变量。右手边必须是一个容器。从容器(某种数据结构)中找出每一个元素设置到左边这个变量。11之前可以用容器的迭代器去取数据。或者标准库里的foreach...
C#+redis实现消息队列的发布订阅功能
代码 参考c#redis stream实现消息队列以及ack机制文章的思路,实现 SubscribeAttribute.cs using System;namespace DotnetQueue.Attributes {/// <summary>/// 订阅特性/// </summary>[AttributeUsage(AttributeTargets.Method, Inherited false)]pu…...
Docker容器基本操作
容器的基本操作 操作命令(全)命令(简)容器的创建docker container run <image name>docker run <image name>容器的列出(up)docker container lsdocker ps容器的列出(up和exit&…...
从无序到有序:上北智信通过深度数据分析改善会议室资源配置
当前企业普遍面临会议室资源管理难题,预约机制不完善和临时会议多导致资源调度不合理,既有空置又有过度拥挤现象。 针对上述问题,上北智信采用了专业数据分析手段,巧妙融合楼层平面图、环形图、折线图和柱形图等多种可视化工具&a…...
总结:使用JDK原生HttpsURLConnection,封装HttpsUtil工具类,加载自定义证书验证,忽略ssl证书验证
总结:使用JDK原生HttpsURLConnection,封装HttpsUtil工具类,加载自定义证书验证,忽略ssl证书验证 一HttpsUtil工具类二SSLUtil工具类 一HttpsUtil工具类 package com.example.util;import javax.net.ssl.HttpsURLConnection; impo…...
重新定义人机关系边界,Soul以AI社交构建多元社交元宇宙
近年来,AI Native应用的兴起已逐渐成为大众关注的焦点。在此背景下,Soul App的首席技术官陶明在极客公园IF2025创新大会上,发表了一场主题为“人机关系的新边界,Soul如何定义AI社交未来”的演讲。他分享了Soul在人工智能领域内的最新技术进展和战略规划,同时也将Soul社交元宇宙…...
HTTP 参数污染(HPP)详解
1. 什么是 HTTP 参数污染(HPP)? HTTP 参数污染(HTTP Parameter Pollution,简称 HPP)是一种 Web 应用攻击技术,攻击者通过在 HTTP 请求中注入多个相同的参数来绕过安全控制或篡改应用逻辑&#…...
阿里云轻量服务器docker部署nginx
拉取nginx docker镜像 sudo docker pull nginx创建以下挂载目录及文件 用户目录下:conf html logs conf: conf.d nginx.conf html: index.html conf.d: default.confnginx.conf添加文件内容 events {worker_connections 1024; }http {include /etc/ngi…...
(萌新入门)如何从起步阶段开始学习STM32 —— 我应该学习HAL库还是寄存器库?
概念 笔者下面需要介绍的是库寄存器和HAL库两个重要的概念,在各位看完之后,需要决定自己的学习路线到底是学习HAL呢?还是寄存器呢?还是两者都学习呢? 库寄存器 库寄存器就是简单的封装了我们对寄存器的操作…...
Windchill开发-电子仓相关对象信息查询SQL
电子仓相关对象信息查询SQL 一、说明二、数据表信息三、数据表字段说明3.1 HOLDERTOCONTENT3.1.1 对象类型3.1.2 存储类型 3.2 APPLICATIONDATA3.2.1 类别3.2.2 与对象的角色关系3.2.3 存储方式3.2.4 其他字段 3.3 URLDATA3.4 STREAMDATA3.5 FVITEM3.6 FVMOUNT3.6.1 安装状态3.…...
MySQL 数据库定时任务及进阶学习
一、引言 在当今数字化时代,数据管理的高效性和自动化至关重要。MySQL 作为一款广泛应用的开源关系型数据库管理系统,提供了强大的功能来满足各种数据处理需求。其中,定时任务执行功能对于自动化数据操作、维护数据完整性以及优化系统性能具…...
DeepSeek教unity------MessagePack-01
中文:GitCode - 全球开发者的开源社区,开源代码托管平台 MessagePack是C# 的极速 MessagePack 序列化器。它比 MsgPack-Cli 快 10 倍,并且性能超过其他 C# 序列化器。MessagePack for C# 还内置支持 LZ4 压缩——一种极其快速的压缩算法。性能在诸如游戏…...
知识拓展:Python序列化模块 marshal 模块详解
Python marshal 模块学习笔记 1. 简介 marshal 是 Python 的内部序列化格式,主要用于序列化和反序列化 Python 对象。它是 Python 字节码(.pyc文件)使用的序列化格式,比 pickle 更原始和受限,但也更快速和安全。 http…...
leetcode 2684. 矩阵中移动的最大次数
题目如下 数据范围 本题使用常规动态规划就行,不过要注意由于有三个转移的方向,所以我们对dp数组的遍历应该是从上到下 从左到右即按列优先遍历。通过代码 class Solution { public:int maxMoves(vector<vector<int>>& grid) {int …...
机械学习基础-6.更多分类-数据建模与机械智能课程自留
data modeling and machine intelligence - FURTHER CLASSIFICATION 混淆矩阵评估指标:灵敏度和特异度ROC 曲线文字说明部分 AUC:ROC曲线下面积 支持向量机思路补充背景知识点积超平面(HYPERPLANES超平面的法向量到超平面的最小距离数据集与超…...
自动化测试实战
http://8.137.19.140:9090/blog_login.htm 账号: lisi 密码: 123456 上面是系统链接 1. 自动化测试的步骤 1.1 编写Web测试用例 1.2 创建空项目添加依赖 然后我们创建一个新的java项目(使用maven管理),然后引入我们的配置文件:屏幕截图,驱动管理,selenium库 <dependency…...
qt QPlainTextEdit总结
QPlainTextEdit 概述 用途:专为处理纯文本设计,适合大文本编辑和简单文本显示(如日志、代码编辑器)。 特点:相比QTextEdit,轻量高效,支持快速加载和滚动大文件,默认不支持富文本。 …...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
Xcode 16 集成 cocoapods 报错
基于 Xcode 16 新建工程项目,集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...
拟合问题处理
在机器学习中,核心任务通常围绕模型训练和性能提升展开,但你提到的 “优化训练数据解决过拟合” 和 “提升泛化性能解决欠拟合” 需要结合更准确的概念进行梳理。以下是对机器学习核心任务的系统复习和修正: 一、机器学习的核心任务框架 机…...
C++ 类基础:封装、继承、多态与多线程模板实现
前言 C 是一门强大的面向对象编程语言,而类(Class)作为其核心特性之一,是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性,包括封装、继承和多态,同时讨论类中的权限控制,并展示如何使用类…...
