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年底ÿ…...
CMake构建类型避坑指南:为什么你的Release模式没有优化?CMAKE_BUILD_TYPE常见问题排查
CMake构建类型避坑指南:为什么你的Release模式没有优化? 在C项目开发中,构建类型的选择直接影响最终生成的可执行文件性能。许多开发者在使用CMake时都遇到过这样的困惑:明明设置了CMAKE_BUILD_TYPERelease,但生成的代…...
Wan2.2-I2V-A14B实战案例:为本地餐饮店生成15秒抖音爆款菜品视频
Wan2.2-I2V-A14B实战案例:为本地餐饮店生成15秒抖音爆款菜品视频 1. 项目背景与价值 对于本地餐饮商家来说,短视频营销已经成为吸引顾客的重要手段。然而,专业视频制作成本高、周期长,很多小店难以承担。Wan2.2-I2V-A14B文生视频…...
Zotero Citation插件进阶使用指南:从安装到定制的全流程解决方案
Zotero Citation插件进阶使用指南:从安装到定制的全流程解决方案 【免费下载链接】zotero-citation Make Zoteros citation in Word easier and clearer. 项目地址: https://gitcode.com/gh_mirrors/zo/zotero-citation [痛点分析]:文献管理中的隐…...
如何使用usearch构建精准视频内容推荐系统:基于观看历史的向量匹配方案
如何使用usearch构建精准视频内容推荐系统:基于观看历史的向量匹配方案 【免费下载链接】usearch Fast Open-Source Search & Clustering engine for Vectors & Arbitrary Objects in C, C, Python, JavaScript, Rust, Java, Objective-C, Swift, C#, GoL…...
除了阿里云,还有哪些靠谱的身份证实名认证方案?SpringBoot整合横向评测
SpringBoot整合主流身份证实名认证API横向评测:从阿里云到多服务商技术选型指南 当你的应用需要接入身份证实名认证功能时,阿里云可能只是众多选项中的一个起点。作为技术决策者,如何在腾讯云、百度智能云、聚合数据等众多服务商中做出最优选…...
Qt, C++数据类型扩展问题
Qt项目中ObjectDic类的类型扩展与代码优化 前言 在Qt项目开发中,我们经常会遇到需要处理不同类型数据的情况,尤其是当涉及到负数时,类型的选择就显得尤为重要。本文将详细介绍如何在Qt项目中扩展ObjectDic类的类型支持,从无符号整…...
基于机器学习的驾驶疲劳检测,应该如何入门?
基于机器学习的驾驶疲劳检测可以说是本科/硕士毕设中性价比很高的一个题目:它既有充足的开源参考资料,又容易做出可视化的Demo,答辩时也比较讨喜。 我来帮你把这个看似庞大的项目拆解成流水线。 你不需要去手搓底层的神经网络,只…...
CCF和中国科协对NeurIPS更正投稿政策做出回应
点击下方卡片,关注“CVer”公众号AI/CV重磅干货,第一时间送达点击进入—>【顶会/顶刊】投稿交流群添加微信号:CVer2233,小助手拉你进群!扫描下方二维码,加入CVer学术星球!可以获得最新顶会/顶…...
实战应用:基于快马AI与OpenClaw构建Mac本地电商价格监控系统
最近在做一个电商价格监控的小工具,发现用OpenClaw配合Mac本地环境搭建特别方便。这里分享一下我的实战经验,希望能帮到有类似需求的同学。 为什么选择OpenClaw OpenClaw是个轻量级的Python爬虫框架,特别适合需要快速搭建数据采集系统的场景…...
告别付费IP!手把手教你用ZCU102 PS端DP接口点亮显示器(附参数调试心得)
解锁ZCU102 PS端DisplayPort潜力:零成本实现高效显示输出的实战指南 在嵌入式视觉系统开发中,显示输出往往是项目落地的最后一道关卡。当我在多个Zynq UltraScale MPSoC项目中反复遭遇HDMI IP核的授权困扰和PL端实现的复杂性后,意外发现PS端集…...
