Java设计一棵红黑树,方法包括插入节点,删除节点和查找节点
时间: 2024-05-15 18:19:40 浏览: 11
红黑树是一种自平衡二叉查找树,它保证了插入、删除和查找操作的最坏情况时间复杂度为 O(log n)。红黑树的节点有两种颜色,红色和黑色,同时满足以下性质:
1. 根节点为黑色;
2. 所有叶子节点都是黑色;
3. 如果一个节点是红色的,则它的两个子节点都是黑色的;
4. 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点;
5. 每个节点的左子树和右子树都是红黑树。
下面是 Java 实现红黑树的代码:
```
public class RedBlackTree<T extends Comparable<T>> {
private Node<T> root;
private static final boolean RED = true;
private static final boolean BLACK = false;
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 void insert(T value) {
root = insert(root, value);
root.color = BLACK;
}
private Node<T> insert(Node<T> node, T value) {
if (node == null) {
return new Node<>(value, RED);
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node.left = insert(node.left, value);
} else if (cmp > 0) {
node.right = insert(node.right, 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;
}
// 删除节点
public void delete(T value) {
if (root == null) {
return;
}
if (!isRed(root.left) && !isRed(root.right)) {
root.color = RED;
}
root = delete(root, value);
if (root != null && !isRed(root.left) && !isRed(root.right)) {
root.color = BLACK;
}
}
private Node<T> delete(Node<T> node, T value) {
if (value.compareTo(node.value) < 0) {
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = delete(node.left, value);
} else {
if (isRed(node.left)) {
node = rotateRight(node);
}
if (value.compareTo(node.value) == 0 && node.right == null) {
return null;
}
if (!isRed(node.right) && !isRed(node.right.left)) {
node = moveRedRight(node);
}
if (value.compareTo(node.value) == 0) {
Node<T> min = findMin(node.right);
node.value = min.value;
node.right = deleteMin(node.right);
} else {
node.right = delete(node.right, value);
}
}
return balance(node);
}
// 查找节点
public Node<T> find(T value) {
Node<T> node = root;
while (node != null) {
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
return node;
}
}
return null;
}
private boolean isRed(Node<T> node) {
return node != null && 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;
}
private Node<T> moveRedLeft(Node<T> node) {
flipColors(node);
if (isRed(node.right.left)) {
node.right = rotateRight(node.right);
node = rotateLeft(node);
flipColors(node);
}
return node;
}
private Node<T> moveRedRight(Node<T> node) {
flipColors(node);
if (isRed(node.left.left)) {
node = rotateRight(node);
flipColors(node);
}
return node;
}
private Node<T> findMin(Node<T> node) {
while (node.left != null) {
node = node.left;
}
return node;
}
private Node<T> deleteMin(Node<T> node) {
if (node.left == null) {
return null;
}
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = deleteMin(node.left);
return balance(node);
}
private Node<T> balance(Node<T> node) {
if (isRed(node.right)) {
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;
}
}
```
其中,插入节点和删除节点都需要进行旋转和颜色翻转等操作来保证红黑树的性质。查找节点则是一个简单的二叉查找。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)