红黑树基于Java代码的剖析

红黑树是一种自平衡的二叉查找树，通过添加颜色属性和旋转操作来保证树的平衡性，从而在最坏情况下仍能提供对数时间复杂度的插入、删除和查找操作。本文通过对一段红黑树的Java代码进行剖析，详细讲解其插入和删除操作是如何实现的，以及这些操作是如何利用红黑树的性质来维持平衡的。

红黑树的基本性质

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点都是黑色（这里的叶子节点指的是NIL节点）。
4. 红色节点的两个子节点都是黑色（红色节点不能连续，即没有两个红色节点是相连的）。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

节点类 Node

红黑树的每个节点包含键值对、颜色、大小以及左右子节点的引用。

// 节点类
private class Node {
    private Key key;           // 节点的键
    private Value val;         // 节点的值
    private Node left, right;  // 左右子节点
    private boolean color;     // 父节点指向该节点的链接颜色
    private int size;          // 以该节点为根的子树中的节点总数

    public Node(Key key, Value val, boolean color, int size) {
        this.key = key;
        this.val = val;
        this.color = color;
        this.size = size;
    }
}

插入操作 put

在红黑树中插入一个新节点需要遵循以下步骤，以保持树的平衡：

1. 普通的BST插入：新节点按照二叉查找树的规则插入到适当的位置。新节点默认颜色为红色。
2. 调整以维持红黑树的性质：
   • 颜色翻转：如果当前节点的左子节点和右子节点都是红色，则将它们的颜色翻转。
   • 左旋转和右旋转：如果出现右子节点是红色而左子节点是黑色的情况，需要进行左旋转。如果左子节点及其左子节点都是红色，需要进行右旋转。
3. 根节点颜色调整：最后，将根节点的颜色设为黑色。

// 插入键值对
public void put(Key key, Value val) {
    if (key == null) throw new IllegalArgumentException("first argument to put() is null");
    if (val == null) {
        delete(key);
        return;
    }

    root = put(root, key, val);
    root.color = BLACK; // 根节点始终为黑色
}

// 在子树中插入键值对，并进行必要的旋转和颜色翻转以保持平衡
private Node put(Node h, Key key, Value val) {
    if (h == null) return new Node(key, val, RED, 1); // 新节点为红色

    int cmp = key.compareTo(h.key);
    if (cmp < 0) h.left = put(h.left, key, val); // 递归插入左子树
    else if (cmp > 0) h.right = put(h.right, key, val); // 递归插入右子树
    else h.val = val; // 更新现有节点的值

    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); // 颜色翻转

    h.size = size(h.left) + size(h.right) + 1;
    return h;
}

删除操作 delete

删除操作相对复杂，需要确保删除后仍然满足红黑树的性质：

1. 调整树以确保有红色子节点：
   • 如果当前节点的左右子节点都是黑色，则通过 moveRedLeft 或 moveRedRight 方法将红色子节点移动到适当位置。
2. 找到并删除节点：
   • 递归查找要删除的节点，并进行相应的删除操作。如果是删除最小节点或最大节点，则直接删除。否则，找到右子树中的最小节点替换当前节点，并删除该最小节点。
3. 恢复红黑树的平衡：
   • 通过 balance 方法重新平衡当前子树。

// 删除最小节点
public void deleteMin() {
    if (isEmpty()) throw new NoSuchElementException("BST underflow");

    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED; // 如果根节点的两个子节点都是黑色，将根节点设为红色

    root = deleteMin(root);
    if (!isEmpty()) root.color = BLACK; // 删除操作完成后将根节点设为黑色
}

// 删除以h为根的子树中的最小节点
private Node deleteMin(Node h) {
    if (h.left == null)
        return null; // 找到最小节点

    if (!isRed(h.left) && !isRed(h.left.left))
        h = moveRedLeft(h); // 确保左子节点或其子节点中至少有一个红色节点

    h.left = deleteMin(h.left);
    return balance(h); // 恢复平衡
}

// 删除指定节点
public void delete(Key key) {
    if (key == null) throw new IllegalArgumentException("argument to delete() is null");
    if (!contains(key)) return;

    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED; // 如果根节点的两个子节点都是黑色，将根节点设为红色

    root = delete(root, key);
    if (!isEmpty()) root.color = BLACK; // 删除操作完成后将根节点设为黑色
}

// 删除以h为根的子树中键为key的节点
private Node delete(Node h, Key key) {
    if (key.compareTo(h.key) < 0) {
        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h); // 确保左子节点或其子节点中至少有一个红色节点
        h.left = delete(h.left, key);
    } else {
        if (isRed(h.left))
            h = rotateRight(h); // 如果左子节点是红色，则右旋
        if (key.compareTo(h.key) == 0 && (h.right == null))
            return null; // 找到要删除的节点并且没有右子节点
        if (!isRed(h.right) && !isRed(h.right.left))
            h = moveRedRight(h); // 确保右子节点或其子节点中至少有一个红色节点
        if (key.compareTo(h.key) == 0) {
            Node x = min(h.right); // 找到右子树中的最小节点
            h.key = x.key; // 替换当前节点
            h.val = x.val;
            h.right = deleteMin(h.right); // 删除右子树中的最小节点
        } else {
            h.right = delete(h.right, key); // 递归删除右子树中的节点
        }
    }
    return balance(h); // 恢复平衡
}

辅助方法

1. 旋转操作：
   • rotateLeft(Node h) 和 rotateRight(Node h) 用于调整树的结构。
2. 颜色翻转：
   • flipColors(Node h) 用于调整节点和其子节点的颜色。
3. 移动红色节点：
   • moveRedLeft(Node h) 和 moveRedRight(Node h) 用于在删除过程中移动红色节点。
4. 恢复平衡：
   • balance(Node h) 用于在插入或删除操作后恢复树的平衡。

// 左旋转: 使红链接向左倾斜
// 前提条件: h 的右子节点为红色
// 执行操作: 将 h 的右子节点 x 移动到 h 的位置，h 成为 x 的左子节点
private Node rotateLeft(Node h) {
    Node x = h.right; // 获取 h 的右子节点 x
    h.right = x.left; // 将 x 的左子节点设为 h 的右子节点
    x.left = h; // 将 h 设为 x 的左子节点
    x.color = h.color; // 保持 x 的颜色与 h 相同
    h.color = RED; // 将 h 设为红色
    x.size = h.size; // x 的 size 为 h 的 size
    h.size = size(h.left) + size(h.right) + 1; // 更新 h 的 size
    return x; // 返回新的子树根节点 x
}

// 右旋转: 使红链接向右倾斜
// 前提条件: h 的左子节点为红色
// 执行操作: 将 h 的左子节点 x 移动到 h 的位置，h 成为 x 的右子节点
private Node rotateRight(Node h) {
    Node x = h.left; // 获取 h 的左子节点 x
    h.left = x.right; // 将 x 的右子节点设为 h 的左子节点
    x.right = h; // 将 h 设为 x 的右子节点
    x.color = h.color; // 保持 x 的颜色与 h 相同
    h.color = RED; // 将 h 设为红色
    x.size = h.size; // x 的 size 为 h 的 size
    h.size = size(h.left) + size(h.right) + 1; // 更新 h 的 size
    return x; // 返回新的子树根节点 x
}

// 颜色翻转: 将一个节点及其两个子节点的颜色进行翻转
// 前提条件: 当前节点 h 及其两个子节点均存在
// 执行操作: 将 h 的颜色与其子节点颜色互换
private void flipColors(Node h) {
    h.color = !h.color; // 翻转 h 的颜色
    h.left.color = !h.left.color; // 翻转左子节点的颜色
    h.right.color = !h.right.color; // 翻转右子节点的颜色
}

// 移动红色节点到左边: 保证左子节点或其子节点中至少有一个红色节点
// 前提条件: h 的左子节点和左子节点的左子节点均为黑色
// 执行操作: 将右子节点的左子节点设为红色，并进行左旋和颜色翻转
private Node moveRedLeft(Node h) {
    flipColors(h); // 颜色翻转: 将 h 设为红色，两个子节点设为黑色
    if (isRed(h.right.left)) { // 如果右子节点的左子节点为红色
        h.right = rotateRight(h.right); // 右子节点右旋
        h = rotateLeft(h); // 当前节点左旋
        flipColors(h); // 再次颜色翻转
    }
    return h; // 返回新的子树根节点
}

// 移动红色节点到右边: 保证右子节点或其子节点中至少有一个红色节点
// 前提条件: h 的右子节点和右子节点的左子节点均为黑色
// 执行操作: 将左子节点的左子节点设为红色，并进行右旋和颜色翻转
private Node moveRedRight(Node h) {
    flipColors(h); // 颜色翻转: 将 h 设为红色，两个子节点设为黑色
    if (isRed(h.left.left)) { // 如果左子节点的左子节点为红色
        h = rotateRight(h); // 当前节点右旋
        flipColors(h); // 再次颜色翻转
    }
    return h; // 返回新的子树根节点
}

// 恢复红黑树的平衡: 修正可能违反红黑树性质的子树
// 前提条件: 子树根节点 h 不为空
// 执行操作: 修正右红链接，左-左红链接，以及颜色翻转
private Node balance(Node h) {
    if (isRed(h.right))                      h = rotateLeft(h); // 如果右子节点为红色，则左旋
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); // 如果左子节点及其左子节点都为红色，则右旋
    if (isRed(h.left) && isRed(h.right))     flipColors(h); // 如果左右子节点都为红色，则颜色翻转

    h.size = size(h.left) + size(h.right) + 1; // 更新 h 的 size
    return h; // 返回新的子树根节点
}

总结

红黑树通过维护额外的颜色属性和引入旋转操作，确保了树的高度始终保持在 (O(\log n)) 的级别，从而保证了高效的插入、删除和查找操作。通过上述代码剖析，可以清晰地看到红黑树是如何通过颜色调整和旋转来保持平衡的。