Java红黑树代码实现

### 回答1：
Java红黑树是一种自平衡二叉搜索树，它是在二叉查找树的基础上添加了一些限制，以保证树的平衡。红黑树的着色性质，即每个节点要么是红色的，要么是黑色的，并且有以下几条性质：

1. 每个节点要么是红色的，要么是黑色的。
2. 根节点是黑色的。
3. 每个叶子节点都是黑色的。
4. 如果一个节点是红色的，那么它的子节点一定是黑色的。
5. 对于任意一个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑色节点。

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

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

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

    public Node(int key, boolean color) {
      this.key = key;
      this.color = color;
    }
  }

  private Node root;

  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, RED);
    }

    if (key < h.key) {
      h.left = put(h.left, key);
    } else if (key > h.key) {
      h.right = put(h.right, key);
    } else {
      h.key = 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)) {
      flipCol  

### 回答2：
红黑树是一种自平衡的二叉搜索树，它的实现方法比较复杂。下面是一个简单的Java红黑树代码实现示例：

// 定义红黑树节点
class Node {
int data; // 节点数据
Node left; // 左子节点
Node right; // 右子节点
Node parent; // 父节点
boolean isRed; // 是否是红色节点

public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
this.isRed = true; // 默认新插入的节点为红色
}
}

// 定义红黑树
class RedBlackTree {
private Node root; // 根节点

// 插入节点
public void insert(int data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
root.isRed = false; // 根节点为黑色
} else {
Node current = root; // 从根节点开始搜索插入位置
Node parent;
while (true) {
parent = current;
if (data < current.data) { // 插入值小于当前节点值
current = current.left;
if (current == null) {
parent.left = newNode;
newNode.parent = parent;
fixInsert(newNode); // 插入后修正红黑树
return;
}
} else { // 插入值大于等于当前节点值
current = current.right;
if (current == null) {
parent.right = newNode;
newNode.parent = parent;
fixInsert(newNode); // 插入后修正红黑树
return;
}
}
}
}
}

// 修正插入后的红黑树
private void fixInsert(Node node) {
Node parent, grandparent, uncle;
while (node.parent != null && node.parent.isRed) { // 父节点为红色时需要修正
parent = node.parent;
grandparent = parent.parent;
if (parent == grandparent.left) { // 父节点为祖父节点的左子节点
uncle = grandparent.right;
if (uncle != null && uncle.isRed) { // Case 1: 叔叔节点也是红色
parent.isRed = false;
uncle.isRed = false;
grandparent.isRed = true;
node = grandparent; // 修改当前节点为祖父节点，继续往上修正
} else {
if (node == parent.right) { // Case 2: 叔叔节点是黑色且当前节点是父节点的右子节点
leftRotate(parent);
node = parent;
parent = node.parent; // 修改当前节点为父节点，进入Case 3
}
// Case 3: 叔叔节点是黑色且当前节点是父节点的左子节点
rightRotate(grandparent);
parent.isRed = false;
grandparent.isRed = true;
node = parent.parent; // 修改当前节点为祖父节点，继续往上修正
}
} else { // 父节点为祖父节点的右子节点（与父节点为左子节点的情况完全相反）
uncle = grandparent.left;
if (uncle != null && uncle.isRed) { // Case 4: 叔叔节点也是红色
parent.isRed = false;
uncle.isRed = false;
grandparent.isRed = true;
node = grandparent; // 修改当前节点为祖父节点，继续往上修正
} else {
if (node == parent.left) { // Case 5: 叔叔节点是黑色且当前节点是父节点的左子节点
rightRotate(parent);
node = parent;
parent = node.parent; // 修改当前节点为父节点，进入Case 6
}
// Case 6: 叔叔节点是黑色且当前节点是父节点的右子节点
leftRotate(grandparent);
parent.isRed = false;
grandparent.isRed = true;
node = parent.parent; // 修改当前节点为祖父节点，继续往上修正
}
}
}
root.isRed = false; // 根节点始终为黑色
}

// 左旋转
private void leftRotate(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 rightRotate(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.left) {
node.parent.left = leftChild;
} else {
node.parent.right = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
}

// 测试红黑树的插入操作
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(5);
tree.insert(25);
}
}

以上是一个简单的红黑树实现示例，实际上红黑树的代码实现还要考虑更多细节。使用红黑树可以实现高效地插入、删除和查找操作，这对于需要经常对数据进行插入和删除操作的场景非常有用。  

### 回答3：
红黑树（Red-Black Tree）是一种自平衡的二叉查找树。它在每个节点上增加了一个存储位来表示节点的颜色，可以为红色或黑色。通过对任何一条从根到叶子的路径上各个节点重新着色和调整树的结构，红黑树保证了在最坏情况下基本动态集合操作的时间复杂度为O(log n)。

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

public class RedBlackTree<Key extends Comparable<Key>, Value> {
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node {
private Key key;
private Value value;
private Node left, right;
private boolean color;
private int size;

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

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

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

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

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

public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
return get(root, key);
}

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

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

public void put(Key key, Value value) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
if (value == null) {
delete(key);
return;
}
root = put(root, key, value);
root.color = BLACK; // root节点始终为黑色
}

private Node put(Node node, Key key, Value value) {
if (node == null) return new Node(key, value, RED, 1);
int cmp = key.compareTo(node.key);
if (cmp < 0) node.left = put(node.left, key, value);
else if (cmp > 0) node.right = put(node.right, key, 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);

node.size = size(node.left) + size(node.right) + 1;
return node;
}

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

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

private void flipColors(Node node) {
node.color = !node.color;
node.left.color = !node.left.color;
node.right.color = !node.right.color;
}

public void deleteMin() {
if (isEmpty()) throw new NoSuchElementException("Tree is empty");
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMin(root);
if (!isEmpty()) root.color = BLACK;
}

private Node deleteMin(Node 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);
}

public void deleteMax() {
if (isEmpty()) throw new NoSuchElementException("Tree is empty");
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMax(root);
if (!isEmpty()) root.color = BLACK;
}

private Node deleteMax(Node node) {
if (isRed(node.left))
node = rotateRight(node);
if (node.right == null)
return null;
if (!isRed(node.right) && !isRed(node.right.left))
node = moveRedRight(node);
node.right = deleteMax(node.right);
return balance(node);
}

public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
if (!contains(key)) return;
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = delete(root, key);
if (!isEmpty()) root.color = BLACK;
}

private Node delete(Node node, Key key) {
if (key.compareTo(node.key) < 0) {
if (!isRed(node.left) && !isRed(node.left.left))
node = moveRedLeft(node);
node.left = delete(node.left, key);
} else {
if (isRed(node.left))
node = rotateRight(node);
if (key.compareTo(node.key) == 0 && (node.right == null))
return null;
if (!isRed(node.right) && !isRed(node.right.left))
node = moveRedRight(node);
if (key.compareTo(node.key) == 0) {
Node min = min(node.right);
node.key = min.key;
node.value = min.value;
node.right = deleteMin(node.right);
} else {
node.right = delete(node.right, key);
}
}
return balance(node);
}

private Node moveRedLeft(Node node) {
flipColors(node);
if (isRed(node.right.left)) {
node.right = rotateRight(node.right);
node = rotateLeft(node);
flipColors(node);
}
return node;
}

private Node moveRedRight(Node node) {
flipColors(node);
if (!isRed(node.left.left))
node = rotateRight(node);
return node;
}

private Node balance(Node 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);
node.size = size(node.left) + size(node.right) + 1;
return node;
}

public Key min() {
if (isEmpty()) throw new NoSuchElementException("Tree is empty");
return min(root).key;
}

private Node min(Node node) {
if (node.left == null) return node;
return min(node.left);
}

public Key max() {
if (isEmpty()) throw new NoSuchElementException("Tree is empty");
return max(root).key;
}

private Node max(Node node) {
if (node.right == null) return node;
return max(node.right);
}

public Iterable<Key> keys() {
if (isEmpty()) return new LinkedList<>();
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hi) {
if (lo == null) throw new IllegalArgumentException("Low key cannot be null");
if (hi == null) throw new IllegalArgumentException("High key cannot be null");

LinkedList<Key> queue = new LinkedList<>();
keys(root, queue, lo, hi);
return queue;
}

private void keys(Node node, LinkedList<Key> queue, Key lo, Key hi) {
if (node == null) return;
int cmpLo = lo.compareTo(node.key);
int cmpHi = hi.compareTo(node.key);
if (cmpLo < 0) keys(node.left, queue, lo, hi);
if (cmpLo <= 0 && cmpHi >= 0) queue.add(node.key);
if (cmpHi > 0) keys(node.right, queue, lo, hi);

}
}

这是一个简单的Java实现红黑树的代码。每个节点包含一个键、值、颜色以及左右子节点的引用。通过一系列的旋转操作和着色调整，确保了红黑树的平衡性。代码提供了插入、删除、查找等基本操作的实现，同时还支持取最小值、最大值和范围查找等功能。