数据结构红黑树

编程问答/2024/02/08 17:20:51

红黑树是一种自平衡的二叉搜索树,它通过确保任何从根到叶子的路径上不会有两个连续的红节点并且从根到叶子的所有路径上有相同数量的黑节点,从而近似平衡。这种平衡保证了在最坏情况下插入、删除、查找操作都能在O(log n)时间复杂度内完成。

下面,我将逐步介绍红黑树的关键操作,包括节点的定义、插入操作以及调整(修复)操作。由于完整的源码和解析非常冗长,我将简要概述每个部分,并给出关键代码片段。

红黑树节点的定义

在实现红黑树之前,我们首先定义树中的节点,包括节点的颜色、键值、左右子节点以及父节点的引用:

class RedBlackNode<T extends Comparable<T>> {enum Color { RED, BLACK }T key;Color color;RedBlackNode<T> left;RedBlackNode<T> right;RedBlackNode<T> parent;public RedBlackNode(T key, Color nodeColor, RedBlackNode<T> left, RedBlackNode<T> right) {this.key = key;this.color = nodeColor;this.left = left;this.right = right;this.parent = null; // 父节点在插入时确定}
}

红黑树的插入操作

插入操作首先按照二叉搜索树的性质插入节点,之后会根据红黑树的性质进行一系列的调整。

public void insert(T key) {RedBlackNode<T> node = new RedBlackNode<T>(key, RedBlackNode.Color.RED, null, null);// 正常的BST插入操作if (root == null) {root = node;} else {insertNode(root, node);}// 插入后的调整操作fixAfterInsertion(node);
}

插入后的调整操作

插入节点后可能会违反红黑树的性质,因此需要进行调整。下面是调整操作的伪代码概述:

while (新节点不是根节点且新节点的父节点是红色) {if (父节点是祖父节点的左子节点) {uncle = 祖父节点的右子节点if (uncle是红色) {// Case 1: 叔叔节点也是红色父节点设为黑色叔叔节点设为黑色祖父节点设为红色新节点 = 祖父节点} else {if (新节点是父节点的右子节点) {// Case 2: 新节点是其父节点的右子节点新节点 = 父节点左旋转(新节点)}// Case 3: 新节点是其父节点的左子节点父节点设为黑色祖父节点设为红色右旋转(祖父节点)}} else {// 对称地处理父节点是祖父节点右子节点的情况...}
}
根节点设为黑色

左旋转示例

左旋转是在插入节点导致树不平衡时重新平衡树的操作之一。以下是左旋转的概念性Java代码:

void leftRotate(RedBlackNode<T> x) {RedBlackNode<T> 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;
}

右旋转示例

右旋转是左旋转的对称操作,用于重新平衡树。

void rightRotate(RedBlackNode<T> y) {RedBlackNode<T> x = y.left;y.left = x.right;if (x.right != null) {x.right.parent = y;}x.parent = y.parent;if (y.parent == null) {root = x;} else if (y == y.parent.right) {y.parent.right = x;} else {y.parent.left = x;}x.right = y;y.parent = x;
}

细节和注意事项

  1. 颜色翻转: 在某些情况下,你需要改变父节点和叔叔节点的颜色,并进行旋转。
  2. 插入时的颜色: 新插入的节点总是红色的。
  3. 根节点的颜色: 每次插入或删除后,根节点应保持为黑色。
  4. 旋转:旋转操作是用来重新平衡树结构的。左旋是将节点向左下方转移,而右旋是将其向右下方转移。

实现红黑树的完整代码需要大量的时间和精力。通常情况下,大多数编程语言的标准库中已经包含了红黑树的实现,比如Java中的TreeMapTreeSet。如果你要实现自己的红黑树,建议详细阅读相关书籍或文档,并在严格控制下一步步实现。


https://weda.daipet.cn/350715.html

相关文章

贪心算法入门题(算法村第十七关青铜挑战)

青铜挑战&amp;#xff1a;贪心其实很简单 贪心算法&amp;#xff08;贪婪算法&amp;#xff09;是指在对问题进行求解时&amp;#xff0c;在每一步选择中都采取最好或者最优的选择&amp;#xff0c;从而希望能够导致结果是最好或者最优的算法。 贪心算法要么得到最优解&amp;#xff0c;要么得到近似最优解…

Vue CLI学习笔记

在看任何开源库的源码之前&amp;#xff0c;必须先了解它有哪些功能&amp;#xff0c;这样才能针对性地分模块阅读源码。 Vue CLI 简介 Vue CLI是Vue.js的官方命令行工具&amp;#xff0c;它是一个基于Vue.js进行快速开发的完整系统。 通过Vue CLI&amp;#xff0c;开发者可以快速搭建和开发Vue.js项…

三、设计模式相关理论总结

一、面向对象编程 1.1 概述 简称Object Oriented Program(OOP)&amp;#xff0c;指以类或对象作为基础组织单元&amp;#xff0c;遵循封装、继承、多态以及抽象等特性&amp;#xff0c;进行编程。其中面向对象不一定遵循封装、继承、封装和多态等特性&amp;#xff0c;只是前人总结的套路规范&amp…

蓝桥杯刷题day08——完全日期

1、题目描述 如果一个日期中年月日的各位数字之和是完全平方数&amp;#xff0c;则称为一个完全日期。 例如&amp;#xff1a;2021年6月5日的各位数字之和为20216516&amp;#xff0c;而16是一个完全平方数&amp;#xff0c;它是4的平方。所以2021年6月5日是一个完全日期。 请问&amp;#xff0c;从200…

【Flink状态管理(二)各状态初始化入口】状态初始化流程详解与源码剖析

文章目录 1. 状态初始化总流程梳理2.创建StreamOperatorStateContext3. StateInitializationContext的接口设计。4. 状态初始化举例&amp;#xff1a;UDF状态初始化 在TaskManager中启动Task线程后&amp;#xff0c;会调用StreamTask.invoke()方法触发当前Task中算子的执行&amp;#xff0c;在…

Get Ready!这些 ALVA 应用即将上线 Vision Pro!

日前&amp;#xff0c;苹果 Vision Pro 正式在美国上市&amp;#xff0c;应用商店首批上线超过 600 款应用程序&amp;#xff0c;出色的显示效果和交互体验&amp;#xff0c;为更多应用提供了全新打开方式。 *图源&amp;#xff1a;Apple 对此&amp;#xff0c;作为全球领先的空间计算技术平台供应商&amp;#xff…

Go语言的100个错误使用场景(30-40)|数据类型与字符串使用

前言 大家好&amp;#xff0c;这里是白泽。 《Go语言的100个错误以及如何避免》 是最近朋友推荐我阅读的书籍&amp;#xff0c;我初步浏览之后&amp;#xff0c;大为惊喜。就像这书中第一章的标题说到的&amp;#xff1a;“Go: Simple to learn but hard to master”&amp;#xff0c;整本书通过分析100…

年货大数据(电商平台年货节数据):水果销售额增长72%,海鲜肉类涨幅高于蔬菜

春节临近&amp;#xff0c;生鲜又成了线上线下“叫卖”狠&amp;#xff0c;竞争大&amp;#xff0c;盈利好的行业之一。无论是线下商超&amp;#xff0c;还是线上电商&amp;#xff0c;生鲜行业在年货节期间不愁没有市场需求。 根据鲸参谋数据显示&amp;#xff0c;1月前三周京东平台生鲜市场整体销量超3300万…

Mac上几款好用的MacBook视频播放器

使用Mac电脑时&amp;#xff0c;视频播放器可以说是我们使用频率最高的软件之一了&amp;#xff0c;不管是工作时看视频资料还是在家里看下载好的电影&amp;#xff0c;都需要用到视频播放器&amp;#xff0c;本文中我们就来推荐几款好用的Macbook视频播放器&amp;#xff0c;总有一款适合你&amp;#xff01;…

中小学信息学奥赛CSP-J认证 CCF非专业级别软件能力认证-入门组初赛模拟题一解析(选择题)

CSP-J入门组初赛模拟题一&amp;#xff08;选择题&amp;#xff09; 1、以下与电子邮件无关的网络协议是 A、SMTP B、POP3 C、MIME D、FTP 答案&amp;#xff1a;D 考点分析&amp;#xff1a;主要考查小朋友们网络相关知识的储备&amp;#xff0c;FTP是文件传输协议和电子邮件无关&amp;#xff0c;所以…