用java完成红黑树的算法
时间: 2023-11-14 17:19:16 浏览: 29
以下是Java实现红黑树的算法:
```
class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
int key;
String value;
Node left, right;
boolean color;
public Node(int key, String value, boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
}
private Node root;
private boolean isRed(Node x) {
if (x == null) {
return false;
}
return x.color == RED;
}
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}
private void flipColors(Node h) {
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
public void put(int key, String value) {
root = put(root, key, value);
root.color = BLACK;
}
private Node put(Node h, int key, String value) {
if (h == null) {
return new Node(key, value, RED);
}
if (key < h.key) {
h.left = put(h.left, key, value);
} else if (key > h.key) {
h.right = put(h.right, key, value);
} else {
h.value = value;
}
if (isRed(h.right) && !isRed(h.left)) {
h = rotateLeft(h);
}
if (isRed(h.left) && isRed(h.left.left)) {
h = rotateRight(h);
}
if (isRed(h.left) && isRed(h.right)) {
flipColors(h);
}
return h;
}
public String get(int key) {
Node x = root;
while (x != null) {
if (key < x.key) {
x = x.left;
} else if (key > x.key) {
x = x.right;
} else {
return x.value;
}
}
return null;
}
public void printInOrder() {
printInOrder(root);
}
private void printInOrder(Node x) {
if (x == null) {
return;
}
printInOrder(x.left);
System.out.println(x.key + ": " + x.value);
printInOrder(x.right);
}
}
```
在这个实现中,我们定义了一个`Node`类来表示红黑树中的节点,其中每个节点都有一个`key`和一个`value`以及一个颜色(红色或黑色)。红黑树的根节点是`root`。我们还定义了一些私有方法来辅助实现操作。
`isRed()`方法用于判断节点是否为红色。
`rotateLeft()`方法用于左旋转节点。
`rotateRight()`方法用于右旋转节点。
`flipColors()`方法用于翻转节点的颜色。
`put()`方法用于插入一个新节点到红黑树中。
`get()`方法用于获取一个节点的值。
`printInOrder()`方法用于按中序遍历方式打印红黑树中的所有节点。