java实现红黑树

红黑树

红黑树是一种自平衡二叉查找树，其中每个节点都有一个颜色属性，颜色为红色或黑色。它的特性保证了树在插入和删除操作后仍然保持大致的平衡，使得查找操作能够在对数时间内完成。以下是红黑树的一些基本性质：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 所有叶子（NIL节点）都是黑色。
4. 每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

以下是红黑树的核心代码解析：

public class RedBlackTree {

    enum Color {
        RED, BLACK;
    }

    Node root;

    static class Node {
        int key;
        Object value;
        Node left;
        Node right;
        Node parent;        // 父节点
        Color color = RED;  // 默认插入的节点为红色

        // 构造函数和辅助函数
    }

构建节点和辅助函数

static class Node {
    // 构造函数，用于创建新节点
    public Node(int key, Object value) {
        this.key = key;
        this.value = value;
    }

    // 判断当前节点是否为左孩子
    boolean isLeftChild() {
        return parent != null && parent.left == this;
    }

    // 叔叔
    Node uncle() {
        if (parent == null || parent.parent == null) {
            return null;
        }
        if (parent.isLeftChild()) {
            return parent.parent.right;
        } else {
            return parent.parent.left;
        }
    }

    // 兄弟
    Node sibling() {
        if (parent == null) {
            return null;
        }
        if (this.isLeftChild()) {
            return parent.right;
        } else {
            return parent.left;
        }
    }
}

旋转操作（leftRotate & rightRotate）

为了维持红黑树的平衡性，在插入和删除节点时可能会用到旋转操作。

private void rightRotate(Node pink) {
    Node parent = pink.parent;
    Node yellow = pink.left;
    Node green = yellow.right;
    if (green != null) {
        green.parent = pink;
    }
    yellow.right = pink;
    yellow.parent = parent;
    pink.left = green;
    pink.parent = yellow;
    if (parent == null) {
        root = yellow;
    } else if (parent.left == pink) {
        parent.left = yellow;
    } else {
        parent.right = yellow;
    }
}

// 左旋
private void leftRotate(Node pink) {
    Node parent = pink.parent;
    Node yellow = pink.right;
    Node green = yellow.left;
    if (green != null) {
        green.parent = pink;
    }
    yellow.left = pink;
    yellow.parent = parent;
    pink.right = green;
    pink.parent = yellow;
    if (parent == null) {
        root = yellow;
    } else if (parent.left == pink) {
        parent.left = yellow;
    } else {
        parent.right = yellow;
    }
}

旋转操作的目的是重新分布节点，使得树的高度保持平衡，同时需要更新父节点和子节点的引用。

插入（put）

当向红黑树中插入新节点时，需要保证树的性质不被破坏。插入操作后，可能需要通过一系列的旋转和着色来修正树，保持红黑树的性质。

public void put(int key, Object value) {
    Node p = root;
    Node parent = null;
    while (p != null) {
        parent = p;
        if (key < p.key) {
            p = p.left;
        } else if (p.key < key) {
            p = p.right;
        } else {
            p.value = value; // 更新
            return;
        }
    }
    Node inserted = new Node(key, value);
    if (parent == null) {
        root = inserted;
    } else if (key < parent.key) {
        parent.left = inserted;
        inserted.parent = parent;
    } else {
        parent.right = inserted;
        inserted.parent = parent;
    }
    fixRedRed(inserted);
}

void fixRedRed(Node x) {
    // case 1 插入节点是根节点，变黑即可
    if (x == root) {
        x.color = BLACK;
        return;
    }
    // case 2 插入节点父亲是黑色，无需调整
    if (isBlack(x.parent)) {
        return;
    }
    /* case 3 当红红相邻，叔叔为红时
            需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
        */
    Node parent = x.parent;
    Node uncle = x.uncle();
    Node grandparent = parent.parent;
    if (isRed(uncle)) {
        parent.color = BLACK;
        uncle.color = BLACK;
        grandparent.color = RED;
        fixRedRed(grandparent);
        return;
    }

    // case 4 当红红相邻，叔叔为黑时
    if (parent.isLeftChild() && x.isLeftChild()) { // LL
        parent.color = BLACK;
        grandparent.color = RED;
        rightRotate(grandparent);
    } else if (parent.isLeftChild()) { // LR
        leftRotate(parent);
        x.color = BLACK;
        grandparent.color = RED;
        rightRotate(grandparent);
    } else if (!x.isLeftChild()) { // RR
        parent.color = BLACK;
        grandparent.color = RED;
        leftRotate(grandparent);
    } else { // RL
        rightRotate(parent);
        x.color = BLACK;
        grandparent.color = RED;
        leftRotate(grandparent);
    }
}

删除（remove）

删除操作是红黑树中比较复杂的部分。在删除节点时，同样需要通过旋转和重新着色操作来保持红黑树的性质。

public void remove(int key) {
    Node deleted = find(key);
    if (deleted == null) {
        return;
    }
    doRemove(deleted);
}

public boolean contains(int key) {
    return find(key) != null;
}

// 查找删除节点
private Node find(int key) {
    Node p = root;
    while (p != null) {
        if (key < p.key) {
            p = p.left;
        } else if (p.key < key) {
            p = p.right;
        } else {
            return p;
        }
    }
    return null;
}

// 查找剩余节点
private Node findReplaced(Node deleted) {
    if (deleted.left == null && deleted.right == null) {
        return null;
    }
    if (deleted.left == null) {
        return deleted.right;
    }
    if (deleted.right == null) {
        return deleted.left;
    }
    Node s = deleted.right;
    while (s.left != null) {
        s = s.left;
    }
    return s;
}

// 处理双黑 (case3、case4、case5)
private void fixDoubleBlack(Node x) {
    if (x == root) {
        return;
    }
    Node parent = x.parent;
    Node sibling = x.sibling();
    // case 3 兄弟节点是红色
    if (isRed(sibling)) {
        if (x.isLeftChild()) {
            leftRotate(parent);
        } else {
            rightRotate(parent);
        }
        parent.color = RED;
        sibling.color = BLACK;
        fixDoubleBlack(x);
        return;
    }
    if (sibling != null) {
        // case 4 兄弟是黑色, 两个侄子也是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            sibling.color = RED;
            if (isRed(parent)) {
                parent.color = BLACK;
            } else {
                fixDoubleBlack(parent);
            }
        }
        // case 5 兄弟是黑色, 侄子有红色
        else {
            // LL
            if (sibling.isLeftChild() && isRed(sibling.left)) {
                rightRotate(parent);
                sibling.left.color = BLACK;
                sibling.color = parent.color;
            }
            // LR
            else if (sibling.isLeftChild() && isRed(sibling.right)) {
                sibling.right.color = parent.color;
                leftRotate(sibling);
                rightRotate(parent);
            }
            // RL
            else if (!sibling.isLeftChild() && isRed(sibling.left)) {
                sibling.left.color = parent.color;
                rightRotate(sibling);
                leftRotate(parent);
            }
            // RR
            else {
                leftRotate(parent);
                sibling.right.color = BLACK;
                sibling.color = parent.color;
            }
            parent.color = BLACK;
        }
    } else {
        // @TODO 实际也不会出现，触发双黑后，兄弟节点不会为 null
        fixDoubleBlack(parent);
    }
}

private void doRemove(Node deleted) {
    Node replaced = findReplaced(deleted);
    Node parent = deleted.parent;
    // 没有孩子
    if (replaced == null) {
        // case 1 删除的是根节点
        if (deleted == root) {
            root = null;
        } else {
            if (isBlack(deleted)) {
                // 复杂调整
                fixDoubleBlack(deleted);
            } else {
                // 红色叶子, 无需任何处理
            }
            if (deleted.isLeftChild()) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            deleted.parent = null;
        }
        return;
    }
    // 有一个孩子
    if (deleted.left == null || deleted.right == null) {
        //  删除的是根节点
        if (deleted == root) {
            root.key = replaced.key;
            root.value = replaced.value;
            root.left = root.right = null;
        } else { // 只可能是红节点
            if (deleted.isLeftChild()) {
                parent.left = replaced;
            } else {
                parent.right = replaced;
            }
            replaced.parent = parent;
            deleted.left = deleted.right = deleted.parent = null;
            replaced.color = BLACK;
        }
        return;
    }
    // case 0 有两个孩子 => 有一个孩子 或 没有孩子
    int t = deleted.key;
    deleted.key = replaced.key;
    replaced.key = t;

    Object v = deleted.value;
    deleted.value = replaced.value;
    replaced.value = v;
    doRemove(replaced);
}