用java写个红黑树
时间: 2023-07-27 09:19:04 浏览: 39
好的,下面是 Java 实现红黑树的基本代码,供您参考:
```java
public class RedBlackTree<T extends Comparable<T>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node<T> root;
private static class Node<T> {
T value;
Node<T> left, right;
boolean color;
Node(T value, boolean color) {
this.value = value;
this.color = color;
}
}
public boolean contains(T value) {
return contains(root, value);
}
private boolean contains(Node<T> node, T value) {
if (node == null) {
return false;
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
return contains(node.left, value);
} else if (cmp > 0) {
return contains(node.right, value);
} else {
return true;
}
}
public void add(T value) {
root = add(root, value);
root.color = BLACK;
}
private Node<T> add(Node<T> node, T value) {
if (node == null) {
return new Node<>(value, RED);
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node.left = add(node.left, value);
} else if (cmp > 0) {
node.right = add(node.right, value);
} else {
// Value already exists in the tree
return node;
}
// Fix 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<T> node) {
if (node == null) {
return false;
}
return node.color == RED;
}
private Node<T> rotateLeft(Node<T> node) {
Node<T> x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
private Node<T> rotateRight(Node<T> node) {
Node<T> x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
private void flipColors(Node<T> node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
}
```
上述代码实现的是一个基本的红黑树,包含了节点的颜色、左右子节点和旋转等操作。您可以根据需要进行修改和扩展。