红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它在插入和删除节点时通过调整节点的颜色和树的结构来保持平衡，以保证查询操作的最坏时间复杂度为 O(log n)。由于其较高的查询、插入和删除效率，红黑树广泛应用于数据库、文件系统和一些常见的数据结构库中，如 Java 的 TreeMap 和 TreeSet。
下面是关于 Java 数据结构与算法中红黑树的详解，包括其定义、性质、实现方式和代码注释，帮助你深入理解红黑树的实现和工作原理。
1. 红黑树的基本概念
红黑树是一种具有以下性质的二叉查找树：
- 节点颜色：每个节点要么是红色，要么是黑色。
- 根节点：根节点始终是黑色的。
- 叶子节点（NIL 节点）：所有的叶子节点是黑色的，且这些叶子节点并不存储数据。实际上，这些叶子节点代表空的树（NIL 节点），其颜色为黑色。
- 红色节点约束：如果一个节点是红色的，则其子节点必须是黑色的。换句话说，红色节点不能连续出现。
- 路径约束：从任意节点到其所有后代叶子节点的路径上，必须包含相同数量的黑色节点。
红黑树的这些性质确保了树的高度在最坏情况下是对数级别的，这使得红黑树的查找、插入和删除操作在时间复杂度上均为 O(log n)。
2. 红黑树的操作
红黑树的主要操作包括插入、删除和查找。为了维持树的平衡，插入和删除操作可能需要通过旋转（左旋和右旋）和重新着色来调整树的结构。
2.1 查找操作
查找操作和普通的二叉查找树一样，沿着树的路径进行比较。由于红黑树是一种二叉查找树，因此查找操作的时间复杂度为 O(log n)。
2.2 插入操作
插入一个新节点后，可能会违反红黑树的性质，因此需要通过调整节点的颜色和旋转操作来恢复红黑树的平衡。插入操作分为以下几个步骤：
- 插入节点时，默认节点的颜色为红色。
- 根据红黑树的性质，检查是否违反了红黑树的性质，并根据情况进行旋转或着色操作。
2.3 删除操作
删除节点时，删除的节点有可能是红色或黑色。红色节点的删除比较简单，但黑色节点的删除则会破坏红黑树的性质，因此需要进行更多的调整。删除操作的处理较为复杂，通常包括以下几种情况：
- 删除的是红色节点：不需要进行额外的操作。
- 删除的是黑色节点：可能需要通过旋转和重着色来恢复树的平衡。
3. 红黑树的旋转
旋转是红黑树中用来调整树结构的操作。它分为左旋和右旋两种，目的是改变节点之间的父子关系。
3.1 左旋
左旋是将一个节点的右子节点提升为父节点，并将该父节点变为左子节点。旋转的步骤如下：
- 将当前节点的右子节点作为新的父节点。
- 将当前节点作为新的父节点的左子节点。
左旋操作的效果是改变树的结构，但它不会影响红黑树的性质。
3.2 右旋
右旋是将一个节点的左子节点提升为父节点，并将该父节点变为右子节点。旋转的步骤如下：
- 将当前节点的左子节点作为新的父节点。
- 将当前节点作为新的父节点的右子节点。
右旋操作也是改变树的结构，但它同样不会影响红黑树的性质。
4. 红黑树的代码实现
下面是 Java 实现红黑树的基本代码。我们将通过一个简单的红黑树类来实现插入操作，包含必要的旋转和着色操作。
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
int data;
boolean color;
Node left, right, parent;
public Node(int data) {
this.data = data;
this.color = RED; // 新插入的节点是红色
this.left = this.right = this.parent = null;
}
}
private Node root;
private Node TNULL; // 哨兵节点，所有叶子节点都指向这个节点
public RedBlackTree() {
TNULL = new Node(0); // 哨兵节点的值为0，颜色为黑色
TNULL.color = BLACK;
root = TNULL;
}
// 左旋操作
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) {
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) {
root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
// 修复插入后的红黑树性质
private void fixInsert(Node k) {
Node u;
while (k.parent.color == RED) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color == RED) {
// 叔叔节点是红色
u.color = BLACK;
k.parent.color = BLACK;
k.parent.parent.color = RED;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
k.parent.color = BLACK;
k.parent.parent.color = RED;
leftRotate(k.parent.parent);
}
} else {
u = k.parent.parent.right;
if (u.color == RED) {
u.color = BLACK;
k.parent.color = BLACK;
k.parent.parent.color = RED;
k = k.parent.parent;
} else {
if (k == k.parent.right) {
k = k.parent;
leftRotate(k);
}
k.parent.color = BLACK;
k.parent.parent.color = RED;
rightRotate(k.parent.parent);
}
}
if (k == root) {
break;
}
}
root.color = BLACK;
}
// 插入新节点
public void insert(int key) {
Node node = new Node(key);
Node y = null;
Node x = 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;
}
node.left = TNULL;
node.right = TNULL;
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(root);
}
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree();
tree.insert(7);
tree.insert(3);
tree.insert(18);
tree.insert(10);
tree.insert(22);
tree.insert(8);
tree.insert(11);
tree.insert(26);
tree.inorder();
}
}
5. 代码解析
- Node 类：表示红黑树的节点，包含数据、颜色、左子节点、右子节点和父节点的引用。
- 左旋和右旋：
leftRotate和rightRotate方法用于进行旋转操作，保持红黑树的平衡。 - fixInsert：该方法修复插入节点后的红黑树性质，确保红黑树的平衡。
- 插入操作：
insert方法用于插入新节点，插入完成后调用fixInsert方法来恢复红黑树的性质。 - 中序遍历：
inorder方法用来打印红黑树中的元素，验证插入操作是否正确。
