当前位置: 首页 > 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;默认不支持富文本。 …...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...