红黑树|这棵树平衡吗？

Question

我最近开始研究红黑树的结构，正在努力确定它是否平衡。并解释为什么它仍然是平衡的，反之亦然。

                                     10(black node)
                                       /          \
                              8(black node)       None (black node)
                              /           \
                      None(black node)   None(black node)

我只是想得到红黑树理论的解释。

Answer 1

不，那棵树不平衡。对于红黑树来说，“平衡”意味着从根到叶子的每条路径都具有相同数量的黑色节点。在您的示例树中情况并非如此，因为包含节点 8 的路径有 3 个黑色节点，而到达最右边叶子的路径只有 2 个黑色节点。

根据该规则，具有一个 NIL 子节点的节点不能拥有另一个黑色非 NIL 节点的子节点。在你的树中，根节点违反了该规则。

如果将值为 8 的节点着色为红色，则该树将成为有效的红黑树，因为这样会减少经过该节点的根到叶路径上的黑色节点的数量。