15

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

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

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

这个场景怎么样：（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 已经是红色的。那么自上而下的删除是否更节省时间和空间？

4

2 回答 2

4

据我所知：“自上而下的删除”避免了在操作过程中多次遍历路径中的同一节点。所以，给定从根到给定节点的简单路径，如果无论如何你要对该路径中的节点做一些事情，为什么不直接在向下的路上做呢？它避免了多次遍历路径的某些部分。因此，这可以节省时间。

2-3-4 树（a,b-trees 的特殊子情况）中的多个操作（包括插入）采用类似的原则

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

想想，在一般情况下，确实如此。因为您可以通过很少的重新平衡操作使之后插入一些东西变得更容易。

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

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

于 2008-12-13T20:01:19.407 回答
3

自上而下是否比自下而上更节省空间？

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

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

自上而下是否比自下而上更节省时间？

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

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

传闻

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

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

于 2011-11-05T23:41:06.433 回答