通过将每个节点的“父”存储在红黑树中来简化哪些操作？

Question

一些红黑树实现为每个节点存储父项。

哪些常见操作（insert，remove，pop_min，pop_max，iteration ...等）可以简化使用这些额外的信息？

Answer 1

有一位家长帮助任何可能需要加强树的操作，这些包括迭代和删除（包括弹出最小/最大）。

找到下一个祖先（可能是祖父母或更远）似乎是有或没有父指针的O（log n）操作，但它们并不相同，因为大多数节点位于具有父级的树意味着在典型情况下只需要一步升级（并且该步骤已经是已知的），而在没有父级的情况下，在大多数情况下必须降级大部分树。基本上有一个父指针反转了祖先搜索问题。从一个实现方面（而不是算法）我也发现插入更容易与父 - 我喜欢实现重新平衡插入和删除作为迭代循环，而不是递归尾部调用。