帮我写一个java 的红黑树
时间: 2023-09-24 08:06:45 浏览: 49
### 回答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:
红黑树是一种自平衡的二叉查找树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是红色或黑色。红黑树满足以下性质:
1. 每个节点要么是红色,要么是黑色。
2. 根节点是黑色。
3. 每个叶子节点(NIL节点,空节点)是黑色。
4. 如果一个节点是红色的,则它的两个子节点都是黑色的。
5. 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点。
下面是一个简单的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 initializeNULLNode(Node node, Node parent) {
node.data = 0;
node.parent = parent;
node.left = null;
node.right = null;
node.color = 0;
}
// 查找插入位置
private Node searchTree(Node node, int key) {
if (node == TNULL || key == node.data) {
return node;
}
if (key < node.data) {
return searchTree(node.left, key);
}
return searchTree(node.right, key);
}
// 对红黑树进行修正以保持平衡
private void fixInsert(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;
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;
}
fixInsert(node);
}
// 中序遍历红黑树
private void inorderHelper(Node node) {
if (node != TNULL) {
inorderHelper(node.left);
System.out.print(node.data + " ");
inorderHelper(node.right);
}
}
public void inorder() {
inorderHelper(this.root);
}
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(8);
rbTree.insert(18);
rbTree.insert(5);
rbTree.insert(15);
rbTree.insert(17);
rbTree.insert(25);
rbTree.insert(40);
rbTree.insert(80);
rbTree.insert(10);
rbTree.insert(11);
System.out.println("中序遍历红黑树:");
rbTree.inorder();
}
}
```
以上是一个简单的Java实现红黑树的例子,可以通过调用`insert`方法插入节点,然后调用`inorder`方法中序遍历红黑树。
### 回答3:
红黑树是一种自平衡的二叉搜索树,它在插入和删除操作后会通过旋转和染色操作来保持其平衡性。下面是一个简单的Java实现红黑树的示例代码:
```java
public class RedBlackTree {
private Node root;
private static class Node {
int data;
Node parent;
Node left;
Node right;
int color;
}
private void insert(int data) {
Node node = new Node();
node.data = data;
node.parent = null;
node.left = null;
node.right = null;
node.color = 1;
Node y = null;
Node x = this.root;
while (x != null) {
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;
fixInsert(node);
}
private void fixInsert(Node k){
Node u;
while (k.parent.color == 1) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
if (u != null && 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 != null && 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 inorder(Node node) {
if (node == null)
return;
inorder(node.left);
System.out.println(node.data + " ");
inorder(node.right);
}
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 static void main(String[] args) {
RedBlackTree rbTree = new RedBlackTree();
rbTree.insert(7);
rbTree.insert(3);
rbTree.insert(18);
rbTree.insert(10);
rbTree.insert(22);
rbTree.insert(8);
rbTree.insert(11);
rbTree.insert(26);
rbTree.insert(2);
rbTree.insert(6);
rbTree.insert(13);
rbTree.inorder(rbTree.root);
}
}
```
以上是一个基本的红黑树实现的示例,其中包含插入、旋转和染色等操作。在插入新节点时,我们会调用`fixInsert`方法来对树进行调整以保持平衡性。最后,我们通过中序遍历来检查红黑树是否正确构建。