red-black-tree - 将元素插入到只需要颜色更改且无需旋转的红/黑树中？

Question

我怎样才能找到一个元素序列，如果插入到红/黑树中，将完全通过改变颜色而不是执行旋转来平衡？

Answer 1

您需要确保新节点始终填充 RB 树的最底部未填充层。例如，如果您有一棵有两个节点的树，它总是不平衡的一面，同样，如果您的树有四个节点，它将是第三“行”上剩余的三个插槽之一。

能够对任意数据执行此操作几乎需要已对任意数据进行排序（无论是在数组中还是在其他方式中）。当然，如果您从已排序的数据创建 RB 树，您甚至不需要更改颜色，所有上层节点都可以是黑色，而未填充层中的任何节点（其中只能有一个）将如果有缺失的节点是红色的，或者如果没有缺失的节点可以是全红或全黑。如果您的数据未排序，您最终会遇到下一个可用节点不适合可用插槽的情况。