在红黑树中,自上而下删除比自下而上删除更快,更节省空间吗？

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 树的特殊子情况）中的多个操作（包括插入）

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

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

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

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