用JAVA写一段红黑树示例代码
时间: 2023-07-25 09:32:09 浏览: 43
好的,以下是一个简单的红黑树示例代码,使用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 key;
Node left, right;
boolean color;
public Node(T key, boolean color) {
this.key = key;
this.color = color;
}
}
public void insert(T key) {
root = insert(root, key);
root.color = BLACK;
}
private Node insert(Node node, T key) {
if (node == null) return new Node(key, RED);
int cmp = key.compareTo(node.key);
if (cmp < 0) node.left = insert(node.left, key);
else if (cmp > 0) node.right = insert(node.right, key);
else node.key = key;
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;
}
}
```
这段代码实现了一个红黑树数据结构,其中每个节点都有一个键和一个颜色(红色或黑色)。在插入一个新键时,根据红黑树的规则进行自平衡操作,以确保树保持平衡。
您可以通过创建一个`RedBlackTree`对象并调用其`insert`方法来使用这个实现。例如,以下代码将创建一个红黑树,并将10个整数插入到树中:
```java
RedBlackTree<Integer> tree = new RedBlackTree<>();
for (int i = 1; i <= 10; i++) {
tree.insert(i);
}
```