用Java写一个红黑树实现代码

### 回答1：
我可以回答这个问题。以下是一个用Java实现的红黑树代码示例：

public class RedBlackTree {
    private Node root;
    
    private static class Node {
        int key;
        Node left;
        Node right;
        boolean isRed;
        
        Node(int key) {
            this.key = key;
            this.isRed = true;
        }
    }
    
    public void insert(int key) {
        root = insert(root, key);
        root.isRed = false;
    }
    
    private Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key);
        }
        
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        }
        
        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 node) {
        if (node == null) {
            return false;
        }
        return node.isRed;
    }
    
    private Node rotateLeft(Node node) {
        Node x = node.right;
        node.right = x.left;
        x.left = node;
        x.isRed = node.isRed;
        node.isRed = true;
        return x;
    }
    
    private Node rotateRight(Node node) {
        Node x = node.left;
        node.left = x.right;
        x.right = node;
        x.isRed = node.isRed;
        node.isRed = true;
        return x;
    }
    
    private void flipColors(Node node) {
        node.isRed = true;
        node.left.isRed = false;
        node.right.isRed = false;
    }
}

希望这个代码示例能够帮助你实现红黑树。

### 回答2：
红黑树是一种自平衡的二叉查找树，其主要特点是能够始终保持树的平衡，从而保证查询、插入和删除操作的时间复杂度都是O(log n)。

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

// 定义红黑树节点
class Node {
    int key;
    Node parent;
    Node left;
    Node right;
    int color;
}

// 红黑树类
class RedBlackTree {
    private Node root;
    private Node TNULL;

    // 构造方法
    public RedBlackTree() {
        TNULL = new Node();
        TNULL.color = 0;
        TNULL.left = null;
        TNULL.right = null;
        root = TNULL;
    }
    
    // 左旋操作
    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // 右旋操作
    private void rightRotate(Node x) {
        Node y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    // 插入节点
    private void insert(int key) {
        Node node = new Node();
        node.parent = null;
        node.key = key;
        node.left = TNULL;
        node.right = TNULL;
        node.color = 1;

        Node y = null;
        Node x = this.root;

        while (x != TNULL) {
            y = x;
            if (node.key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node;
        } else if (node.key < y.key) {
            y.left = node;
        } else {
            y.right = node;
        }

        if (node.parent == null){
            node.color = 0;
            return;
        }

        if (node.parent.parent == null) {
            return;
        }

        fixInsert(node);
    }

    // 插入后平衡红黑树
    private void fixInsert(Node k){
        Node u;
        while (k.parent.color == 1) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left;
                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rightRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    leftRotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right;

                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        leftRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    rightRotate(k.parent.parent);
                }
            }
            if (k == root) {
                break;
            }
        }
        root.color = 0;
    }

    // 打印红黑树
    private void printTree(Node root, String indent, boolean last) {
        if (root != TNULL) {
            System.out.print(indent);
            if (last) {
                System.out.print("└─");
                indent += "  ";
            } else {
                System.out.print("├─");
                indent += "| ";
            }

            String sColor = root.color == 1?"RED":"BLACK";
            System.out.println(root.key + "(" + sColor + ")");
            printTree(root.left, indent, false);
            printTree(root.right, indent, true);
        }
    }

    // 公开的插入方法
    public void insert(int key) {
        insert(key);
    }

    // 公开的打印方法
    public void printTree() {
        printTree(this.root, "", true);
    }
}

// 测试红黑树
public class Main {
    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(15);
        tree.insert(18);
        tree.insert(25);
        tree.printTree();
    }
}

以上代码通过使用Node类表示红黑树中的节点，并使用红黑颜色值0和1来标记节点的颜色（0为黑色，1为红色）。具体的实现包括左旋操作、右旋操作、插入节点和插入后平衡红黑树等方法，并提供了一个公开的插入方法和打印方法，方便对红黑树进行测试和演示。

在测试部分，我们创建了一个红黑树对象tree，然后调用insert方法插入了一些测试数据，并通过调用printTree方法打印出红黑树的结构。

### 回答3：
红黑树是一种自平衡的二叉搜索树，具有高效的插入、删除和查找操作。以下是用Java实现红黑树的代码：

class RedBlackTree {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    private class Node {
        int key;
        Node left;
        Node right;
        int size;
        boolean color;

        Node(int key) {
            this.key = key;
            this.size = 1;
            this.color = RED;
        }
    }

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

    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.size = h.size;
        h.size = 1 + size(h.left) + size(h.right);
        return x;
    }

    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.size = h.size;
        h.size = 1 + size(h.left) + size(h.right);
        return x;
    }

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

    private int size(Node x) {
        if (x == null) return 0;
        return x.size;
    }

    public void put(int key) {
        root = put(root, key);
        root.color = BLACK;
    }

    private Node put(Node h, int key) {
        if (h == null) return new Node(key);

        if (key < h.key) {
            h.left = put(h.left, key);
        } else if (key > h.key) {
            h.right = put(h.right, key);
        }

        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;
    }

    public boolean contains(int key) {
        return contains(root, key);
    }

    private boolean contains(Node x, int key) {
        if (x == null) return false;
        if (key < x.key) {
            return contains(x.left, key);
        } else if (key > x.key) {
            return contains(x.right, key);
        } else {
            return true;
        }
    }
}

这个红黑树实现代码包括实现插入操作的`put()`方法和查询操作的`contains()`方法。每个节点都具有键值对(`key`)，左子节点(`left`)和右子节点(`right`)。红黑树通过旋转操作和颜色变换来保持平衡。插入操作中，根据节点关系和颜色判断是否需要进行旋转和颜色变换。`contains()`方法通过递归遍历树来查找指定的键值是否存在。

以上是一个简单的红黑树实现代码，你可以根据需要进行修改和扩展。