Java 红黑树实现：插入、删除、查找操作详解

红黑树是一种自平衡的二叉搜索树，它的实现比较复杂，但是它的性能比较稳定，可以保证在最坏情况下的时间复杂度为O(logn)。下面是一个简单的 Java 版的红黑树实现。

首先，我们需要定义一个节点类，它包含了一个值、左右子树、颜色等信息：

class RBNode<T extends Comparable<T>> {
    T val;
    RBNode<T> left, right;
    boolean isRed;

    public RBNode(T val) {
        this.val = val;
        isRed = true;
    }
}

接下来，我们需要实现插入、删除、查找等操作。

插入操作：

public void insert(T val) {
    root = insert(root, val);
    root.isRed = false;
}

private RBNode<T> insert(RBNode<T> node, T val) {
    if (node == null) {
        return new RBNode<>(val);
    }

    if (val.compareTo(node.val) < 0) {
        node.left = insert(node.left, val);
    } else if (val.compareTo(node.val) > 0) {
        node.right = insert(node.right, val);
    } else {
        return node;
    }

    if (isRed(node.right) && !isRed(node.left)) {
        node = rotateLeft(node);
    }
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rotateRight(node);
    }
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }

    return node;
}

删除操作：

public void delete(T val) {
    if (!contains(val)) {
        return;
    }

    if (!isRed(root.left) && !isRed(root.right)) {
        root.isRed = true;
    }

    root = delete(root, val);
    if (root != null) {
        root.isRed = false;
    }
}

private RBNode<T> delete(RBNode<T> node, T val) {
    if (val.compareTo(node.val) < 0) {
        if (!isRed(node.left) && !isRed(node.left.left)) {
            node = moveRedLeft(node);
        }
        node.left = delete(node.left, val);
    } else {
        if (isRed(node.left)) {
            node = rotateRight(node);
        }
        if (val.compareTo(node.val) == 0 && node.right == null) {
            return null;
        }
        if (!isRed(node.right) && !isRed(node.right.left)) {
            node = moveRedRight(node);
        }
        if (val.compareTo(node.val) == 0) {
            RBNode<T> min = findMin(node.right);
            node.val = min.val;
            node.right = deleteMin(node.right);
        } else {
            node.right = delete(node.right, val);
        }
    }

    return balance(node);
}

查找操作：

public boolean contains(T val) {
    RBNode<T> cur = root;
    while (cur != null) {
        if (val.compareTo(cur.val) < 0) {
            cur = cur.left;
        } else if (val.compareTo(cur.val) > 0) {
            cur = cur.right;
        } else {
            return true;
        }
    }
    return false;
}

辅助操作：

private boolean isRed(RBNode<T> node) {
    if (node == null) {
        return false;
    }
    return node.isRed;
}

private RBNode<T> rotateLeft(RBNode<T> node) {
    RBNode<T> x = node.right;
    node.right = x.left;
    x.left = node;
    x.isRed = node.isRed;
    node.isRed = true;
    return x;
}

private RBNode<T> rotateRight(RBNode<T> node) {
    RBNode<T> x = node.left;
    node.left = x.right;
    x.right = node;
    x.isRed = node.isRed;
    node.isRed = true;
    return x;
}

private void flipColors(RBNode<T> node) {
    node.isRed = !node.isRed;
    node.left.isRed = !node.left.isRed;
    node.right.isRed = !node.right.isRed;
}

private RBNode<T> moveRedLeft(RBNode<T> node) {
    flipColors(node);
    if (isRed(node.right.left)) {
        node.right = rotateRight(node.right);
        node = rotateLeft(node);
        flipColors(node);
    }
    return node;
}

private RBNode<T> moveRedRight(RBNode<T> node) {
    flipColors(node);
    if (isRed(node.left.left)) {
        node = rotateRight(node);
        flipColors(node);
    }
    return node;
}

private RBNode<T> findMin(RBNode<T> node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

private RBNode<T> deleteMin(RBNode<T> node) {
    if (node.left == null) {
        return null;
    }

    if (!isRed(node.left) && !isRed(node.left.left)) {
        node = moveRedLeft(node);
    }

    node.left = deleteMin(node.left);
    return balance(node);
}

private RBNode<T> balance(RBNode<T> node) {
    if (isRed(node.right)) {
        node = rotateLeft(node);
    }
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rotateRight(node);
    }
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }
    return node;
}

最后，我们需要实现一些辅助方法，比如获取树的高度、输出树的结构等。

完整代码如下：

public class RedBlackTree<T extends Comparable<T>> {
    private RBNode<T> root;

    // 插入节点
    public void insert(T val) {
        root = insert(root, val);
        root.isRed = false;
    }

    private RBNode<T> insert(RBNode<T> node, T val) {
        if (node == null) {
            return new RBNode<>(val);
        }

        if (val.compareTo(node.val) < 0) {
            node.left = insert(node.left, val);
        } else if (val.compareTo(node.val) > 0) {
            node.right = insert(node.right, val);
        } else {
            return node;
        }

        // 维护红黑树性质
        if (isRed(node.right) && !isRed(node.left)) {
            node = rotateLeft(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rotateRight(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }

        return node;
    }

    // 删除节点
    public void delete(T val) {
        if (!contains(val)) {
            return;
        }

        if (!isRed(root.left) && !isRed(root.right)) {
            root.isRed = true;
        }

        root = delete(root, val);
        if (root != null) {
            root.isRed = false;
        }
    }

    private RBNode<T> delete(RBNode<T> node, T val) {
        if (val.compareTo(node.val) < 0) {
            // 左子树上查找
            if (!isRed(node.left) && !isRed(node.left.left)) {
                node = moveRedLeft(node);
            }
            node.left = delete(node.left, val);
        } else {
            // 右子树上查找
            if (isRed(node.left)) {
                node = rotateRight(node);
            }
            if (val.compareTo(node.val) == 0 && node.right == null) {
                return null;
            }
            if (!isRed(node.right) && !isRed(node.right.left)) {
                node = moveRedRight(node);
            }
            if (val.compareTo(node.val) == 0) {
                // 找到要删除的节点
                RBNode<T> min = findMin(node.right);
                node.val = min.val;
                node.right = deleteMin(node.right);
            } else {
                node.right = delete(node.right, val);
            }
        }

        // 维护红黑树性质
        return balance(node);
    }

    // 查找节点
    public boolean contains(T val) {
        RBNode<T> cur = root;
        while (cur != null) {
            if (val.compareTo(cur.val) < 0) {
                cur = cur.left;
            } else if (val.compareTo(cur.val) > 0) {
                cur = cur.right;
            } else {
                return true;
            }
        }
        return false;
    }

    // 辅助操作
    private boolean isRed(RBNode<T> node) {
        if (node == null) {
            return false;
        }
        return node.isRed;
    }

    private RBNode<T> rotateLeft(RBNode<T> node) {
        RBNode<T> x = node.right;
        node.right = x.left;
        x.left = node;
        x.isRed = node.isRed;
        node.isRed = true;
        return x;
    }

    private RBNode<T> rotateRight(RBNode<T> node) {
        RBNode<T> x = node.left;
        node.left = x.right;
        x.right = node;
        x.isRed = node.isRed;
        node.isRed = true;
        return x;
    }

    private void flipColors(RBNode<T> node) {
        node.isRed = !node.isRed;
        node.left.isRed = !node.left.isRed;
        node.right.isRed = !node.right.isRed;
    }

    private RBNode<T> moveRedLeft(RBNode<T> node) {
        flipColors(node);
        if (isRed(node.right.left)) {
            node.right = rotateRight(node.right);
            node = rotateLeft(node);
            flipColors(node);
        }
        return node;
    }

    private RBNode<T> moveRedRight(RBNode<T> node) {
        flipColors(node);
        if (isRed(node.left.left)) {
            node = rotateRight(node);
            flipColors(node);
        }
        return node;
    }

    private RBNode<T> findMin(RBNode<T> node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    private RBNode<T> deleteMin(RBNode<T> node) {
        if (node.left == null) {
            return null;
        }

        if (!isRed(node.left) && !isRed(node.left.left)) {
            node = moveRedLeft(node);
        }

        node.left = deleteMin(node.left);
        return balance(node);
    }

    private RBNode<T> balance(RBNode<T> node) {
        if (isRed(node.right)) {
            node = rotateLeft(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rotateRight(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }
        return node;
    }
}