红黑树(Red-Black Tree)是一种自平衡的二叉搜索树,它满足以下五个特性:
- 每个节点要么是红色,要么是黑色。
- 根节点是黑色的。
- 所有叶子节点(NIL节点,空节点)是黑色的。
- 如果一个节点是红色的,则它的两个子节点都是黑色的(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
- 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点(称为黑高度)。
特点
-
自动平衡:红黑树通过旋转和重新着色操作来保持树的平衡,从而确保查询、插入和删除操作的时间复杂度都是对数级别的。
-
高效:由于红黑树的平衡性,使得查找、插入和删除等操作的时间复杂度都是O(log n),其中n是树中节点的数量。
-
黑高度平衡:红黑树保证了从根到叶子节点的最长路径不会超过最短路径的两倍,从而保证了树的平衡性。
基本操作(Java实现)
由于红黑树的实现相对复杂,这里只给出一些基本操作的基本思路和伪代码,并不提供完整的Java实现。
插入操作
- 将新节点插入为红色。
- 如果违反了性质4(即新节点的父节点是红色),则进行颜色调整。
- 如果违反了性质5(即黑高度不平衡),则进行旋转操作。
删除操作
- 如果要删除的节点有两个子节点,则找到其后继节点(或前驱节点),用后继节点(或前驱节点)的值替换要删除的节点,并删除后继节点(或前驱节点)。
- 将要删除的节点(或其替代节点)的颜色设为红色(如果原本是黑色)。
- 如果违反了性质5(即黑高度不平衡),则进行旋转和颜色调整操作。
旋转操作
旋转操作包括左旋和右旋,它们用于在插入或删除节点后重新平衡树。
- 左旋:将当前节点的右子节点提升为当前节点的父节点,并将当前节点变为右子节点的左子节点。
- 右旋:将当前节点的左子节点提升为当前节点的父节点,并将当前节点变为左子节点的右子节点。
颜色调整
颜色调整操作通常与旋转操作一起使用,用于在插入或删除节点后保持红黑树的性质。
注意事项
红黑树的实现需要仔细处理各种边界情况和特殊情况,以确保树的正确性和平衡性。因此,在实际编写红黑树的代码时,需要特别注意各种细节和异常情况的处理。
public class RedBlackTree<T extends Comparable<T>> { | |
private static final boolean RED = true; | |
private static final boolean BLACK = false; | |
private class Node<T> { | |
T key; | |
Node<T> left; | |
Node<T> right; | |
Node<T> parent; | |
boolean color; | |
Node(T key, boolean color, Node<T> parent) { | |
this.key = key; | |
this.color = color; | |
this.parent = parent; | |
this.left = null; | |
this.right = null; | |
} | |
} | |
private Node<T> root; | |
// 旋转操作 | |
private void rotateLeft(Node<T> x) { | |
Node<T> 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 rotateRight(Node<T> y) { | |
Node<T> x = y.left; | |
y.left = x.right; | |
if (x.right != null) { | |
x.right.parent = y; | |
} | |
x.parent = y.parent; | |
if (y.parent == null) { | |
root = x; | |
} else if (y == y.parent.left) { | |
y.parent.left = x; | |
} else { | |
y.parent.right = x; | |
} | |
x.right = y; | |
y.parent = x; | |
} | |
// 插入修复 | |
private void fixInsert(Node<T> k) { | |
while (k.parent != null && k.parent.color == RED) { | |
if (k.parent == k.parent.parent.right) { | |
Node<T> u = k.parent.parent.left; | |
if (u != null && u.color == RED) { | |
k.parent.color = BLACK; | |
u.color = BLACK; | |
k.parent.parent.color = RED; | |
k = k.parent.parent; | |
} else { | |
if (k == k.parent.left) { | |
k = k.parent; | |
rotateRight(k); | |
} | |
k.parent.color = BLACK; | |
k.parent.parent.color = RED; | |
rotateLeft(k.parent.parent); | |
} | |
} else { | |
// 镜像处理左子树的情况 | |
Node<T> u = k.parent.parent.right; | |
if (u != null && u.color == RED) { | |
k.parent.color = BLACK; | |
u.color = BLACK; | |
k.parent.parent.color = RED; | |
k = k.parent.parent; | |
} else { | |
if (k == k.parent.right) { | |
k = k.parent; | |
rotateLeft(k); | |
} | |
k.parent.color = BLACK; | |
k.parent.parent.color = RED; | |
rotateRight(k.parent.parent); | |
} | |
} | |
} | |
root.color = BLACK; | |
} | |
// 插入新节点 | |
public void insert(T key) { | |
Node<T> y = null; | |
Node<T> x = root; | |
while (x != null) { | |
y = x; | |
if (key.compareTo(x.key) < 0) { | |
x = x.left; | |
} else { | |
x = x.right; | |
} | |
} | |
Node<T> z = new Node<>( |
Node<T>(key, RED, y); | |
if (y == null) { | |
root = z; | |
} else if (key.compareTo(y.key) < 0) { | |
y.left = z; | |
} else { | |
y.right = z; | |
} | |
// 修复插入后的红黑树性质 | |
fixInsert(z); | |
} | |
// 中序遍历(用于打印树结构) | |
private void inorder(Node<T> root) { | |
if (root != null) { | |
inorder(root.left); | |
System.out.print(root.key + " "); | |
inorder(root.right); | |
} | |
} | |
// 主函数或测试代码 | |
public static void main(String[] args) { | |
RedBlackTree<Integer> tree = new RedBlackTree<>(); | |
// 插入元素进行测试 | |
tree.insert(3); | |
tree.insert(1); | |
tree.insert(4); | |
tree.insert(2); | |
tree.insert(5); | |
tree.insert(0); | |
// 打印树结构 | |
System.out.println("Inorder traversal of the constructed tree: "); | |
tree.inorder(tree.root); | |
} | |
} |
这段代码提供了一个完整的红黑树实现,包括插入、修复插入后红黑树性质的方法以及中序遍历用于打印树结构。main
函数中创建了一个 RedBlackTree
对象,并插入了几个整数,然后打印了树的中序遍历结果。
请注意,由于红黑树的实现相对复杂,此代码仅作为一个基本的示例,可能还需要进一步的错误检查和优化,以确保在所有情况下都能正确工作。此外,对于删除操作和其他高级功能,如查找最小/最大元素、查找特定元素等,需要额外的实现。