帮我用Java写个红黑树
时间: 2023-09-03 09:26:06 浏览: 70
### 回答1:
好的,这是一个简单的红黑树 Java 实现。
```
class Node {
int key, color;
Node left, right, parent;
Node(int key) {
this.key = key;
left = right = parent = null;
color = 1;
}
}
class RedBlackTree {
private static final int RED = 0;
private static final int BLACK = 1;
Node root;
private Node rotateLeft(Node node) {
Node rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left != null) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (node.parent == null) {
root = rightChild;
} else if (node == node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
rightChild.left = node;
node.parent = rightChild;
return rightChild;
}
private Node rotateRight(Node node) {
Node leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right != null) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (node.parent == null) {
root = leftChild;
} else if (node == node.parent.right) {
node.parent.right = leftChild;
} else {
node.parent.left = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
return leftChild;
}
private void fixAfterInsertion(Node node) {
node.color = RED;
while (node != null && node != root && node.parent.color == RED) {
Node parent = node.parent;
Node grandParent = parent.parent;
Node uncle = grandParent.right;
if (parent == grandParent.left) {
uncle = grandParent.right;
if (uncle != null && uncle.color == RED) {
uncle.color = BLACK;
parent.color = BLACK;
grandParent.color = RED;
node = grandParent;
} else {
if (node == parent.right) {
node = parent;
rotateLeft(node);
}
parent.color = BLACK;
grandParent.color = RED;
rotateRight(grandParent);
}
} else {
uncle = grandParent.left;
if (uncle != null && uncle.color == RED) {
uncle.color = BLACK;
parent.color = BLACK;
grandParent.color = RED;
node = grandParent;
} else {
if (node == parent.left) {
node = parent;
rotateRight(node);
}
parent.color = BLACK;
grandParent.color = RED;
rotateLeft(grandParent);
}
### 回答2:
红黑树是一种自平衡的二叉查找树,它在插入和删除节点时通过一系列的变换操作来保持平衡。下面是一个用Java编写的红黑树示例:
```java
// 创建红黑树节点类
class Node {
int data;
Node parent;
Node left;
Node right;
int color;
public Node(int data) {
this.data = data;
}
}
public class RedBlackTree {
private Node root;
private Node TNULL;
// 前序遍历红黑树的辅助函数
private void preOrderHelper(Node node) {
if (node != TNULL) {
System.out.print(node.data + " ");
preOrderHelper(node.left);
preOrderHelper(node.right);
}
}
// 中序遍历红黑树的辅助函数
private void inOrderHelper(Node node) {
if (node != TNULL) {
inOrderHelper(node.left);
System.out.print(node.data + " ");
inOrderHelper(node.right);
}
}
// 后序遍历红黑树的辅助函数
private void postOrderHelper(Node node) {
if (node != TNULL) {
postOrderHelper(node.left);
postOrderHelper(node.right);
System.out.print(node.data + " ");
}
}
// 搜索树中包含给定值的节点
private Node searchTreeHelper(Node node, int key) {
if (node == TNULL || key == node.data) {
return node;
}
if (key < node.data) {
return searchTreeHelper(node.left, key);
}
return searchTreeHelper(node.right, key);
}
// 将节点插入红黑树中
private void insertFix(Node k) {
Node u;
while (k.parent.color == 1) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left; // 叔父节点
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
leftRotate(k.parent.parent);
}
} else {
u = k.parent.parent.right; // 叔父节点
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.right) {
k = k.parent;
leftRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
rightRotate(k.parent.parent);
}
}
if (k == root) {
break;
}
}
root.color = 0;
}
// 旋转红黑树节点
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != TNULL) {
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 != TNULL) {
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 node = new Node(key);
node.parent = null;
node.data = key;
node.left = TNULL;
node.right = TNULL;
node.color = 1; // 1代表红色,0代表黑色
Node y = null;
Node x = this.root;
while (x != TNULL) {
y = x;
if (node.data < x.data) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y == null) {
root = node;
} else if (node.data < y.data) {
y.left = node;
} else {
y.right = node;
}
if (node.parent == null) {
node.color = 0;
return;
}
if (node.parent.parent == null) {
return;
}
insertFix(node);
}
// 对外前序遍历红黑树函数
public void preorder() {
preOrderHelper(this.root);
}
// 对外中序遍历红黑树函数
public void inorder() {
inOrderHelper(this.root);
}
// 对外后序遍历红黑树函数
public void postorder() {
postOrderHelper(this.root);
}
// 对外搜索红黑树包含给定值的节点函数
public Node searchTree(int k) {
return searchTreeHelper(this.root, k);
}
public RedBlackTree() {
TNULL = new Node(0);
TNULL.color = 0;
TNULL.left = null;
TNULL.right = null;
root = TNULL;
}
public static void main(String[] args) {
RedBlackTree rbTree = new RedBlackTree();
rbTree.insert(10);
rbTree.insert(20);
rbTree.insert(30);
rbTree.insert(40);
rbTree.insert(50);
rbTree.insert(25);
System.out.println("前序遍历:");
rbTree.preorder();
System.out.println("\n中序遍历:");
rbTree.inorder();
System.out.println("\n后序遍历:");
rbTree.postorder();
System.out.println("\n搜索结果:");
System.out.println(rbTree.searchTree(40));
}
}
```
上述代码实现了一个简单的红黑树,其中包括节点类`Node`和红黑树类`RedBlackTree`。`RedBlackTree`类中提供了插入节点、前序遍历、中序遍历、后序遍历和搜索红黑树的方法。通过main函数可以看到红黑树的基本使用方法和结果展示。