在红黑树中，自上而下的删除是否比自下而上的删除更快、更节省空间？

Question

根据此页面 http://www.eternallyconfuzzled.com/tuts/datastructs/jsw_tut_rbtree.aspx< /a> “自上而下删除”是红黑树节点删除的一种实现，它通过将红色节点向下推入树来主动平衡树，从而保证被删除的叶节点是红色的。 由于叶子节点保证是红色的，因此您不必担心重新平衡树，因为删除红色叶子节点不会违反任何规则，并且您不必执行任何额外的操作来重新平衡树。平衡并恢复红黑度。

“自下而上删除”涉及到在树上进行正常的二分搜索以找到要删除的节点，交换叶节点（如果找到的节点不是叶节点），然后恢复红黑树属性通过爬回树上同时修复红黑规则违规行为。

自上而下的删除是否可以最大限度地减少重新平衡操作的次数？ 是否有可能自上而下的删除在向下的过程中主动进行了太多的重新着色和重新平衡？

这种情况怎么样：（x）表示红色节点

               8
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

如果我想删除16，自下而上的删除不会做任何重新平衡，但自上而下的删除会一直向下重新着色节点，然后才发现重新着色操作是不必要的：

迭代 1：

              (8)
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

迭代 2：

               8
         _____/ \____
        /            \
      (4)            (12)
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

迭代 3：

               8
         _____/ \____
        /            \
      (4)             12
     /   \          /    \
   2       6     (10)    (14)
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

然后在迭代 4 中，您发现不需要下推，因为 16 已经是红色了。 那么自上而下的删除是否更节省时间和空间呢？

Answer 1

据我所知：“自上而下删除”避免了在操作过程中多次遍历路径中的同一节点。 因此，考虑到从根到给定节点的简单路径，如果您要对该路径中的节点执行某些操作，为什么不直接在下行路径上执行呢？ 它避免了必须多次遍历部分路径。 因此，这节省了时间。

类似的原理也适用于 2-3-4 树（a,b 树的特殊子情况）中的多个操作（包括插入）。

自上而下的删除是否可以最大程度地减少重新平衡操作的数量？

认为，在一般情况下，确实如此。 因为您可以更轻松地随后插入某些内容，而只需很少的重新平衡操作。

是否有可能自上而下的删除在向下的过程中主动进行了太多的重新着色和重新平衡？

也许吧，但这取决于数据集。 不过，如上所述。 这可以总体上减少重新着色和重新平衡的次数。

Answer 2

自上而下是否比自下而上更有效空间？

总之，是的。 永远令人困惑中提出的自顶向下算法不需要节点上的父指针。 自下而上的算法在时间和空间之间进行权衡：父指针允许在插入和删除后重新平衡时进行一些短路。

例如OpenJdk-7对红黑的实现树有父指针，这允许它选择删除后是否需要重新平衡（例如在您的场景中）。

自上而下是否比自下而上更有时间效率？

一般来说，是的：自上而下的方法每次操作只能遍历一次树，而底部方法每次操作必须遍历树两次。 正如我之前提到的，自下而上的方法可以通过使用父指针来节省一些时间。 但绝对不是每次都遍历整个树。

两种实现还可以选择利用线程来改善所需的时间或空间迭代整个树。 这需要每个节点一个或两个标志的开销。 这也可以使用父指针来实现，但效率不高。 注意：线程链接说线程不如父指针高效，但这仅适用于自下而上的树（本书介绍了这一点）。

轶事证据

回到大学时，我们实现了永远困惑的自上而下的红黑树在 C++ 中，并与我们的 STL（自下而上）std::map 实现进行了比较。 我们自上而下的方法肯定更快——我想说它在所有变异操作上都快了 2 倍。 搜索速度也更快，但我不能说这是由于更平衡的树还是更简单的代码。

可悲的是，我不再有代码，也不再有文章。