红黑树代码实现java
时间: 2023-11-07 22:04:32 浏览: 48
红黑树是一种自平衡的二叉查找树,它具有以下特性:
1. 每个节点要么是红色,要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点(NIL节点,空节点)都是黑色的。
4. 如果一个节点是红色的,则它的两个子节点都是黑色的。
5. 对于每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑色节点。
下面是一个红黑树的Java代码实现:
```java
package RBTree;
public class RedBlackTree {
private RBTreeNode root;
public void insert(int key) {
RBTreeNode newNode = new RBTreeNode(key);
if (root == null) {
root = newNode;
root.setColor(RBTreeNode.BLACK);
return;
}
RBTreeNode current = root;
RBTreeNode parent;
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeft();
if (current == null) {
parent.setLeft(newNode);
newNode.setParent(parent);
break;
}
} else {
current = current.getRight();
if (current == null) {
parent.setRight(newNode);
newNode.setParent(parent);
break;
}
}
}
fixInsert(newNode);
}
private void fixInsert(RBTreeNode node) {
while (node.getParent().getColor() == RBTreeNode.RED) {
if (node.getParent() == node.getParent().getParent().getLeft()) {
RBTreeNode uncle = node.getParent().getParent().getRight();
if (uncle != null && uncle.getColor() == RBTreeNode.RED) {
node.getParent().setColor(RBTreeNode.BLACK);
uncle.setColor(RBTreeNode.BLACK);
node.getParent().getParent().setColor(RBTreeNode.RED);
node = node.getParent().getParent();
} else {
if (node == node.getParent().getRight()) {
node = node.getParent();
leftRotate(node);
}
node.getParent().setColor(RBTreeNode.BLACK);
node.getParent().getParent().setColor(RBTreeNode.RED);
rightRotate(node.getParent().getParent());
}
} else {
RBTreeNode uncle = node.getParent().getParent().getLeft();
if (uncle != null && uncle.getColor() == RBTreeNode.RED) {
node.getParent().setColor(RBTreeNode.BLACK);
uncle.setColor(RBTreeNode.BLACK);
node.getParent().getParent().setColor(RBTreeNode.RED);
node = node.getParent().getParent();
} else {
if (node == node.getParent().getLeft()) {
node = node.getParent();
rightRotate(node);
}
node.getParent().setColor(RBTreeNode.BLACK);
node.getParent().getParent().setColor(RBTreeNode.RED);
leftRotate(node.getParent().getParent());
}
}
}
root.setColor(RBTreeNode.BLACK);
}
private void leftRotate(RBTreeNode node) {
RBTreeNode rightChild = node.getRight();
node.setRight(rightChild.getLeft());
if (rightChild.getLeft() != null) {
rightChild.getLeft().setParent(node);
}
rightChild.setParent(node.getParent());
if (node.getParent() == null) {
root = rightChild;
} else if (node == node.getParent().getLeft()) {
node.getParent().setLeft(rightChild);
} else {
node.getParent().setRight(rightChild);
}
rightChild.setLeft(node);
node.setParent(rightChild);
}
private void rightRotate(RBTreeNode node) {
RBTreeNode leftChild = node.getLeft();
node.setLeft(leftChild.getRight());
if (leftChild.getRight() != null) {
leftChild.getRight().setParent(node);
}
leftChild.setParent(node.getParent());
if (node.getParent() == null) {
root = leftChild;
} else if (node == node.getParent().getRight()) {
node.getParent().setRight(leftChild);
} else {
node.getParent().setLeft(leftChild);
}
leftChild.setRight(node);
node.setParent(leftChild);
}
// 其他操作(如删除、查找等)可以根据需要进行实现
@Override
public String toString() {
return "RedBlackTree{" +
"root=" + root +
'}';
}
}
```
以上代码实现了红黑树的插入操作,并包含了左旋和右旋方法。你可以根据需要继续完善其他操作。
我还可以回答其他关于红黑树的问题,如果你有的话。