你能写一段java描述红黑树的代码吗
时间: 2023-05-14 20:07:28 浏览: 56
当然可以,以下是一段简单的 Java 代码描述红黑树:
```
public class RedBlackTree {
private Node root;
private static class Node {
int key;
Node left;
Node right;
boolean isRed;
Node(int key, boolean isRed) {
this.key = key;
this.isRed = isRed;
}
}
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, true);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node;
}
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;
}
}
```
这段代码实现了红黑树的插入操作,其中包括了左旋、右旋和颜色翻转等操作。