每日算法 — 使用java实现红黑树：自平衡二叉搜索树与旋转操作

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，由Rudolf Bayer于1972年发明。它通过为每个节点增加一个颜色属性（红色或黑色）并维持五条核心性质，确保树的高度始终保持在O(log n)，从而保证查找、插入和删除操作的最坏时间复杂度均为O(log n)。Java的TreeMap、TreeSet以及C++的map、set均以红黑树为底层实现。

核心性质

红黑树必须满足以下五条性质：

每个节点要么是红色，要么是黑色
根节点必须是黑色
所有叶子节点（NIL）都是黑色
红色节点的两个子节点必须是黑色（不存在连续红色节点）
从任一节点到其每个叶子节点的所有路径上，黑色节点数量相同（黑高相同）

性质4和性质5共同保证了最长路径不超过最短路径的两倍，因此树高被限制在2log(n+1)以内。

旋转操作

旋转是红黑树维持平衡的基础操作，分为左旋和右旋，均在O(1)时间内完成。

左旋

以某个节点为支点，将其右子节点提升为新的子树根，原节点变为左子节点。

private void leftRotate(Node x) {
    Node y = x.right;
    x.right = y.left;
    if (y.left != nil) {
        y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent == nil) {
        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 rightRotate(Node y) {
    Node x = y.left;
    y.left = x.right;
    if (x.right != nil) {
        x.right.parent = y;
    }
    x.parent = y.parent;
    if (y.parent == nil) {
        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
情况3：叔节点为黑色且当前节点为外侧子节点 —— 变色后对祖父节点旋转

private void insertFixup(Node z) {
    while (z.parent.color == RED) {
        if (z.parent == z.parent.parent.left) {
            Node y = z.parent.parent.right; // 叔节点
            if (y.color == RED) {
                // 情况1：叔节点为红色
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                if (z == z.parent.right) {
                    // 情况2：转为情况3
                    z = z.parent;
                    leftRotate(z);
                }
                // 情况3
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                rightRotate(z.parent.parent);
            }
        } else {
            // 对称处理
            Node y = z.parent.parent.left;
            if (y.color == RED) {
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                if (z == z.parent.left) {
                    z = z.parent;
                    rightRotate(z);
                }
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                leftRotate(z.parent.parent);
            }
        }
    }
    root.color = BLACK;
}

完整可运行代码

/**
 * 红黑树实现 - 自平衡二叉搜索树
 * 插入、删除、查找时间复杂度: O(log n)
 */
public class RedBlackTree {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        int key;
        boolean color;
        Node left, right, parent;

        Node(int key) {
            this.key = key;
            this.color = RED; // 新节点默认为红色
        }
    }

    private Node root;
    private final Node nil; // 哨兵叶子节点

    public RedBlackTree() {
        nil = new Node(0);
        nil.color = BLACK;
        root = nil;
    }

    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != nil) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == nil) {
            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 rightRotate(Node y) {
        Node x = y.left;
        y.left = x.right;
        if (x.right != nil) {
            x.right.parent = y;
        }
        x.parent = y.parent;
        if (y.parent == nil) {
            root = x;
        } else if (y == y.parent.right) {
            y.parent.right = x;
        } else {
            y.parent.left = x;
        }
        x.right = y;
        y.parent = x;
    }

    public void insert(int key) {
        Node z = new Node(key);
        Node y = nil;
        Node x = root;

        while (x != nil) {
            y = x;
            if (z.key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        z.parent = y;
        if (y == nil) {
            root = z;
        } else if (z.key < y.key) {
            y.left = z;
        } else {
            y.right = z;
        }

        z.left = nil;
        z.right = nil;
        z.color = RED;

        insertFixup(z);
    }

    private void insertFixup(Node z) {
        while (z.parent.color == RED) {
            if (z.parent == z.parent.parent.left) {
                Node y = z.parent.parent.right;
                if (y.color == RED) {
                    z.parent.color = BLACK;
                    y.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else {
                    if (z == z.parent.right) {
                        z = z.parent;
                        leftRotate(z);
                    }
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    rightRotate(z.parent.parent);
                }
            } else {
                Node y = z.parent.parent.left;
                if (y.color == RED) {
                    z.parent.color = BLACK;
                    y.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else {
                    if (z == z.parent.left) {
                        z = z.parent;
                        rightRotate(z);
                    }
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    leftRotate(z.parent.parent);
                }
            }
        }
        root.color = BLACK;
    }

    public Node search(int key) {
        Node x = root;
        while (x != nil && key != x.key) {
            if (key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        return x == nil ? null : x;
    }

    public void inorderTraversal() {
        inorderHelper(root);
        System.out.println();
    }

    private void inorderHelper(Node node) {
        if (node != nil) {
            inorderHelper(node.left);
            System.out.print(node.key + (node.color == RED ? "(R) " : "(B) "));
            inorderHelper(node.right);
        }
    }

    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        int[] keys = {10, 20, 30, 15, 25, 5, 1};

        for (int key : keys) {
            tree.insert(key);
        }

        System.out.print("中序遍历: ");
        tree.inorderTraversal();

        System.out.println("查找 15: " + (tree.search(15) != null ? "找到" : "未找到"));
        System.out.println("查找 100: " + (tree.search(100) != null ? "找到" : "未找到"));
    }
}

复杂度分析

操作	时间复杂度	说明
查找	O(log n)	最坏情况下树高为2log(n+1)
插入	O(log n)	含O(1)次旋转修复
删除	O(log n)	含O(1)次旋转修复
空间	O(n)	每个节点存储颜色和三个指针

与AVL树的对比

特性	红黑树	AVL树
平衡严格度	较宽松（最长路径≤2倍最短路径）	严格平衡（左右子树高度差≤1）
查找性能	略慢	更快
插入/删除	旋转次数更少，更适合频繁修改	旋转次数更多
典型应用	TreeMap、Linux内核调度	数据库索引（读多写少）

红黑树在工程实践中更为常见，因其在查找和修改之间取得了更好的平衡。

Tagged with: Red-Black Tree TreeMap 二叉树旋转操作红黑树自平衡二叉搜索树