java实现一个红黑树
时间: 2023-05-30 18:06:31 浏览: 50
以下是Java实现红黑树的代码:
```
public class RedBlackTree<T extends Comparable<T>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
T value;
Node left;
Node right;
boolean color;
Node(T value) {
this.value = value;
this.color = RED;
}
}
private Node root;
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);
}
if (value.compareTo(node.value) < 0) {
node.left = insert(node.left, value);
} else if (value.compareTo(node.value) > 0) {
node.right = insert(node.right, 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);
}
return node;
}
private boolean isRed(Node node) {
if (node == null) {
return BLACK;
}
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;
}
public boolean contains(T value) {
return contains(root, value);
}
private boolean contains(Node node, T value) {
if (node == null) {
return false;
}
if (value.compareTo(node.value) < 0) {
return contains(node.left, value);
} else if (value.compareTo(node.value) > 0) {
return contains(node.right, value);
} else {
return true;
}
}
}
```
在这个实现中,我们使用了一个私有内部类`Node`来表示红黑树的节点。每个节点包含了一个值、左子节点、右子节点和一个颜色标记。
通过`insert`方法,我们可以向红黑树中插入一个值。在插入过程中,我们会根据节点的颜色和位置进行旋转和重新着色操作。在插入完成后,我们将根节点的颜色设置为黑色,以保证红黑树的性质。
通过`contains`方法,我们可以判断一个值是否存在于红黑树中。在查找过程中,我们会根据值的大小和节点的值进行比较,直到找到对应的节点或者到达了叶子节点。