Red-Black Tree

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

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

性质

• 节点为红色或黑色

• NIL 节点（空叶子节点）为黑色

• 红色节点的子节点为黑色

• 从根节点到 NIL 节点的每条路径上的黑色节点数量相同