红黑树通关指南：从底层原理到工业级实战，一篇吃透！

果酱带你啃java

发布于 2026-04-14 13:47:09

510

红黑树通关指南：从底层原理到工业级实战，一篇吃透！

在数据结构的世界里，平衡二叉树是处理有序数据的利器，但严格平衡的AVL树在频繁插入删除时因旋转次数过多显得笨重。红黑树作为近似平衡二叉树的代表，以“少量旋转+高效操作”的特性成为工程领域的首选——Java的TreeMap、Linux内核的CFS调度器、C++ STL的map容器，处处可见它的身影。本文将从原理到实战，用通俗语言拆解红黑树的核心逻辑，结合可运行代码让你彻底掌握这一“工业级数据结构”。

一、红黑树的定义与核心性质（权威依据：《算法导论》第13章）

红黑树是一种自平衡的二叉查找树（BST），每个节点额外存储一个“颜色”属性（红/黑），通过颜色约束保证树的黑高平衡（从节点到叶节点的路径上黑节点数量相同）。其核心性质必须满足以下5点：

颜色约束：每个节点要么是红色，要么是黑色；
根节点规则：根节点必须是黑色；
叶节点规则：所有叶节点（NIL哨兵节点）是黑色；
红色节点规则：若一个节点是红色，则它的子节点必须是黑色（杜绝连续红节点）；
黑高规则：从任意节点到其所有后代叶节点的路径上，黑节点数量相同（称为“黑高”）。

这些规则看似简单，却能保证红黑树的高度不超过2log(n+1)（n为节点数），从而确保查找、插入、删除的时间复杂度均为**O(logn)**。

二、红黑树的基础操作：左旋与右旋

红黑树的平衡调整依赖左旋和右旋两个基础操作——本质是“旋转支点，调整子树关系”，不改变二叉查找树的有序性。

1. 左旋（Left Rotate）

以节点x为支点，将其右子树y提升为父节点，x成为y的左子节点，y的左子树转为x的右子树。

2. 右旋（Right Rotate）

以节点y为支点，将其左子树x提升为父节点，y成为x的右子节点，x的右子树转为y的左子树（与左旋对称）。

三、红黑树的插入操作：从定位到修复

红黑树插入节点时默认设为红色（减少黑高冲突），但可能违反“红色节点子节点为黑”的规则，需通过插入修复调整颜色和旋转。

插入流程（3步）

BST插入：按二叉查找树规则找到插入位置，新节点设为红色；
检查冲突：若父节点为黑色，无需修复；若父节点为红色，触发修复；
修复策略：分3种情况（以父节点为祖父左孩子为例，右孩子对称）：
- 情况1：叔叔节点为红 → 父+叔叔设黑，祖父设红，向上递归检查；
- 情况2：叔叔为黑，新节点是父的右孩子 → 左旋父节点，转为情况3；
- 情况3：叔叔为黑，新节点是父的左孩子 → 父设黑，祖父设红，右旋祖父节点。

四、红黑树的删除操作：从替换到修复

删除是红黑树最复杂的操作，需先按BST规则删除节点，再修复因“黑节点缺失”导致的黑高失衡。

删除流程（4步）

BST删除：找到待删节点z，分3种情况处理：
- 无孩子：直接删除；
- 一个孩子：用孩子替换z；
- 两个孩子：用后继节点（右子树最小节点）替换z；
记录颜色：若被替换节点是黑色，触发修复；
修复策略：分4种情况（以x为替换节点且是父的左孩子为例，右孩子对称）：
- 情况1：兄弟是红色 → 兄弟设黑，父设红，左旋父节点；
- 情况2：兄弟及孩子均为黑 → 兄弟设红，x上移；
- 情况3：兄弟右孩子黑，左孩子红 → 兄弟左孩子设黑，兄弟设红，右旋兄弟；
- 情况4：兄弟右孩子红 → 兄弟继承父颜色，父设黑，兄弟右孩子设黑，左旋父节点；
最终调整：将x设为黑色，确保根节点为黑。

五、红黑树与AVL树的核心区别（易混淆点梳理）

特性	红黑树	AVL树
平衡标准	黑高相同（近似平衡）	左右子树高度差≤1（严格平衡）
旋转次数	插入最多2次，删除最多3次	插入/删除最多O(logn)次
操作效率	插入删除更高效（旋转少）	查找更高效（高度更低）
内存占用	仅需1位存储颜色	需存储高度（int型）
典型应用	TreeMap、Linux CFS调度器	数据库索引（读多写少场景）

六、实战：手写红黑树（Java实现，JDK17+阿里巴巴规范）

以下是完整的红黑树实现，包含节点定义、基础操作、插入删除及测试代码，可直接编译运行。

1. 节点类定义（com.jam.demo.RBNode）

package com.jam.demo;
import lombok.Data;
/**
 * 红黑树节点类
 * @author ken
 * @param <K> 键类型（需实现Comparable）
 * @param <V> 值类型
 */
@Data
publicclass RBNode<K extends Comparable<K>, V> {
    publicstaticfinalboolean RED = true;
    publicstaticfinalboolean BLACK = false;
    private K key;
    private V value;
    private RBNode<K, V> parent;
    private RBNode<K, V> left;
    private RBNode<K, V> right;
    privateboolean color;
    /**
     * 构造函数
     * @param key 键
     * @param value 值
     * @param color 颜色
     */
    public RBNode(K key, V value, boolean color) {
        this.key = key;
        this.value = value;
        this.color = color;
    }
}

2. 红黑树核心实现（com.jam.demo.RBTree）

package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
/**
 * 红黑树实现类
 * @author ken
 * @param <K> 键类型（需实现Comparable）
 * @param <V> 值类型
 */
@Slf4j
publicclass RBTree<K extends Comparable<K>, V> {
    privatefinal RBNode<K, V> NIL;
    private RBNode<K, V> root;
    /**
     * 构造函数，初始化哨兵节点和根节点
     */
    public RBTree() {
        NIL = new RBNode<>(null, null, RBNode.BLACK);
        root = NIL;
    }
    /**
     * 左旋操作（以x为支点）
     * @param x 左旋支点节点
     */
    private void leftRotate(RBNode<K, V> x) {
        RBNode<K, V> y = x.getRight();
        x.setRight(y.getLeft());
        if (!ObjectUtils.nullSafeEquals(y.getLeft(), NIL)) {
            y.getLeft().setParent(x);
        }
        y.setParent(x.getParent());
        if (ObjectUtils.nullSafeEquals(x.getParent(), NIL)) {
            root = y;
        } elseif (ObjectUtils.nullSafeEquals(x, x.getParent().getLeft())) {
            x.getParent().setLeft(y);
        } else {
            x.getParent().setRight(y);
        }
        y.setLeft(x);
        x.setParent(y);
    }
    /**
     * 右旋操作（以y为支点）
     * @param y 右旋支点节点
     */
    private void rightRotate(RBNode<K, V> y) {
        RBNode<K, V> x = y.getLeft();
        y.setLeft(x.getRight());
        if (!ObjectUtils.nullSafeEquals(x.getRight(), NIL)) {
            x.getRight().setParent(y);
        }
        x.setParent(y.getParent());
        if (ObjectUtils.nullSafeEquals(y.getParent(), NIL)) {
            root = x;
        } elseif (ObjectUtils.nullSafeEquals(y, y.getParent().getRight())) {
            y.getParent().setRight(x);
        } else {
            y.getParent().setLeft(x);
        }
        x.setRight(y);
        y.setParent(x);
    }
    /**
     * 插入键值对
     * @param key 键（非空）
     * @param value 值
     */
    public void insert(K key, V value) {
        RBNode<K, V> z = new RBNode<>(key, value, RBNode.RED);
        RBNode<K, V> y = NIL;
        RBNode<K, V> x = root;
        while (!ObjectUtils.nullSafeEquals(x, NIL)) {
            y = x;
            int cmp = z.getKey().compareTo(x.getKey());
            if (cmp < 0) {
                x = x.getLeft();
            } elseif (cmp > 0) {
                x = x.getRight();
            } else {
                x.setValue(value);
                return;
            }
        }
        z.setParent(y);
        if (ObjectUtils.nullSafeEquals(y, NIL)) {
            root = z;
        } elseif (z.getKey().compareTo(y.getKey()) < 0) {
            y.setLeft(z);
        } else {
            y.setRight(z);
        }
        z.setLeft(NIL);
        z.setRight(NIL);
        insertFixup(z);
    }
    /**
     * 插入后修复红黑树性质
     * @param z 插入的节点
     */
    private void insertFixup(RBNode<K, V> z) {
        while (z.getParent().getColor() == RBNode.RED) {
            if (ObjectUtils.nullSafeEquals(z.getParent(), z.getParent().getParent().getLeft())) {
                RBNode<K, V> y = z.getParent().getParent().getRight();
                if (y.getColor() == RBNode.RED) {
                    z.getParent().setColor(RBNode.BLACK);
                    y.setColor(RBNode.BLACK);
                    z.getParent().getParent().setColor(RBNode.RED);
                    z = z.getParent().getParent();
                } else {
                    if (ObjectUtils.nullSafeEquals(z, z.getParent().getRight())) {
                        z = z.getParent();
                        leftRotate(z);
                    }
                    z.getParent().setColor(RBNode.BLACK);
                    z.getParent().getParent().setColor(RBNode.RED);
                    rightRotate(z.getParent().getParent());
                }
            } else {
                RBNode<K, V> y = z.getParent().getParent().getLeft();
                if (y.getColor() == RBNode.RED) {
                    z.getParent().setColor(RBNode.BLACK);
                    y.setColor(RBNode.BLACK);
                    z.getParent().getParent().setColor(RBNode.RED);
                    z = z.getParent().getParent();
                } else {
                    if (ObjectUtils.nullSafeEquals(z, z.getParent().getLeft())) {
                        z = z.getParent();
                        rightRotate(z);
                    }
                    z.getParent().setColor(RBNode.BLACK);
                    z.getParent().getParent().setColor(RBNode.RED);
                    leftRotate(z.getParent().getParent());
                }
            }
        }
        root.setColor(RBNode.BLACK);
    }
    /**
     * 根据键查找节点
     * @param key 键
     * @return 找到的节点（未找到返回NIL）
     */
    private RBNode<K, V> search(K key) {
        RBNode<K, V> x = root;
        while (!ObjectUtils.nullSafeEquals(x, NIL)) {
            int cmp = key.compareTo(x.getKey());
            if (cmp < 0) {
                x = x.getLeft();
            } elseif (cmp > 0) {
                x = x.getRight();
            } else {
                return x;
            }
        }
        return NIL;
    }
    /**
     * 替换节点（BST删除辅助操作）
     * @param u 被替换节点
     * @param v 替换节点
     */
    private void transplant(RBNode<K, V> u, RBNode<K, V> v) {
        if (ObjectUtils.nullSafeEquals(u.getParent(), NIL)) {
            root = v;
        } elseif (ObjectUtils.nullSafeEquals(u, u.getParent().getLeft())) {
            u.getParent().setLeft(v);
        } else {
            u.getParent().setRight(v);
        }
        v.setParent(u.getParent());
    }
    /**
     * 查找子树最小节点
     * @param node 子树根节点
     * @return 最小节点
     */
    private RBNode<K, V> minimum(RBNode<K, V> node) {
        while (!ObjectUtils.nullSafeEquals(node.getLeft(), NIL)) {
            node = node.getLeft();
        }
        return node;
    }
    /**
     * 根据键删除节点
     * @param key 键
     */
    public void delete(K key) {
        RBNode<K, V> z = search(key);
        if (ObjectUtils.nullSafeEquals(z, NIL)) {
            log.warn("键{}不存在，无需删除", key);
            return;
        }
        RBNode<K, V> y = z;
        RBNode<K, V> x;
        boolean yOriginalColor = y.getColor();
        if (ObjectUtils.nullSafeEquals(z.getLeft(), NIL)) {
            x = z.getRight();
            transplant(z, z.getRight());
        } elseif (ObjectUtils.nullSafeEquals(z.getRight(), NIL)) {
            x = z.getLeft();
            transplant(z, z.getLeft());
        } else {
            y = minimum(z.getRight());
            yOriginalColor = y.getColor();
            x = y.getRight();
            if (ObjectUtils.nullSafeEquals(y.getParent(), z)) {
                x.setParent(y);
            } else {
                transplant(y, y.getRight());
                y.setRight(z.getRight());
                y.getRight().setParent(y);
            }
            transplant(z, y);
            y.setLeft(z.getLeft());
            y.getLeft().setParent(y);
            y.setColor(z.getColor());
        }
        if (yOriginalColor == RBNode.BLACK) {
            deleteFixup(x);
        }
    }
    /**
     * 删除后修复红黑树性质
     * @param x 替换节点
     */
    private void deleteFixup(RBNode<K, V> x) {
        while (!ObjectUtils.nullSafeEquals(x, root) && x.getColor() == RBNode.BLACK) {
            if (ObjectUtils.nullSafeEquals(x, x.getParent().getLeft())) {
                RBNode<K, V> w = x.getParent().getRight();
                if (w.getColor() == RBNode.RED) {
                    w.setColor(RBNode.BLACK);
                    x.getParent().setColor(RBNode.RED);
                    leftRotate(x.getParent());
                    w = x.getParent().getRight();
                }
                if (w.getLeft().getColor() == RBNode.BLACK && w.getRight().getColor() == RBNode.BLACK) {
                    w.setColor(RBNode.RED);
                    x = x.getParent();
                } else {
                    if (w.getRight().getColor() == RBNode.BLACK) {
                        w.getLeft().setColor(RBNode.BLACK);
                        w.setColor(RBNode.RED);
                        rightRotate(w);
                        w = x.getParent().getRight();
                    }
                    w.setColor(x.getParent().getColor());
                    x.getParent().setColor(RBNode.BLACK);
                    w.getRight().setColor(RBNode.BLACK);
                    leftRotate(x.getParent());
                    x = root;
                }
            } else {
                RBNode<K, V> w = x.getParent().getLeft();
                if (w.getColor() == RBNode.RED) {
                    w.setColor(RBNode.BLACK);
                    x.getParent().setColor(RBNode.RED);
                    rightRotate(x.getParent());
                    w = x.getParent().getLeft();
                }
                if (w.getRight().getColor() == RBNode.BLACK && w.getLeft().getColor() == RBNode.BLACK) {
                    w.setColor(RBNode.RED);
                    x = x.getParent();
                } else {
                    if (w.getLeft().getColor() == RBNode.BLACK) {
                        w.getRight().setColor(RBNode.BLACK);
                        w.setColor(RBNode.RED);
                        leftRotate(w);
                        w = x.getParent().getLeft();
                    }
                    w.setColor(x.getParent().getColor());
                    x.getParent().setColor(RBNode.BLACK);
                    w.getLeft().setColor(RBNode.BLACK);
                    rightRotate(x.getParent());
                    x = root;
                }
            }
        }
        x.setColor(RBNode.BLACK);
    }
    /**
     * 中序遍历（升序输出）
     * @param node 起始节点
     */
    public void inOrderTraversal(RBNode<K, V> node) {
        if (!ObjectUtils.nullSafeEquals(node, NIL)) {
            inOrderTraversal(node.getLeft());
            log.info("Key: {}, Value: {}, Color: {}", node.getKey(), node.getValue(), node.getColor() ? "RED" : "BLACK");
            inOrderTraversal(node.getRight());
        }
    }
    // Getter
    public RBNode<K, V> getRoot() { return root; }
    public RBNode<K, V> getNIL() { return NIL; }
}

3. 测试类（com.jam.demo.RBTreeTest）

package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;
importstatic org.junit.jupiter.api.Assertions.*;
/**
 * 红黑树测试类
 * @author ken
 */
@Slf4j
publicclass RBTreeTest {
    @Test
    public void testInsertAndTraversal() {
        RBTree<Integer, String> rbTree = new RBTree<>();
        rbTree.insert(10, "A");
        rbTree.insert(20, "B");
        rbTree.insert(30, "C");
        rbTree.insert(15, "D");
        log.info("插入后中序遍历：");
        rbTree.inOrderTraversal(rbTree.getRoot());
        // 验证根节点为黑色
        assertEquals(RBNode.BLACK, rbTree.getRoot().getColor());
        // 验证根节点键为20（插入调整后）
        assertEquals(20, rbTree.getRoot().getKey());
    }
    @Test
    public void testDelete() {
        RBTree<Integer, String> rbTree = new RBTree<>();
        rbTree.insert(10, "A");
        rbTree.insert(20, "B");
        rbTree.insert(30, "C");
        log.info("删除前遍历：");
        rbTree.inOrderTraversal(rbTree.getRoot());
        rbTree.delete(20);
        log.info("删除后遍历：");
        rbTree.inOrderTraversal(rbTree.getRoot());
        // 验证根节点为黑色
        assertEquals(RBNode.BLACK, rbTree.getRoot().getColor());
        // 验证删除后根节点为10或30
        assertTrue(rbTree.getRoot().getKey() == 10 || rbTree.getRoot().getKey() == 30);
    }
}

4. Maven依赖（pom.xml）

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.jam.demo</groupId>
    <artifactId>rb-tree-demo</artifactId>
    <version>1.0.0</version>
    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
        <lombok.version>1.18.30</lombok.version>
        <spring-context.version>6.1.5</spring-context.version>
        <guava.version>33.2.1-jre</guava.version>
        <junit.jupiter.version>5.10.2</junit.jupiter.version>
    </properties>
    <dependencies>
        <!-- Lombok -->
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>${lombok.version}</version>
            <scope>provided</scope>
        </dependency>
        <!-- Spring Context（工具类依赖） -->
        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-context</artifactId>
            <version>${spring-context.version}</version>
        </dependency>
        <!-- Guava（集合工具） -->
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>${guava.version}</version>
        </dependency>
        <!-- JUnit 5（测试） -->
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-api</artifactId>
            <version>${junit.jupiter.version}</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-engine</artifactId>
            <version>${junit.jupiter.version}</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>

七、红黑树的工业级应用场景

Java集合框架：TreeMap/TreeSet底层基于红黑树实现，保证键的有序性和O(logn)操作效率；
Linux内核：
- CFS调度器用红黑树维护进程的vruntime（虚拟运行时间），实现公平调度；
- epoll用红黑树管理注册的文件描述符（fd），快速查找事件；
C++ STL：std::map/std::set底层是红黑树，支持有序遍历和高效插入删除；
内存数据库：如Oracle内存数据库用红黑树管理索引，平衡读写性能。