当前位置：首页 > java >正文

JAVA：红黑树应用的技术指南

java 2025/5/5 2:57:34

🌳 1、简述

红黑树是一种自平衡二叉查找树（Self-Balancing Binary Search Tree），被广泛应用于操作系统调度、Java集合、数据库索引等核心模块中。本文将从 基本原理 入手，结合 实际应用场景与代码实例，带你全面理解红黑树的精髓。

代码样例：https://gitee.com/lhdxhl/algorithm-example.git

在这里插入图片描述

📘 2、什么是红黑树？

红黑树是一种特殊的二叉查找树（BST），其核心目的是通过维护“颜色约束”来实现平衡，从而提高插入、查找和删除操作的效率。

红黑树的每个节点除了值和左右指针外，还会包含一个颜色字段（红或黑）。

🎯 红黑树的五大性质

每个节点不是红色就是黑色。
根节点是黑色。
所有叶子节点（NIL）都是黑色的（虚拟叶子节点）。
若一个节点是红色，则其子节点必须是黑色（红色节点不能相邻）。
从任一节点到其叶子节点的所有路径上，黑色节点数量相同。

✅ 这些性质共同确保了树的“近似平衡”，从而使红黑树操作的时间复杂度保持在：

查找：O(log n)
插入：O(log n)
删除：O(log n)

在这里插入图片描述

🔧 3、红黑树的操作（核心逻辑）

📥 插入操作流程

插入节点为红色，作为 BST 插入。
若父节点为黑色，插入完成。
若父节点为红色，需通过旋转（左旋/右旋）+变色保持平衡。
最终保持根节点为黑色。

📤 删除操作流程

删除较复杂，需要考虑：

替代节点颜色是否影响黑平衡；
是否需要旋转或变色修复结构；
若删除的是黑节点，需额外修复。

🧪 3、实践样例

用 Java 手写简化版红黑树：

public class RedBlackTree<K extends Comparable<K>, V> {private static final boolean RED = true;private static final boolean BLACK = false;private class Node {K key;V value;Node left, right;boolean color;Node(K key, V value, boolean color) {this.key = key;this.value = value;this.color = color;}}private Node root;// 判断节点是否为红色private boolean isRed(Node node) {return node != null && node.color == RED;}// 左旋private Node rotateLeft(Node h) {Node x = h.right;h.right = x.left;x.left = h;x.color = h.color;h.color = RED;return x;}// 右旋private Node rotateRight(Node h) {Node x = h.left;h.left = x.right;x.right = h;x.color = h.color;h.color = RED;return x;}// 颜色翻转private void flipColors(Node h) {h.color = RED;h.left.color = BLACK;h.right.color = BLACK;}// 插入public void put(K key, V value) {root = put(root, key, value);root.color = BLACK;}private Node put(Node h, K key, V value) {if (h == null) return new Node(key, value, RED);int cmp = key.compareTo(h.key);if (cmp < 0) h.left = put(h.left, key, value);else if (cmp > 0) h.right = put(h.right, key, value);else h.value = value;if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);if (isRed(h.left) && isRed(h.right)) flipColors(h);return h;}public V get(K key) {Node x = root;while (x != null) {int cmp = key.compareTo(x.key);if (cmp < 0) x = x.left;else if (cmp > 0) x = x.right;else return x.value;}return null;}
}

下面是基于上面实现的 RedBlackTree 类的使用样例，帮助你理解红黑树在 Java 中的基本操作与实际应用场景：

public class RedBlackTreeExample {public static void main(String[] args) {RedBlackTree<Integer, String> tree = new RedBlackTree<>();// 插入元素tree.put(10, "十");tree.put(5, "五");tree.put(15, "十五");tree.put(1, "一");tree.put(7, "七");// 查询元素System.out.println("key=7 -> " + tree.get(7)); // 输出: 七System.out.println("key=10 -> " + tree.get(10)); // 输出: 十System.out.println("key=20 -> " + tree.get(20)); // 输出: null（不存在）}
}

💡 4、应用场景

应用场景	使用说明
🔠 Java 的 TreeMap / TreeSet	使用红黑树实现有序键值对集合
🧠 Linux CFS（完全公平调度器）	使用红黑树调度任务时间片
🗂 数据库索引（如 PostgreSQL）	作为内存结构实现 B-Tree 之前的数据排序
🧬 内核内存管理	设备地址映射、区域管理等

🔍 红黑树 vs 其它平衡树对比

数据结构	插入复杂度	是否自平衡	应用代表
AVL树	O(log n)	是	少见、用于内存索引
红黑树	O(log n)	是（弱平衡）	TreeMap、Linux
B+ 树	O(log n)	是	数据库索引
跳表（SkipList）	O(log n)	是（概率）	Redis