Java数据结构与算法(红黑树)

server/2024/12/23 7:39:15/

前言

红黑树是一种自平衡二叉搜索树,确保在插入和删除操作后,树的高度保持平衡,从而保证基本操作(插入、删除、查找)的时间复杂度为O(log n)。

实现原理

红黑树具有以下性质:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点是黑色的。
  3. 每个叶子节点(NIL节点,通常是空节点)是黑色的。
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

动画过程

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:待定


http://www.ppmy.cn/server/46587.html

相关文章

智能监控技术助力山林生态养鸡:打造智慧安全的养殖新模式

随着现代科技的不断发展&#xff0c;智能化、自动化的养殖方式逐渐受到广大养殖户的青睐。特别是在山林生态养鸡领域&#xff0c;智能化监控方案的引入不仅提高了养殖效率&#xff0c;更有助于保障鸡只的健康与安全。视频监控系统EasyCVR视频汇聚/安防监控视频管理平台在山林生…

数据结构(C):从初识堆到堆排序的实现

&#x1f31e;0.前言 言C之言&#xff0c;聊C之识&#xff0c;以C会友&#xff0c;共向远方。各位博友的各位你们好啊&#xff0c;这里是持续分享数据结构知识的小赵同学&#xff0c;今天要分享的数据结构知识是堆&#xff0c;在这一章&#xff0c;小赵将会向大家展开聊聊堆的相…

Python课设-学生信息管理系统

一、效果展示图 二、前端代码 1、HTML代码 <1>index.html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0">…

基于Qt GraphicView 解析 CIM/G 电力接线图文件

本文讲述了如何使用Qt的框架来渲染展示标准的CIM/G格式的图形文件&#xff0c;也就是公用信息模型&#xff08;common information model&#xff0c;CIM&#xff09;中的G文件部分的内容。这是一种电力系统图形的交换规则&#xff0c;用于电网图形交换。 [by amjieker] CIM/G …

【头歌】计算机网络DHCP服务器配置第二关access口配置答案

头歌计算机网络DHCP服务器配置第二关access口配置操作步骤 任务描述 本关任务&#xff1a;创建 vlan &#xff0c;并且将与 pc 机相连接口划分 vlan 。 操作要求 在第一关的拓扑图的基础上&#xff0c;配置交换机&#xff0c;具体要求如下&#xff1a; 1、在特权模式下进入 vla…

Ubuntu20.04安装VINS_Mono 和 VINS_Fusion

文章目录 一、问题描述二、依赖环境1. Eigen 安装2. glog 安装3. gflags 安装4. ceres 安装 三、VINS-Mono 安装1. git 下载并安装2. OpenCV 版本冲突3. 运行 四、VINS—Fusion 安装1. git 下载并安装2. OpenCV 版本冲突3. 运行 五、日常bug1. 动静态库链接冲突 一、问题描述 …

自动化办公02 用openpyxl库操作excel.xlsx文件(新版本)

目录 一、文件读操作 二、文件写操作 三、修改单元格样式 openpyxl 是一个处理Excel表格的第三方库。openpyxl 库可以处理Excel2010以后的电子表格格式&#xff0c;包括&#xff1a;xlsx/xlsm/xltx/xltm。 openpyxl教程 一、文件读操作 工作簿(workbook): excel文件 工作表…

IDEA+MyBatisX根据mapper方法自动添加注解和生成xml方法结构

前提&#xff1a;确保IDEA已安装并启用了MyBatisX插件 在service层写dao或mapper的方法结构&#xff0c;反向生成dao层方法声明&#xff0c;如下&#xff1a; void updateStock(Long skuId, Long wareId, Integer skuNum); 由于该方法传递多个参数&#xff0c;为了让MyBatis识…