Red-Black Tree

红黑树是一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡。

红黑树是 4 阶 B 树（2-3-4 树）的变体。

性质 - 节点为红色或黑色 - NIL 节点（空叶子节点）为黑色 - 红色节点的子节点为黑色 - 从根节点到 NIL 节点的每条路径上的黑色节点数量相同

Note

部分资料中还加入了第五条性质，即根节点必须为黑色，这条性质要求完成插入操作后若根节点为红色则将其染黑，但由于将根节点染黑的操作也可以延迟至删除操作时进行，因此，该条性质并非必须满足（本文给出的代码实现中满足该性质）。