java红黑树代码实现

### 回答1：
红黑树是一种自平衡二叉查找树，它在保持二叉查找树基本性质的同时，通过对节点进行染色，保持了树的平衡，从而保证了最坏情况下的时间复杂度为 O(log n)。

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

public class RedBlackTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        private K key;
        private V value;
        private Node left, right;
        private boolean color;
        private int size;

        public Node(K key, V value, boolean color, int size) {
            this.key = key;
            this.value = value;
            this.color = color;
            this.size = size;
        }
    }

    private Node root;

    public RedBlackTree() {
    }

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

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

    public int size() {
        return size(root);
    }

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

    public V get(K key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return get(root, key);
    }

    private V get(Node x, K key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) x = x.left;
            else if (cmp > 0) x = x.right;
            else return x.value;
        }
        return null;
    }

    public boolean contains(K key) {
        return get(key) != null;
    }

    public void put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");
        if (value == null) {
            delete(key);
            return;
        }
        root = put(root, key, value);
        root.color = BLACK;
    }

    private Node put(Node h, K key, V value) {
        if (h == null) return new Node(key, value, RED, 1);

        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, value);
        else if (cmp > 0) h.right = put(h.right, key, value);
        else h.value = value;

        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 void deleteMin() {
        if (isEmpty()) throw new NoSuchElementException("BST underflow");

        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;

        root = deleteMin(root);
        if (!isEmpty()) root.color = BLACK;
    }

    private Node deleteMin(Node h) {
        if (h.left == null)
            return null;

        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);

        h.left = deleteMin  

### 回答2：
红黑树是一种自平衡的二叉查找树，它在进行插入和删除操作时能够维持良好的平衡性，保证了查找、插入和删除的时间复杂度为O(log n)。

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

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

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

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

private Node root;

public RedBlackTree() {
root = null;
}

private Node findNode(int key) {
Node current = root;
while (current != null) {
if (key < current.key) {
current = current.left;
} else if (key > current.key) {
current = current.right;
} else {
return current;
}
}
return null;
}

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

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

public void insert(int key) {
Node newNode = new Node(key);
Node current = root;
Node parent = null;

while (current != null) {
parent = current;
if (newNode.key < current.key) {
current = current.left;
} else {
current = current.right;
}
}

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

fixInsert(newNode);
}

private void fixInsert(Node node) {
while (node != root && node.parent.color == RED) {
if (node.parent == node.parent.parent.left) {
Node uncle = node.parent.parent.right;
if (uncle != null && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
} else {
if (node == node.parent.right){
node = node.parent;
rotateLeft(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
rotateRight(node.parent.parent);
}
} else {
Node uncle = node.parent.parent.left;
if (uncle != null && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
} else {
if (node == node.parent.left){
node = node.parent;
rotateRight(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
rotateLeft(node.parent.parent);
}
}
}
root.color = BLACK;
}
}

这段代码实现了红黑树的插入操作。红黑树的插入操作分为以下几步：首先，按照二叉查找树的规则将新节点插入到适当的位置，并将其颜色设置为红色；接着，通过一系列的旋转和颜色调整来保持红黑树的平衡性。

其中，rotateLeft()和rotateRight()分别实现了左旋和右旋操作，用于保持树的平衡性；findNode()方法用于查找具有指定键值的节点；insert()方法表示向红黑树中插入一个新节点，并在插入后调用fixInsert()方法进行修复操作。

在修复操作中，通过不断旋转和颜色调整来保持树的平衡性，直到满足红黑树的性质。  

### 回答3：
红黑树是一种自平衡的二叉搜索树，其中每个节点都有一个附加的存储位来表示节点的颜色，可以是红色或黑色。红黑树具有以下性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL节点，空节点）都是黑色。
4. 每个红色节点的两个子节点都是黑色。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

以下是实现红黑树的Java代码示例：

// 定义红黑树节点类
class RBTreeNode {
int key; // 节点键值
int color; // 节点颜色（0表示红色，1表示黑色）
RBTreeNode left; // 左子节点
RBTreeNode right; // 右子节点
RBTreeNode parent; // 父节点

public RBTreeNode(int key, int color) {
this.key = key;
this.color = color;
this.left = null;
this.right = null;
this.parent = null;
}
}

// 红黑树类
class RedBlackTree {
private RBTreeNode root;

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

// 左旋
private void leftRotate(RBTreeNode x) {
RBTreeNode y = x.right;
x.right = y.left;

if (y.left != null) {
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(RBTreeNode x) {
RBTreeNode y = x.left;
x.left = y.right;

if (y.right != null) {
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;
}

// 插入节点
public void insert(int key) {
RBTreeNode node = new RBTreeNode(key, 0); // 新插入的节点默认为红色
RBTreeNode y = null;
RBTreeNode x = this.root;

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

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

insertFixup(node);
}

// 插入修复操作
private void insertFixup(RBTreeNode node) {
while (node.parent != null && node.parent.color == 0) { // 当父节点为红色时需要修复
if (node.parent == node.parent.parent.left) { // 当父节点是祖父节点的左子节点
RBTreeNode uncle = node.parent.parent.right; // 叔节点

if (uncle != null && uncle.color == 0) { // 叔节点存在且为红色
node.parent.color = 1;
uncle.color = 1;
node.parent.parent.color = 0;
node = node.parent.parent;
} else { // 叔节点不存在或为黑色
if (node == node.parent.right) {
node = node.parent;
leftRotate(node);
}

node.parent.color = 1;
node.parent.parent.color = 0;
rightRotate(node.parent.parent);
}
} else { // 当父节点是祖父节点的右子节点
RBTreeNode uncle = node.parent.parent.left; // 叔节点

if (uncle != null && uncle.color == 0) { // 叔节点存在且为红色
node.parent.color = 1;
uncle.color = 1;
node.parent.parent.color = 0;
node = node.parent.parent;
} else { // 叔节点不存在或为黑色
if (node == node.parent.left) {
node = node.parent;
rightRotate(node);
}

node.parent.color = 1;
node.parent.parent.color = 0;
leftRotate(node.parent.parent);
}
}
}

this.root.color = 1; // 根节点为黑色
}
}

以上是一个简单的Java红黑树的代码实现，实现了插入功能并保持树的红黑性质。