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

按此页面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已经是红色.那么自上而下的删除更有时间和空间效率吗？