在红黑树中，自顶向下的删除操作比自底向上的删除操作更快且空间利用率更高吗？

Question

根据此页面 http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx，“自顶向下删除(Top-down deletion)”是红黑树节点删除的一种实现，通过将红色节点沿着树向下推送，使得要删除的叶子节点保证为红色，从而主动平衡树。由于保证要删除的叶子节点为红色，因此不需要担心再次平衡树，因为删除红色叶子节点不违反任何规则，也不需要执行任何额外的操作来重新平衡和恢复红黑'ness。

“自底向上删除(Bottom-up deletion)”涉及在树中进行正常的二进制搜索以找到要删除的节点，在交换叶子节点（如果找到的节点不是叶子节点）后，通过向上爬树并修复红黑规则违规来恢复红黑树属性。

自顶向下的删除是否最小化了重新平衡操作的数量？自顶向下的删除是否可能在向下过程中主动进行了过多的重新着色和重新平衡操作？

那么这种情况呢：(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)

然后在第四次迭代中，您发现不需要向下推，因为16已经是红色的。所以自顶向下的删除更节省时间和空间吗？

- funkyworklehead

Answer 1

据我所知，“自顶向下删除”在操作过程中避免了在路径上多次遍历同一节点。因此，如果你要对路径上的某个节点进行操作，为什么不在下降的过程中直接进行呢？这样可以避免重复遍历路径的部分内容，从而节省时间。

2-3-4树（a,b树的特殊子情形）也采用了类似的原则来进行多个操作（包括插入）。

自顶向下删除是否最小化了重新平衡操作的数量？

在平均情况下，它可能会。因为这样有可能使得之后插入操作需要的重新平衡操作更少。

自顶向下删除是否会在下降的过程中主动进行过多的重新着色和重新平衡操作？

可能会，但这取决于数据集。然而，正如上面所提到的，这可能会减少总体上的重新着色和重新平衡操作的数量。

- mepcotterell

---

你可以看一下我的RedBlackTree中的remove方法吗？http://stackoverflow.com/questions/28705454/how-to-fix-remove-in-redblacktree-implementation - committedandroider

Answer 2

自上而下的算法比自下而上的算法更节省空间吗？

简而言之，是的。在eternally confuzzled网站介绍的自上而下的算法不需要节点上的父指针。而自下而上的算法需要在插入和删除后重新平衡树时进行时间和空间的权衡：父指针允许一些短路操作。

例如，OpenJdk-7实现了红黑树，并使用了父指针，这使得它可以选择是否需要在删除后重新平衡树（如您的情况）。

自上而下的算法比自下而上的算法更节省时间吗？

总体上，是的：每次操作自上而下的算法只需遍历树一次，而自下而上的算法则需要遍历树两次。正如我之前提到的，自下而上的方法可以通过使用父指针来缩短一些时间。但肯定不是每次都需要遍历整棵树。

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

经验性证据

在大学时，我们使用C++实现了eternally confuzzled网站的自上而下红黑树，并与我们STL的（自下而上）std::map实现进行了比较。我们的自上而下方法明显更快 - 我想说，在所有变异操作中，它至少快了2倍。搜索也更快，但我不能确定是由于更平衡的树还是更简单的代码。

可悲的是，我已经没有那段代码或写作了。

- Michael Deardeuff

---

感谢您回答我的悬赏问题以引起更多关注！Eternally confuzzled的“自底向上”的插入和删除算法也不需要父指针，因为它们在向下递归时存储在堆栈上。当然，即使节点没有父级，使用堆栈也会占用不同的空间。 - u0b34a0f6ae

这也有相反的证据。例如：http://gedare-csphd.blogspot.cz/2011/08/red-black-trees-bottom-up-or-top-down.html 他声称发现自下而上的方法更快。 - mnicky

好的，这让我相信我的实现比std::map更快，因为代码要简单得多。 - Michael Deardeuff

你们能否看一下我在RedBlackTree中的remove方法？http://stackoverflow.com/questions/28705454/how-to-fix-remove-in-redblacktree-implementation - committedandroider