Java 红黑树代码实现

红黑树是一种自平衡的二叉搜索树，它的特点是每个节点都有一个颜色（红色或黑色），并且满足以下规则：

1. 根节点为黑色。
2. 每个叶子节点为黑色。
3. 如果一个节点是红色，则它的子节点必须为黑色。
4. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

下面是 Java 实现红黑树的代码：

enum Color {
    RED, BLACK
}

class Node {
    int val;
    Color color;
    Node left, right, parent;

    public Node(int val) {
        this.val = val;
        this.color = Color.RED;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class RedBlackTree {
    private Node root;

    public RedBlackTree() {
        this.root = null;
    }

    private boolean isRed(Node node) {
        if (node == null) {
            return false;
        }
        return node.color == Color.RED;
    }

    private Node rotateLeft(Node node) {
        Node right = node.right;
        node.right = right.left;
        if (right.left != null) {
            right.left.parent = node;
        }
        right.parent = node.parent;
        if (node.parent == null) {
            this.root = right;
        } else if (node == node.parent.left) {
            node.parent.left = right;
        } else {
            node.parent.right = right;
        }
        right.left = node;
        node.parent = right;
        return right;
    }

    private Node rotateRight(Node node) {
        Node left = node.left;
        node.left = left.right;
        if (left.right != null) {
            left.right.parent = node;
        }
        left.parent = node.parent;
        if (node.parent == null) {
            this.root = left;
        } else if (node == node.parent.left) {
            node.parent.left = left;
        } else {
            node.parent.right = left;
        }
        left.right = node;
        node.parent = left;
        return left;
    }

    private void flipColors(Node node) {
        node.color = Color.RED;
        node.left.color = Color.BLACK;
        node.right.color = Color.BLACK;
    }

    public void insert(int val) {
        Node node = new Node(val);
        if (this.root == null) {
            this.root = node;
            this.root.color = Color.BLACK;
        } else {
            Node cur = this.root;
            while (true) {
                if (val < cur.val) {
                    if (cur.left == null) {
                        cur.left = node;
                        node.parent = cur;
                        break;
                    }
                    cur = cur.left;
                } else if (val > cur.val) {
                    if (cur.right == null) {
                        cur.right = node;
                        node.parent = cur;
                        break;
                    }
                    cur = cur.right;
                } else {
                    return;
                }
            }
            fixInsertion(node);
        }
    }

    private void fixInsertion(Node node) {
        while (isRed(node.parent)) {
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                if (isRed(uncle)) {
                    flipColors(node.parent.parent);
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.right) {
                        node = node.parent;
                        this.rotateLeft(node);
                    }
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    this.rotateRight(node.parent.parent);
                }
            } else {
                Node uncle = node.parent.parent.left;
                if (isRed(uncle)) {
                    flipColors(node.parent.parent);
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        this.rotateRight(node);
                    }
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    this.rotateLeft(node.parent.parent);
                }
            }
        }
        this.root.color = Color.BLACK;
    }

    public boolean search(int val) {
        Node cur = this.root;
        while (cur != null) {
            if (val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            } else {
                return true;
            }
        }
        return false;
    }

    public void delete(int val) {
        Node cur = this.root;
        while (cur != null) {
            if (val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            } else {
                if (cur.left == null && cur.right == null) {
                    if (cur == this.root) {
                        this.root = null;
                    } else {
                        if (isRed(cur)) {
                            fixDeletion(cur);
                        } else {
                            fixDeletion(cur);
                        }
                        if (cur.parent.left == cur) {
                            cur.parent.left = null;
                        } else {
                            cur.parent.right = null;
                        }
                    }
                } else if (cur.left != null && cur.right == null) {
                    cur.left.parent = cur.parent;
                    if (cur == this.root) {
                        this.root = cur.left;
                    } else {
                        if (cur.parent.left == cur) {
                            cur.parent.left = cur.left;
                        } else {
                            cur.parent.right = cur.left;
                        }
                        if (!isRed(cur)) {
                            fixDeletion(cur.left);
                        }
                    }
                } else if (cur.left == null && cur.right != null) {
                    cur.right.parent = cur.parent;
                    if (cur == this.root) {
                        this.root = cur.right;
                    } else {
                        if (cur.parent.left == cur) {
                            cur.parent.left = cur.right;
                        } else {
                            cur.parent.right = cur.right;
                        }
                        if (!isRed(cur)) {
                            fixDeletion(cur.right);
                        }
                    }
                } else {
                    Node min = cur.right;
                    while (min.left != null) {
                        min = min.left;
                    }
                    cur.val = min.val;
                    if (isRed(min)) {
                        fixDeletion(min);
                        min.parent.left = null;
                    } else {
                        fixDeletion(min);
                        min.parent.left = min.right;
                        if (min.right != null) {
                            min.right.parent = min.parent;
                        }
                    }
                }
                return;
            }
        }
    }

    private void fixDeletion(Node node) {
        while (node != this.root && !isRed(node)) {
            if (node == node.parent.left) {
                Node sibling = node.parent.right;
                if (isRed(sibling)) {
                    sibling.color = Color.BLACK;
                    node.parent.color = Color.RED;
                    this.rotateLeft(node.parent);
                    sibling = node.parent.right;
                }
                if (!isRed(sibling.left) && !isRed(sibling.right)) {
                    sibling.color = Color.RED;
                    node = node.parent;
                } else {
                    if (!isRed(sibling.right)) {
                        sibling.left.color = Color.BLACK;
                        sibling.color = Color.RED;
                        this.rotateRight(sibling);
                        sibling = node.parent.right;
                    }
                    sibling.color = node.parent.color;
                    node.parent.color = Color.BLACK;
                    sibling.right.color = Color.BLACK;
                    this.rotateLeft(node.parent);
                    node = this.root;
                }
            } else {
                Node sibling = node.parent.left;
                if (isRed(sibling)) {
                    sibling.color = Color.BLACK;
                    node.parent.color = Color.RED;
                    this.rotateRight(node.parent);
                    sibling = node.parent.left;
                }
                if (!isRed(sibling.left) && !isRed(sibling.right)) {
                    sibling.color = Color.RED;
                    node = node.parent;
                } else {
                    if (!isRed(sibling.left)) {
                        sibling.right.color = Color.BLACK;
                        sibling.color = Color.RED;
                        this.rotateLeft(sibling);
                        sibling = node.parent.left;
                    }
                    sibling.color = node.parent.color;
                    node.parent.color = Color.BLACK;
                    sibling.left.color = Color.BLACK;
                    this.rotateRight(node.parent);
                    node = this.root;
                }
            }
        }
        node.color = Color.BLACK;
    }
}

其中，`Node` 类表示红黑树的节点，`Color` 枚举类型表示节点颜色。`RedBlackTree` 类是红黑树的实现，包含插入、查找、删除等基本操作。其中，`fixInsertion` 和 `fixDeletion` 分别用于修复插入和删除操作后可能破坏红黑树性质的情况。其他方法包括 `rotateLeft`、`rotateRight` 和 `flipColors` 分别用于左旋、右旋和颜色翻转操作，以保持红黑树性质。