数据结构与算法 / 系统课时

红黑树原理

红黑树原理

红黑树不是追求每个节点都接近绝对平衡,而是通过颜色规则限制最长路径与最短路径的比例。它允许局部高度差存在,却仍把整体树高控制在 O(log⁡n)O(\log n),因此常用于需要频繁插入和删除的有序集合与映射。

学习目标

  • 能准确说明红黑树的五条核心性质及其对树高的约束。
  • 能解释插入时旋转与重新着色分别解决什么问题。
  • 能运行并验证一个包含插入修复逻辑的红黑树实现。

颜色约束与插入修复

红黑树仍满足二叉搜索树顺序,同时具有五条性质:每个节点为红或黑;根节点为黑;所有空叶子视为黑;红节点的孩子必须为黑;从任意节点到其后代空叶子的每条路径包含相同数量的黑节点。最后一项通常称为黑高一致。

这些约束意味着一条根到叶路径不可能连续出现两个红节点,最长路径至多是最短路径的两倍,可推出含 n 个内部节点的红黑树高度不超过 2log⁡2(n+1)2\log_2(n+1)。因此查找、插入和删除的渐进时间复杂度都是 O(log⁡n)O(\log n)。

插入首先按普通二叉搜索树规则放置新节点,并把新节点设为红色。这样不会立即增加路径黑高;真正可能被破坏的是“红节点不能有红孩子”。修复过程围绕父节点、叔叔节点和祖父节点展开:

条件 主要动作 目的
父节点为黑 无需修复 所有性质仍成立
父节点与叔叔节点都为红 父、叔变黑,祖父变红并向上继续 消除局部红红冲突且保持黑高
父节点为红、叔叔节点为黑,方向呈折线 先旋转父节点 转换为直线结构
父节点为红、叔叔节点为黑,方向呈直线 旋转祖父并交换相关颜色 消除红红冲突并恢复局部黑高

红黑树性质与插入修复流程

旋转只改变局部结构,负责修正路径形状;重新着色不改变键的位置,负责恢复颜色与黑高约束。二者经常组合使用,不能把“旋转后有序”误认为“红黑性质已经自动成立”。

完整可运行示例

下面的 Java 17 示例实现经典红黑树插入。代码把 null 当作黑色空叶子,使用父指针寻找叔叔与祖父,并对左右方向编写镜像修复分支;重复键直接忽略。

java
import java.util.ArrayList;
import java.util.List;

public class RedBlackTreeDemo {

    private enum Color {
        RED, BLACK
    }

    private static class Node {
        int key;
        // 新插入节点先设为红色,避免立即改变所有路径的黑高。
        Color color = Color.RED;
        Node left;
        Node right;
        Node parent;

        Node(int key) {
            this.key = key;
        }
    }

    private Node root;

    public void insert(int key) {
        Node parent = null;
        Node current = root;
        while (current != null) {
            parent = current;
            if (key < current.key) {
                current = current.left;
            } else if (key > current.key) {
                current = current.right;
            } else {
                return;
            }
        }

        Node inserted = new Node(key);
        inserted.parent = parent;
        if (parent == null) {
            root = inserted;
        } else if (key < parent.key) {
            parent.left = inserted;
        } else {
            parent.right = inserted;
        }
        // 普通 BST 插入完成后,只修复可能出现的红红冲突。
        fixAfterInsert(inserted);
    }

    private void fixAfterInsert(Node node) {
        // 只要父节点为红,就违反了红节点不能有红孩子的约束。
        while (node != root && colorOf(node.parent) == Color.RED) {
            Node parent = node.parent;
            Node grandparent = parent.parent;
            if (parent == grandparent.left) {
                Node uncle = grandparent.right;
                if (colorOf(uncle) == Color.RED) {
                    // 父叔同红时重新着色,并把检查点上移到祖父。
                    parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    grandparent.color = Color.RED;
                    node = grandparent;
                } else {
                    if (node == parent.right) {
                        // 折线结构先旋转父节点,转换为可统一处理的直线结构。
                        node = parent;
                        rotateLeft(node);
                        parent = node.parent;
                        grandparent = parent.parent;
                    }
                    parent.color = Color.BLACK;
                    grandparent.color = Color.RED;
                    rotateRight(grandparent);
                }
            } else {
                Node uncle = grandparent.left;
                if (colorOf(uncle) == Color.RED) {
                    // 右侧分支与左侧分支完全镜像。
                    parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    grandparent.color = Color.RED;
                    node = grandparent;
                } else {
                    if (node == parent.left) {
                        node = parent;
                        rotateRight(node);
                        parent = node.parent;
                        grandparent = parent.parent;
                    }
                    parent.color = Color.BLACK;
                    grandparent.color = Color.RED;
                    rotateLeft(grandparent);
                }
            }
        }
        // 修复传播到根时,最终强制根节点为黑色。
        root.color = Color.BLACK;
    }

    private void rotateLeft(Node top) {
        // 旋转只改变局部连接,不改变中序遍历中的键顺序。
        Node newTop = top.right;
        top.right = newTop.left;
        if (newTop.left != null) {
            newTop.left.parent = top;
        }
        newTop.parent = top.parent;
        replaceParentLink(top, newTop);
        newTop.left = top;
        top.parent = newTop;
    }

    private void rotateRight(Node top) {
        Node newTop = top.left;
        top.left = newTop.right;
        if (newTop.right != null) {
            newTop.right.parent = top;
        }
        newTop.parent = top.parent;
        replaceParentLink(top, newTop);
        newTop.right = top;
        top.parent = newTop;
    }

    private void replaceParentLink(Node oldChild, Node newChild) {
        if (oldChild.parent == null) {
            root = newChild;
        } else if (oldChild == oldChild.parent.left) {
            oldChild.parent.left = newChild;
        } else {
            oldChild.parent.right = newChild;
        }
    }

    private Color colorOf(Node node) {
        return node == null ? Color.BLACK : node.color;
    }

    public void printSummary() {
        List<String> ordered = new ArrayList<>();
        collectInOrder(root, ordered);
        System.out.println("中序遍历: " + ordered);
        System.out.println("根节点颜色: " + root.color);
        System.out.println("树高: " + height(root));
        System.out.println("无连续红节点: " + hasNoRedRed(root));
        System.out.println("黑高一致: " + (blackHeight(root) >= 0));
    }

    private void collectInOrder(Node node, List<String> ordered) {
        if (node == null) {
            return;
        }
        collectInOrder(node.left, ordered);
        ordered.add(node.key + (node.color == Color.RED ? "R" : "B"));
        collectInOrder(node.right, ordered);
    }

    private int height(Node node) {
        return node == null ? 0 : Math.max(height(node.left), height(node.right)) + 1;
    }

    private boolean hasNoRedRed(Node node) {
        if (node == null) {
            return true;
        }
        if (node.color == Color.RED
                && (colorOf(node.left) == Color.RED || colorOf(node.right) == Color.RED)) {
            return false;
        }
        return hasNoRedRed(node.left) && hasNoRedRed(node.right);
    }

    private int blackHeight(Node node) {
        if (node == null) {
            return 1;
        }
        int left = blackHeight(node.left);
        int right = blackHeight(node.right);
        if (left < 0 || right < 0 || left != right) {
            return -1;
        }
        return left + (node.color == Color.BLACK ? 1 : 0);
    }

    public static void main(String[] args) {
        RedBlackTreeDemo tree = new RedBlackTreeDemo();
        int[] values = {10, 20, 30, 15, 25, 5, 1};
        for (int value : values) {
            tree.insert(value);
        }
        tree.printSummary();
    }
}

将代码保存为 RedBlackTreeDemo.java,然后编译运行:

bash
javac RedBlackTreeDemo.java
java RedBlackTreeDemo

预期输出:

text
中序遍历: [1R, 5B, 10R, 15B, 20B, 25R, 30B]
根节点颜色: BLACK
树高: 4
无连续红节点: true
黑高一致: true

输出中的 R 与 B 分别表示红色和黑色。中序键值递增验证搜索树顺序,后两项验证没有红红相邻,并且各根到空叶路径的黑节点数量一致。

常见错误与练习

实现旋转时最容易遗漏父指针或祖父到新子树根的连接,结果可能出现环、丢失节点或后续空指针异常。另一个常见误区是只检查根为黑和没有连续红节点,却未验证黑高一致;这两项通过仍不足以证明整棵树合法。

  1. 将输入改为 {30, 20, 10},记录发生的旋转和重新着色,并验证最终根节点为黑。
  2. 在每次插入后调用性质校验,要求一旦黑高不一致就立即抛出异常并打印当前插入键。
  3. 比较同一组递增数据在普通二叉搜索树、AVL 树和红黑树中的高度,验收时分别解释三者的平衡强度与更新成本差异。

本课总结

  • 红黑树以颜色和黑高约束实现近似平衡,树高上界保证核心操作为 O(log⁡n)O(\log n)。
  • 插入红节点可避免立即改变黑高;父叔同红主要靠重新着色,叔黑场景通常需要旋转与着色配合。
  • 验证红黑树不能只看形状,还必须同时检查搜索顺序、根颜色、红红约束和黑高一致。

下一课预告

下一阶段将继续比较平衡搜索树在查询频率、更新频率、内存占用以及外部存储场景中的工程取舍。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

红黑树原理

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通