Java数据结构与算法(红黑树)
前言
红黑树是一种自平衡二叉搜索树,确保在插入和删除操作后,树的高度保持平衡,从而保证基本操作(插入、删除、查找)的时间复杂度为O(log n)。
实现原理
红黑树具有以下性质:
- 每个节点要么是红色,要么是黑色。
- 根节点是黑色的。
- 每个叶子节点(NIL节点,通常是空节点)是黑色的。
- 如果一个节点是红色的,则它的两个子节点都是黑色的。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
动画过程
Red/Black Tree Visualization
具体代码实现
public class RedBlackTree {private static final boolean RED = false;private static final boolean BLACK = true;private class Node {int key;Node left, right, parent;boolean color;Node(int key, boolean color, Node parent) {this.key = key;this.color = color;this.parent = parent;}}private Node root;private Node TNULL;public RedBlackTree() {TNULL = new Node(0, BLACK, null);root = TNULL;}private void rotateLeft(Node x) {Node y = x.right;x.right = y.left;if (y.left != TNULL) {y.left.parent = x;}y.parent = x.parent;if (x.parent == null) {this.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 x) {Node y = x.left;x.left = y.right;if (y.right != TNULL) {y.right.parent = x;}y.parent = x.parent;if (x.parent == null) {this.root = y;} else if (x == x.parent.right) {x.parent.right = y;}y.right = x;x.parent = y;}private void insertFix(Node k) {Node u;while (k.parent.color == RED) {if (k.parent == k.parent.parent.left) {u = k.parent.parent.right;if (u.color == RED) {u.color = BLACK;k.parent.color = BLACK;k.parent.parent.color = RED;k = k.parent.parent;} else {if (k == k.parent.right) {k = k.parent;rotateLeft(k);}k.parent.color = BLACK;k.parent.parent.color = RED;rotateRight(k.parent.parent);}} else {u = k.parent.parent.left;if (u.color == RED) {u.color = BLACK;k.parent.color = BLACK;k.parent.parent.color = RED;k = k.parent.parent;} else {if (k == k.parent.left) {k = k.parent;rotateRight(k);}k.parent.color = BLACK;k.parent.parent.color = RED;rotateLeft(k.parent.parent);}}if (k == root) {break;}}root.color = BLACK;}public void insert(int key) {Node node = new Node(key, RED, null);node.left = TNULL;node.right = TNULL;Node y = null;Node x = this.root;while (x != TNULL) {y = x;if (node.key < x.key) {x = x.left;} else {x = x.right;}}node.parent = y;if (y == null) {root = node;} else if (node.key < y.key) {y.left = node;} else {y.right = node;}if (node.parent == null) {node.color = BLACK;return;}if (node.parent.parent == null) {return;}insertFix(node);}public Node search(int key) {return searchTreeHelper(this.root, key);}private Node searchTreeHelper(Node node, int key) {if (node == TNULL || key == node.key) {return node;}if (key < node.key) {return searchTreeHelper(node.left, key);}return searchTreeHelper(node.right, key);}public void printTree() {printHelper(this.root, "", true);}private void printHelper(Node root, String indent, boolean last) {if (root != TNULL) {System.out.print(indent);if (last) {System.out.print("R----");indent += " ";} else {System.out.print("L----");indent += "| ";}String sColor = root.color == RED ? "RED" : "BLACK";System.out.println(root.key + "(" + sColor + ")");printHelper(root.left, indent, false);printHelper(root.right, indent, true);}}public static void main(String[] args) {RedBlackTree tree = new RedBlackTree();tree.insert(55);tree.insert(40);tree.insert(65);tree.insert(60);tree.insert(75);tree.insert(57);tree.printTree();}
}
QA:待定
相关文章:
Java数据结构与算法(红黑树)
前言 红黑树是一种自平衡二叉搜索树,确保在插入和删除操作后,树的高度保持平衡,从而保证基本操作(插入、删除、查找)的时间复杂度为O(log n)。 实现原理 红黑树具有以下性质: 每个节点要么是红色&#…...
SpringBoot RPM制作
安装依赖 [root20240423-instance4 ~]# yum install rpmdevtools2.初始化目录 [root20240423-instance4 ~]# rpmdev-setuptree [root20240423-instance4 ~]# tree rpmbuild/ rpmbuild/ ├── BUILD ├── RPMS ├── SOURCES ├── SPECS └── SRPMS5 directories, 0 …...
专转本上岸别太老实做这三件事
如果你专转本上岸,千万不要当老实人去做这三件事,真的没有必要,不但浪费时间,还会让你提前进入对未来的迷茫期。建议转本人们一定要知道,首先就是不要过度关注学分。因为转本上岸只有两年,我们属于大三&…...
Cisco网络工程师和网络安全视频教程(完整版)
0001.IT技术包括的技能 0002.课程目标.mp4 0003.Internet示意图.m 0004.局域网和广域网区 0005.服务器客户机mp4 0006.应用层和表示层.m.. 0007.会话层.mp4 0008.传输层.mp4 0009.网络层数据链路层 0010.OSI参考模型和网 0011.普换法排错.mp4 0012.OSI参考模型和网. 0013.网线和…...
如何在一个 JavaScript 文件中引入另一个 JavaScript 文件
在早期版本的 JavaScript 中,没有提供原生的模块导入功能,因此开发者们尝试过各种不同的方法来解决这个问题。然而,自 2015 年 (ES6) 以来,JavaScript 引入了 ES6 模块标准,这使得在 Node.js 中导入模块变得更加规范。现代浏览器也广泛支持这一标准。 为了与旧版浏览器兼…...
2024最新 Jenkins + Docker实战教程(七)- Jenkins实现远程传输和自动部署
😄 19年之后由于某些原因断更了三年,23年重新扬帆起航,推出更多优质博文,希望大家多多支持~ 🌷 古之立大事者,不惟有超世之才,亦必有坚忍不拔之志 🎐 个人CSND主页——Mi…...
WWW24因果论文(1/8) | 利用强化学习(智能体)进行因果问答
【摘要】因果问题询问不同事件或现象之间的因果关系。它们对于各种用例都很重要,包括虚拟助手和搜索引擎。然而,许多当前的因果问答方法无法为其答案提供解释或证据。因此,在本文中,我们旨在使用因果关系图来回答因果问题…...
比较kube-proxy模式:iptables还是IPVS?
kube-proxy是任何 Kubernetes 部署中的关键组件。它的作用是将流向服务(通过集群 IP 和节点端口)的流量负载均衡到正确的后端pod。kube-proxy可以运行在三种模式之一,每种模式都使用不同的数据平面技术来实现:userspace、iptables…...
CSS:浮动
▐ 文档流: 由于网页默认是一个二维平面,当我们在网页中一行行摆放标签时,块标签会独占一行,行标签则只占自身大小,这种情况下要实现网页布局就很麻烦了,所以我们就需要通过一些方法来改变这种默认的布局方…...
SQL 语言:嵌入式 SQL 和动态 SQL
文章目录 基本概述嵌入式 SQL动态 SQL总结 基本概述 嵌入式SQL和动态SQL是两种在应用程序中嵌入和使用SQL语句的方法。它们都允许开发人员在编程语言中编写SQL语句,以便在应用程序中执行数据库操作。然而,这两种方法在实现方式、性能和灵活性方面存在一…...
Java Object类方法介绍
Object作为顶级类,所有的类都实现了该类的方法,包括数组。 查询Java文档: 1、object.eauqls(): 其作用与 有些类似。 : 是一个比较运算符,而不是一个方法。 ①可以判断基本类型,也可以判断引用类型。 ②若…...
2024 京麟ctf -MazeCodeV1
文章目录 检查代码思路一个字节的指令注意附上S1uM4i佬们的exp https://www.ctfiot.com/184181.html 检查 代码 __int64 __fastcall check_solve(char *a1) {__int64 result; // rax__int64 v2; // rax__int64 index_step; // rax__int64 v4; // rax__int64 v5; // rax__int64…...
计算机网络基础 - 计算机网络和因特网(1)
计算机网络基础 计算机网络和因特网什么是 Internet?具体构造的的角度服务角度网络结构 网络边缘网络核心电路交换分组交换概述排队时延和分组丢失转发表和路由选择协议按照有无网络层的连接 分组交换 VS 电路交换 接入网DSL 因特网接入电缆因特网接入光纤到户 FTTH无线接入网…...
自学动态规划——零钱兑换
零钱兑换 322. 零钱兑换 - 力扣(LeetCode) 注意几个关键的地方: 因为每次都是找min,所以我们不能将所有元素都初始化为0,不然最后结果一定是0,这里我设置为0x3f3f3f3f,表示无解。当amount0的…...
kafka单机安装及性能测试
kafka单机安装及性能测试 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,并于2011年开源,随后成为Apache项目。Kafka的核心概念包括发布-订阅消息系统、持久化日志和流处理平台。它主要用于构建实时数据管道和流处理应用ÿ…...
2024.05.29学习记录
1、css面经复习 2、代码随想录二刷 3、rosebush upload组件初步完成...
6.10 Libbpf-bootstrap(一,简介)
写在前面 在看完前面的介绍,是不是感觉看了也就看了。但是,如果想要像BCC那样使用libbpf编写BPF程序,该怎么开始呢? 那么这就需要libbpf-bootstrap了。 libbpf-bootstrap是官方推荐的一个范式,就像我们写PPT的模版。简单来说可以简化我们的BPF开发流程,它可以帮助我们…...
2.1.2 基于配置方式使用MyBatis
文章目录 实战目标实战步骤1. 创建Maven项目2. 添加项目依赖3. 创建用户实体类4. 创建用户映射器配置文件5. 创建MyBatis配置文件6. 创建日志属性文件7. 测试用户操作8. 运行测试方法 预期结果实战方法结论 实战目标 本实战的目标是演示如何使用MyBatis框架来操作数据库。通过…...
使用NuScenes数据集生成ROS Bag文件:深度学习与机器人操作的桥梁
在自动驾驶、机器人导航及环境感知的研究中,高质量的数据集是推动算法发展的关键。NuScenes数据集作为一项开源的多模态自动驾驶数据集,提供了丰富的雷达、激光雷达(LiDAR)、摄像头等多种传感器数据,是进行多传感器融合…...
氢燃料电池汽车行业发展
文章目录 前言 市场分布 整车销售 发动机配套 氢气供应 发展动能 参考文献 前言 见《氢燃料电池技术综述》 见《燃料电池工作原理详解》 见《燃料电池发电系统详解》 见《燃料电池电动汽车详解》 市场分布 纵观全球的燃料电池汽车市场,截至2022年底ÿ…...
4个步骤实现跨设备数据同步:开源工具Kazumi的WebDAV集成方案
4个步骤实现跨设备数据同步:开源工具Kazumi的WebDAV集成方案 【免费下载链接】Kazumi 基于自定义规则的番剧采集APP,支持流媒体在线观看,支持弹幕,支持实时超分辨率。 项目地址: https://gitcode.com/gh_mirrors/ka/Kazumi …...
GLM-4.1V-9B-Base实战案例:智能客服知识库图片问答模块集成方案
GLM-4.1V-9B-Base实战案例:智能客服知识库图片问答模块集成方案 1. 项目背景与需求分析 在智能客服系统中,用户经常需要上传产品图片、使用场景截图或问题示意图进行咨询。传统客服系统只能依赖人工处理这类图片咨询,效率低下且成本高昂。G…...
如何在5分钟内开始使用Ivy Wallet:新手入门教程
如何在5分钟内开始使用Ivy Wallet:新手入门教程 【免费下载链接】ivy-wallet Ivy Wallet is an open-source money manager app for android that you can either build or download from Google Play. 项目地址: https://gitcode.com/gh_mirrors/iv/ivy-wallet …...
对于多轮对话中的对话策略优化,OpenClaw 的在线强化学习更新频率?
关于OpenClaw在多轮对话中对话策略的在线强化学习更新频率,其实并没有一个公开的、固定的官方数字。这倒不是因为它是什么秘密,而是因为这类系统的更新机制往往不是按“每隔几秒一次”这样刻板的方式来运作的。它更像是一个动态调整的过程,取…...
鼎捷T100——快速构建简易报表:azzi310与azzi910的高效协作
1. 从零开始:理解鼎捷T100报表开发的核心模块 第一次接触鼎捷T100系统时,我被各种功能模块搞得晕头转向。直到真正用azzi310和azzi910协作完成报表开发,才发现这套组合拳的妙处。简单来说,azzi310就像你的SQL编辑器报表设计器&…...
如何用3dsconv解决3DS游戏格式兼容问题:从入门到精通的转换指南
如何用3dsconv解决3DS游戏格式兼容问题:从入门到精通的转换指南 【免费下载链接】3dsconv Python script to convert Nintendo 3DS CCI (".cci", ".3ds") files to the CIA format 项目地址: https://gitcode.com/gh_mirrors/3d/3dsconv …...
Vue2集成海康摄像头RTSP流:基于FFmpeg转码与WebSocket实时传输方案
1. 海康摄像头RTSP流播放的技术挑战 海康威视作为国内主流监控设备厂商,其摄像头输出的RTSP流在Web端直接播放存在天然技术屏障。浏览器原生不支持RTSP协议,传统方案需要依赖浏览器插件或转码服务。我在实际项目中发现,直接使用VLC测试RTSP流…...
Qwen3-ASR-0.6B与Java集成:企业级语音处理方案
Qwen3-ASR-0.6B与Java集成:企业级语音处理方案 1. 引言 想象一下这样的场景:你的客服中心每天要处理成千上万的电话录音,传统的人工转录不仅成本高昂,还容易出错。或者你的移动应用需要实时语音转文字功能,但现有的云…...
基于历史数据的加密货币交易系统策略验证实践指南
基于历史数据的加密货币交易系统策略验证实践指南 【免费下载链接】node-binance-trader 💰 Cryptocurrency Trading Strategy & Portfolio Management Development Framework for Binance. 🤖 项目地址: https://gitcode.com/gh_mirrors/no/node-…...
如何快速为AMD 780M APU解锁隐藏性能:完整优化教程
如何快速为AMD 780M APU解锁隐藏性能:完整优化教程 【免费下载链接】ROCmLibs-for-gfx1103-AMD780M-APU ROCm Library Files for gfx1103 and update with others arches based on AMD GPUs for use in Windows. 项目地址: https://gitcode.com/gh_mirrors/ro/RO…...
