用Java写一个红黑树的定义代码
时间: 2023-05-26 13:02:07 浏览: 48
红黑树是一种自平衡的二叉搜索树,其中每个节点被标记为红色或黑色,满足以下规则:
1. 根节点是黑色的
2. 所有叶子节点(null节点)是黑色的
3. 如果一个节点是红色的,则它的两个子节点都是黑色的
4. 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
以下是用Java实现红黑树的代码:
```
public class RedBlackTree<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private class Node {
private Key key; // 键
private Value val; // 值
private Node left, right; // 左右子节点
private boolean color; // 连接父节点的颜色
public Node(Key key, Value val, boolean color) {
this.key = key;
this.val = val;
this.color = color;
}
}
// 判断节点的颜色
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(Key key, Value val) {
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val) {
if (h == null) return new Node(key, val, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
// 自平衡操作
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 Value get(Key key) {
Node x = root;
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp < 0) x = x.left;
else if (cmp > 0) x = x.right;
else return x.val;
}
return null;
}
}
```