当前位置: 首页 > news >正文

【数据结构-红黑树】

文章目录

  • 红黑树
    • 红黑树介绍
    • 红黑树的五个基本性质
    • 红黑树的平衡原理
    • 红黑树的操作
    • 红黑树的操作
  • 代码实现
    • 节点实现
    • 插入和查询操作

红黑树

红黑树介绍

在这里插入图片描述

红黑树(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 方法修复红黑树的性质。
修复逻辑:
根据红黑树的性质,修复插入操作可能破坏的平衡。
主要处理以下几种情况:
叔叔节点是红色:将父节点和叔叔节点改为黑色,祖父节点改为红色,继续向上检查。
叔叔节点是黑色:根据节点的位置进行旋转操作,调整树的结构。
旋转操作:
左旋:将右子节点提升为新的根节点,调整子树的连接关系。
右旋:将左子节点提升为新的根节点,调整子树的连接关系。
查找操作:
从根节点开始,根据键值的大小关系逐层向下查找,直到找到目标节点或到达叶子节点。

相关文章:

【数据结构-红黑树】

文章目录 红黑树红黑树介绍红黑树的五个基本性质红黑树的平衡原理红黑树的操作红黑树的操作 代码实现节点实现插入和查询操作 红黑树 红黑树介绍 红黑树&#xff08;Red-Black Tree&#xff09;是一种自平衡的二叉查找树&#xff08;Binary Search Tree, BST&#xff09;&…...

【STM32】舵机SG90

1.舵机原理 舵机内部有一个电位器&#xff0c;当转轴随电机旋转&#xff0c;电位器的电压会发生改变&#xff0c;电压会带动转一定的角度&#xff0c;舵机中的控制板就会电位器输出的电压所代表的角度&#xff0c;与输入的PWM所代表的角度进行比较&#xff0c;从而得出一个旋转…...

【Linux】Socket编程—TCP

&#x1f525; 个人主页&#xff1a;大耳朵土土垚 &#x1f525; 所属专栏&#xff1a;Linux系统编程 这里将会不定期更新有关Linux的内容&#xff0c;欢迎大家点赞&#xff0c;收藏&#xff0c;评论&#x1f973;&#x1f973;&#x1f389;&#x1f389;&#x1f389; 文章目…...

c++11 for auto不定参数

数量不定的模板参数。参数分为一个和一包两部分。 ​ 冒号的左边声明一个变量。右手边必须是一个容器。从容器(某种数据结构)中找出每一个元素设置到左边这个变量。11之前可以用容器的迭代器去取数据。或者标准库里的foreach...

C#+redis实现消息队列的发布订阅功能

代码 参考c#redis stream实现消息队列以及ack机制文章的思路&#xff0c;实现 SubscribeAttribute.cs using System;namespace DotnetQueue.Attributes {/// <summary>/// 订阅特性/// </summary>[AttributeUsage(AttributeTargets.Method, Inherited false)]pu…...

Docker容器基本操作

容器的基本操作 操作命令&#xff08;全&#xff09;命令&#xff08;简&#xff09;容器的创建docker container run <image name>docker run <image name>容器的列出&#xff08;up&#xff09;docker container lsdocker ps容器的列出&#xff08;up和exit&…...

从无序到有序:上北智信通过深度数据分析改善会议室资源配置

当前企业普遍面临会议室资源管理难题&#xff0c;预约机制不完善和临时会议多导致资源调度不合理&#xff0c;既有空置又有过度拥挤现象。 针对上述问题&#xff0c;上北智信采用了专业数据分析手段&#xff0c;巧妙融合楼层平面图、环形图、折线图和柱形图等多种可视化工具&a…...

总结:使用JDK原生HttpsURLConnection,封装HttpsUtil工具类,加载自定义证书验证,忽略ssl证书验证

总结&#xff1a;使用JDK原生HttpsURLConnection&#xff0c;封装HttpsUtil工具类&#xff0c;加载自定义证书验证&#xff0c;忽略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 参数污染&#xff08;HPP&#xff09;&#xff1f; HTTP 参数污染&#xff08;HTTP Parameter Pollution&#xff0c;简称 HPP&#xff09;是一种 Web 应用攻击技术&#xff0c;攻击者通过在 HTTP 请求中注入多个相同的参数来绕过安全控制或篡改应用逻辑&#…...

阿里云轻量服务器docker部署nginx

拉取nginx docker镜像 sudo docker pull nginx创建以下挂载目录及文件 用户目录下&#xff1a;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库两个重要的概念&#xff0c;在各位看完之后&#xff0c;需要决定自己的学习路线到底是学习HAL呢&#xff1f;还是寄存器呢&#xff1f;还是两者都学习呢&#xff1f; 库寄存器 库寄存器就是简单的封装了我们对寄存器的操作&#xf…...

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 数据库定时任务及进阶学习

一、引言 在当今数字化时代&#xff0c;数据管理的高效性和自动化至关重要。MySQL 作为一款广泛应用的开源关系型数据库管理系统&#xff0c;提供了强大的功能来满足各种数据处理需求。其中&#xff0c;定时任务执行功能对于自动化数据操作、维护数据完整性以及优化系统性能具…...

DeepSeek教unity------MessagePack-01

中文&#xff1a;GitCode - 全球开发者的开源社区,开源代码托管平台 MessagePack是C# 的极速 MessagePack 序列化器。它比 MsgPack-Cli 快 10 倍&#xff0c;并且性能超过其他 C# 序列化器。MessagePack for C# 还内置支持 LZ4 压缩——一种极其快速的压缩算法。性能在诸如游戏…...

知识拓展:Python序列化模块 marshal 模块详解

Python marshal 模块学习笔记 1. 简介 marshal 是 Python 的内部序列化格式&#xff0c;主要用于序列化和反序列化 Python 对象。它是 Python 字节码&#xff08;.pyc文件&#xff09;使用的序列化格式&#xff0c;比 pickle 更原始和受限&#xff0c;但也更快速和安全。 http…...

leetcode 2684. 矩阵中移动的最大次数

题目如下 数据范围 本题使用常规动态规划就行&#xff0c;不过要注意由于有三个转移的方向&#xff0c;所以我们对dp数组的遍历应该是从上到下 从左到右即按列优先遍历。通过代码 class Solution { public:int maxMoves(vector<vector<int>>& grid) {int …...

机械学习基础-6.更多分类-数据建模与机械智能课程自留

data modeling and machine intelligence - FURTHER CLASSIFICATION 混淆矩阵评估指标&#xff1a;灵敏度和特异度ROC 曲线文字说明部分 AUC&#xff1a;ROC曲线下面积 支持向量机思路补充背景知识点积超平面&#xff08;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 概述 用途&#xff1a;专为处理纯文本设计&#xff0c;适合大文本编辑和简单文本显示&#xff08;如日志、代码编辑器&#xff09;。 特点&#xff1a;相比QTextEdit&#xff0c;轻量高效&#xff0c;支持快速加载和滚动大文件&#xff0c;默认不支持富文本。 …...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

JS红宝书笔记 - 3.3 变量

要定义变量&#xff0c;可以使用var操作符&#xff0c;后跟变量名 ES实现变量初始化&#xff0c;因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符&#xff0c;可以创建一个全局变量 如果需要定义…...