帮我写一个java 的红黑树
时间: 2023-09-22 13:06:16 浏览: 55
### 回答1:
红黑树是一种自平衡二叉查找树,其中任意一个节点的左右子树的高度相差不超过1。红黑树还有一些其他的性质,包括:
1. 根节点是黑色的
2. 所有叶子节点都是黑色的(叶子节点是指没有子节点的节点)
3. 每个红色节点的两个子节点都是黑色的(也就是说,不存在两个连续的红色节点)
4. 从任意节点到其叶子节点的所有路径都包含相同数目的黑色节点
这里是一个简单的Java实现:
```
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
int key;
Node left, right;
boolean color;
Node(int key, boolean color) {
this.key = key;
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 = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
public void put(int key) {
root = put(root, key);
root.color = BLACK;
}
private Node put(Node h, int key) {
if (h == null) return new Node(key, RED);
if (key < h.key) h.left = put(h.left, key);
### 回答2:
红黑树是一种自平衡的二叉查找树,通过保持节点的平衡和向上维护性质,保证了树的高度始终为 O(log n)。下面是一个简单的Java实现红黑树的示例:
```java
// 定义红黑树的节点
class Node {
int data;
Node parent;
Node left;
Node right;
boolean isRed; // true为红色,false为黑色
public Node(int data) {
this.data = data;
this.isRed = true;
}
}
// 红黑树
class RedBlackTree {
private Node root;
// 左旋
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
// 右旋
private void rightRotate(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != null) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
// 插入
public void insert(int key) {
Node newNode = new Node(key);
Node y = null;
Node x = this.root;
while (x != null) {
y = x;
if (newNode.data < x.data) {
x = x.left;
} else {
x = x.right;
}
}
newNode.parent = y;
if (y == null) { // 如果树为空
this.root = newNode;
} else if (newNode.data < y.data) {
y.left = newNode;
} else {
y.right = newNode;
}
newNode.isRed = true;
insertFixUp(newNode);
}
// 调整红黑树
private void insertFixUp(Node node) {
while (node.parent != null && node.parent.isRed) {
if (node.parent == node.parent.parent.left) {
Node y = node.parent.parent.right;
if (y != null && y.isRed) {
node.parent.isRed = false;
y.isRed = false;
node.parent.parent.isRed = true;
node = node.parent.parent;
} else {
if (node == node.parent.right) {
node = node.parent;
leftRotate(node);
}
node.parent.isRed = false;
node.parent.parent.isRed = true;
rightRotate(node.parent.parent);
}
} else {
Node y = node.parent.parent.left;
if (y != null && y.isRed) {
node.parent.isRed = false;
y.isRed = false;
node.parent.parent.isRed = true;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
node = node.parent;
rightRotate(node);
}
node.parent.isRed = false;
node.parent.parent.isRed = true;
leftRotate(node.parent.parent);
}
}
}
this.root.isRed = false;
}
}
```
这是一个简单的红黑树的Java实现,包括了插入和调整红黑树的操作。你可以根据需要对其中的功能进行扩展和修改。希望对你有所帮助!
### 回答3:
红黑树是一种自平衡二叉查找树,其插入、删除和查找操作的时间复杂度都是O(log n)。下面是一个简单的Java实现红黑树的代码:
```
public class RedBlackTree<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
private Key key;
private Value value;
private Node left, right;
private boolean isRed;
public Node(Key key, Value value, boolean isRed) {
this.key = key;
this.value = value;
this.isRed = isRed;
}
}
private boolean isRed(Node node) {
if (node == null) {
return false;
}
return node.isRed;
}
public void put(Key key, Value value) {
root = put(root, key, value);
root.isRed = false;
}
private Node put(Node node, Key key, Value value) {
if (node == null) {
return new Node(key, value, true);
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = put(node.left, key, value);
} else if (cmp > 0) {
node.right = put(node.right, key, value);
} else {
node.value = 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 Node rotateLeft(Node node) {
Node x = node.right;
node.right = x.left;
x.left = node;
x.isRed = node.isRed;
node.isRed = true;
return x;
}
private Node rotateRight(Node node) {
Node x = node.left;
node.left = x.right;
x.right = node;
x.isRed = node.isRed;
node.isRed = true;
return x;
}
private void flipColors(Node node) {
node.isRed = true;
node.left.isRed = false;
node.right.isRed = false;
}
}
```
以上是一个简单的红黑树的Java实现,包含了基本的插入操作。你可以通过调用`put`方法来插入新的键值对。请注意,此代码仅用于例示,并不包含完整的红黑树功能。