data-structures - 在红黑树中，自顶向下删除比自底向上删除更快，空间效率更高？

Question

每本页 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 已经是红色的。那么自上而下的删除是否更节省时间和空间？

Answer 1

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

在 2-3-4 树(a,b-trees 的特殊子情况)中的多个操作(包括插入)采用了类似的原理

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

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

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

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