用java实现一个红黑树
时间: 2023-11-12 17:59:06 浏览: 32
红黑树是一种自平衡二叉查找树,它保证了插入、删除和查找的时间复杂度均为O(log n)。下面是一个简单的Java实现:
```java
public class RedBlackTree<T extends Comparable<T>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private class Node {
T value;
Node left, right;
boolean color;
Node(T value, boolean color) {
this.value = value;
this.color = color;
}
}
public void insert(T value) {
root = insert(root, value);
root.color = BLACK;
}
private Node insert(Node node, T value) {
if (node == null) {
return new Node(value, RED);
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node.left = insert(node.left, value);
} else if (cmp > 0) {
node.right = insert(node.right, value);
} else {
node.value = value;
}
// Fix-up any violations of the red-black tree properties.
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.color == RED;
}
private Node rotateLeft(Node node) {
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
private Node rotateRight(Node node) {
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
private void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
}
```
这个实现中,我们使用内部类 `Node` 表示红黑树中的节点。红黑树的插入操作通过递归实现,如果插入的节点违反了红黑树的性质,则进行相应的旋转和颜色翻转来修复。
注意,在插入节点时,我们总是把新插入的节点标记为红色,因为这样可以更容易地保证红黑树的平衡性质。当然,在插入完成后,我们需要将根节点标记为黑色。
另外,我们还定义了两个常量 `RED` 和 `BLACK`,用于表示红色和黑色节点。这样可以让代码更加清晰易懂。