红黑树
进阶红黑树追求"足够平衡"，而不是 AVL 那样的严格平衡。
// 算法讲解
红黑树
示例强调颜色约束如何把“最坏高度”控制在可接受范围内。
待机
速度 中
待机 ⌨1enum Color { RED, BLACK };
2
3struct Node {
4 int key;
5 Color color;
6 Node* left;
7 Node* right;
8 Node* parent;
9};
10
11bool isRed(Node* node) {
12 return node != nullptr && node->color == RED;
13}
复杂度分析
时间 查找/插入/删除 O(log n)
空间 O(n)
最优 O(log n)
最坏 O(log n)
算法讲解
红黑树给每个节点附加红或黑两种颜色，并规定根是黑色、红节点不能相邻、任一路径黑高相同等规则。
这些规则保证树高不会失控，从而把查找、插入、删除都维持在 O(log n)。
相比 AVL，红黑树旋转次数通常更少，因此在标准库 map、set 等容器里非常常见。
学习重点不是死记修复分支，而是理解颜色规则如何限制最坏树高。