java 红黑树代码

### 回答1：
java 红黑树是一种二叉搜索树，其中的每个节点都具有颜色属性，要么是红色，要么是黑色。红黑树的节点颜色可以是"红色"或"黑色"。这种树遵循以下几条规则：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 每个叶子节点都是黑色的空节点（NIL节点）。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 对于任意节点而言，其到叶子节点的每条路径都包含相同数目的黑色节点。

在 Java 中，可以使用 java.util.TreeMap 类来实现红黑树。这个类实现了映射接口，允许将键映射到值。它使用红黑树来维护映射关系，保证映射关系有序。

下面是一个简单的示例，展示了如何使用 TreeMap 类将字符串映射到整数：

import java.util.TreeMap;

public class RedBlackTreeExample {
    public static void main(String[] args) {
        // 创建一个 TreeMap 对象
        TreeMap<String, Integer> map = new TreeMap<>();

        // 向 TreeMap 中添加映射关系
        map.put("Apple", 10);
        map.put("Banana", 20);
        map.put("Orange", 30);
        map.put("Mango", 40);

        // 输出 TreeMap 中的映射  

### 回答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;
}

// 插入节点
public 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 node) {
Node uncle;

while (node.parent.color == 1) {
if (node.parent == node.parent.parent.right) {
uncle = node.parent.parent.left;

if (uncle != null && uncle.color == 1) {
uncle.color = 0;
node.parent.color = 0;
node.parent.parent.color = 1;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
node = node.parent;
rightRotate(node);
}

node.parent.color = 0;
node.parent.parent.color = 1;
leftRotate(node.parent.parent);
}
} else {
uncle = node.parent.parent.right;

if (uncle != null && uncle.color == 1) {
uncle.color = 0;
node.parent.color = 0;
node.parent.parent.color = 1;
node = node.parent.parent;
} else {
if (node == node.parent.right) {
node = node.parent;
leftRotate(node);
}

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

if (node == root) {
break;
}
}

root.color = 0;
}

// 左旋转
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;
}

// 打印红黑树的中序遍历结果
public void printTree(Node node) {
if (node == TNULL) {
return;
}
printTree(node.left);
System.out.print(node.key + " ");
printTree(node.right);
}
}

// 测试
public class Main {
public static void main(String[] args) {
RedBlackTree rbTree = new RedBlackTree();

rbTree.insert(55);
rbTree.insert(10);
rbTree.insert(5);
rbTree.insert(2);
rbTree.insert(8);
rbTree.insert(15);
rbTree.insert(16);

System.out.println("红黑树中序遍历结果：");
rbTree.printTree(rbTree.root);
}
}

以上是一个简单的红黑树的Java代码实现，其中包括插入节点、修正插入导致的红黑树性质被破坏、左旋转、右旋转等操作。在测试部分，插入了一些节点，并打印了红黑树的中序遍历结果。

红黑树的代码实现相对复杂，但是它的自平衡性质让它在各种操作下具有较好的性能。希望以上的代码示例能对你理解红黑树的实现有所帮助。