java 红黑树代码实现

红黑树是一种自平衡的二叉搜索树，它的每个节点都被标记为红色或黑色。通过一系列的旋转和颜色变化操作，红黑树保证了树的高度始终是log(n)，从而保证了树的查找、插入和删除等操作的时间复杂度都是O(log(n))。

下面是一个简单的Java代码实现：

public class RedBlackTree<T extends Comparable<T>> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node<T> root;

    private static class Node<T> {
        T value;
        Node<T> left, right;
        boolean color; // true for RED, false for BLACK
        Node(T value, boolean color) {
            this.value = value;
            this.color = color;
        }
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void insert(T value) {
        root = insert(root, value);
        root.color = BLACK;
    }

    private Node<T> insert(Node<T> node, T value) {
        if (node == null) {
            return new Node<>(value, RED);
        }
        int cmp = value.compareTo(node.value);
        if (cmp < 0) {
            node.left = insert(node.left, value);
        } else if (cmp > 0) {
            node.right = insert(node.right, value);
        } else {
            node.value = value;
        }
        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;
    }

    private boolean isRed(Node<T> node) {
        return node != null && node.color == RED;
    }

    private Node<T> rotateLeft(Node<T> node) {
        Node<T> x = node.right;
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

    private Node<T> rotateRight(Node<T> node) {
        Node<T> x = node.left;
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

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

在这个实现中，我们用一个Node类来表示红黑树的节点，每个节点有一个值、左右子节点和一个颜色属性。我们用RED和BLACK常量来表示颜色属性。

在insert方法中，我们首先递归地找到要插入的位置。如果节点为空，我们就创建一个新节点并将颜色设置为红色。如果节点已经存在，我们就更新节点的值。接着，我们按照红黑树的规则进行旋转和颜色变化操作，以保证树的平衡性。

在rotateLeft和rotateRight方法中，我们分别进行左旋和右旋操作。在flipColors方法中，我们将当前节点和它的左右子节点的颜色进行翻转。

这样，我们就完成了一个简单的红黑树的实现。