In red-black trees is top-down deletion faster and more space efficient than bottom-up deletion?

Question

Per this page http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx "Top-down deletion" is an implementation of a red-black tree node removal that pro-actively balances a tree by pushing a red node down through the tree so that the leaf node which is being removed is guaranteed to be red. Since the leaf node is guaranteed to be red, you don't have to worry about re-balancing the tree, because deleting a red leaf node doesn't violate any rules and you don't have to perform any additional operations to re-balance and restore red-black'ness.

"Bottom-up deletion" involves doing a normal binary search down the tree to find the node to be deleted, swapping in the leaf node ( if the found node isn't a leaf node), and then restoring the red-black tree properties by climbing back up the tree while fixing red-black rule violations.

Does top-down deletion minimize the number of re-balancing operations? Could it be possible that top-down deletion pro-actively does too many re-colorings and re-balancings on the way down?

What about this scenario: (x) denotes a red node

               8
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

If I want to delete 16, a bottom-up deletion wouldn't do any rebalancing, but a top-down deletion re-colors the nodes all the way down, before discovering that the recoloring operations were unnecessary:

iteration 1:

              (8)
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

iteration 2:

               8
         _____/ \____
        /            \
      (4)            (12)
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

iteration 3:

               8
         _____/ \____
        /            \
      (4)             12
     /   \          /    \
   2       6     (10)    (14)
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

Then in iteration 4 you discover that you don't need to push down because 16 is already red. So is top-down deletion more time and space efficient?

Answer 1

From what I gather: "top-down deletion" avoids traversing the same node in a path more than once during the operation. So, given the simple path from the root to a given node, if you're going to do some thing to a node that's in that path anyway, why not just do it on the way down? It avoids having to traverse over parts of the path more than once. Therefore, this saves time.

A similar principle is employed for multiple operations (including insert) in 2-3-4 trees (a special sub-case of a,b-trees)

Does top-down deletion minimize the number of re-balancing operations?

Think that, in the average case, it does. Because you make it potentially easier to insert something afterward with few re-balancing operations.

Could it be possible that top-down deletion pro-actively does too many re-colorings and re-balancings on the way down?

Maybe, but that depends on the data set. However, as mentioned above. This may reduce the number of re-colorings and re-balancings overall.