红黑树（Red-Black Tree）是一种自平衡的二叉查找树（Binary Search Tree），它确保了在最坏情况下基本操作（比如插入、删除、查找）都能在O(log n)时间内完成。红黑树的关键在于它在每个节点上存储了一个额外的位用于表示节点的颜色（红色或黑色），通过一组严格的规则来保证树的大致平衡。
1.红黑树的性质
红黑树有以下五个性质：
1. 每个节点不是红色就是黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL节点）是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些性质确保了红黑树的平衡性，从而使得基本操作的时间复杂度是O(log n)。
红黑树的插入操作
插入节点时，需要重新调整树以确保红黑树的性质不被破坏。插入操作的步骤如下：
1. 将新节点插入树中，并且将其颜色设为红色。
2. 如果插入后破坏了红黑树的性质，通过旋转和重新着色来恢复树的平衡。
2.代码示例
以下是一个用Java实现的红黑树的简单示例，包括插入操作：
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
int key;
Node left, right, parent;
boolean color;
Node(int key, boolean color, Node parent) {
this.key = key;
this.color = color;
this.parent = parent;
}
}
private Node root;
public void insert(int key) {
Node newNode = new Node(key, RED, null);
if (root == null) {
root = newNode;
fixInsert(newNode);
return;
}
Node current = root;
Node parent = null;
while (current != null) {
parent = current;
if (key < current.key) {
current = current.left;
} else if (key > current.key) {
current = current.right;
} else {
return; // Duplicate keys are not allowed
}
}
newNode.parent = parent;
if (key < parent.key) {
parent.left = newNode;
} else {
parent.right = newNode;
}
fixInsert(newNode);
}
private void fixInsert(Node node) {
while (node != null && node != root && node.parent.color == RED) {
if (node.parent == node.parent.parent.left) {
Node uncle = node.parent.parent.right;
if (uncle != null && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
} else {
if (node == node.parent.right) {
node = node.parent;
rotateLeft(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
rotateRight(node.parent.parent);
}
} else {
Node uncle = node.parent.parent.left;
if (uncle != null && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
node = node.parent;
rotateRight(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
rotateLeft(node.parent.parent);
}
}
}
root.color = BLACK;
}
private void rotateLeft(Node node) {
Node right = node.right;
node.right = right.left;
if (right.left != null) {
right.left.parent = node;
}
right.parent = node.parent;
if (node.parent == null) {
root = right;
} else if (node == node.parent.left) {
node.parent.left = right;
} else {
node.parent.right = right;
}
right.left = node;
node.parent = right;
}
private void rotateRight(Node node) {
Node left = node.left;
node.left = left.right;
if (left.right != null) {
left.right.parent = node;
}
left.parent = node.parent;
if (node.parent == null) {
root = left;
} else if (node == node.parent.left) {
node.parent.left = left;
} else {
node.parent.right = left;
}
left.right = node;
node.parent = left;
}
public void inorder() {
inorderHelper(root);
}
private void inorderHelper(Node node) {
if (node != null) {
inorderHelper(node.left);
System.out.print(node.key + " ");
inorderHelper(node.right);
}
}
public static void main(String[] args) {
RedBlackTree rbt = new RedBlackTree();
int[] keys = {10, 20, 30, 15, 25, 5, 1};
for (int key : keys) {
rbt.insert(key);
}
rbt.inorder();
}
}
在这段代码中，我们实现了一个简单的红黑树，包含节点类`Node`，红黑树类`RedBlackTree`以及插入和调整的函数。`rotateLeft`和`rotateRight`函数用于旋转子树以维持平衡。`fixInsert`函数用于插入新节点后进行调整以恢复红黑树的性质。
运行这段代码会在控制台打印插入节点后的中序遍历结果，从而验证红黑树的正确性。