红黑树

[giscus[bot]]

红黑树

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

https://oi-wiki.org/ds/rbtree/

[ongiant]

建议加上AA树这种特殊的红黑树，代码实现也非常简单

[2378822760]

插入的case6中，若N为左子节点，应该是右旋祖父借点

[MTDickens]

删除的平衡维护，可以理解为：

1. 我删除了 $N$，将 $N$ 变成了 $N' = Nil$，从而，任意经过该 $N'$ 的路径的黑色节点数量相比 $N$ 减小了 1（其它路径不变）
2. 因此，我必须执行函数 $maintain(N')$，使得执行函数之后

• 任意经过该 $N'$ 的路径的黑色节点数量增加 1
• 其他路径不变

3. 从而，我们执行上述删除操作的 Case 1 ~ Case 5

---

其中，Case 3 里面，父节点、兄弟节点全部都是黑色的，侄子节点均为 NIL。
我们将兄弟节点变成红色。目前，任意经过该 $N'$ 的父节点路径的黑色节点数量相比 $N$ 减小了 1（其它不变）。我们当前的任务转变为

• 任意经过 $N'$ 父节点的路径的黑色节点数量增加 1
• 其他路径不变

从而，我们把维护的锅甩给了父节点，只需递归执行 $maintain(parent(N'))$ 即可

[lq252392]

删除的Case 4第一步应该是旋转S，代码也是旋转S，但是正文写成了旋转P。
删除的Case3可以粗糙的理解为：引入一个 双重黑 来维护黑高不变，然后不断向上传递，传递到根的时候还是双重黑，那么直接变为正常黑节点就行，此时黑高减一。

[KikyouKushida]

删除调整里面漏掉了兄弟结点是黑色，两个 nephew 都是红色的情况了吧

[isteven-shu]

"右旋操作会使得 T3 子树上结点的深度均减 1"
这里不应该是加1吗？