以下是一個簡單的紅黑樹實現代碼示例:
class Node {
int data;
Node left, right, parent;
boolean color; // true表示紅色,false表示黑色
public Node(int data) {
this.data = data;
this.color = true; // 新插入的節點默認為紅色
this.left = this.right = this.parent = null;
}
}
public 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) {
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) {
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 data) {
Node newNode = new Node(data);
Node parent = null;
Node current = root;
while (current != null) {
parent = current;
if (data < current.data) {
current = current.left;
} else {
current = current.right;
}
}
newNode.parent = parent;
if (parent == null) {
root = newNode;
} else if (data < parent.data) {
parent.left = newNode;
} else {
parent.right = newNode;
}
insertFixUp(newNode);
}
// 紅黑樹插入修正
private void insertFixUp(Node x) {
while (x != root && x.parent.color == true) {
if (x.parent == x.parent.parent.left) {
Node y = x.parent.parent.right;
if (y != null && y.color == true) {
x.parent.color = false;
y.color = false;
x.parent.parent.color = true;
x = x.parent.parent;
} else {
if (x == x.parent.right) {
x = x.parent;
leftRotate(x);
}
x.parent.color = false;
x.parent.parent.color = true;
rightRotate(x.parent.parent);
}
} else {
Node y = x.parent.parent.left;
if (y != null && y.color == true) {
x.parent.color = false;
y.color = false;
x.parent.parent.color = true;
x = x.parent.parent;
} else {
if (x == x.parent.left) {
x = x.parent;
rightRotate(x);
}
x.parent.color = false;
x.parent.parent.color = true;
leftRotate(x.parent.parent);
}
}
}
root.color = false;
}
// 中序遍歷打印紅黑樹
public void inorderTraversal(Node node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
}
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.inorderTraversal(rbTree.root);
}
}
以上是一個簡單的紅黑樹實現,包含了插入和修正操作。您可以根據需要進行進一步擴展和優化。