Proper way to Re-Balance a 2-3 Tree after deleting the root node

Question

The goal is to remove 22 from the root node and re-balance the tree.

First I remove 22, and replace it by its in-order successor 28.

Secondly I rebalance the resulting tree, by moving the empty node to the left. The resulting tree is below.

Is moving 28 up the right procedure, and did I balance the left side correctly in the end?

         22,34
     /     |    \
   16      28    37
   / \    / \    / \
 15   21 25  33 35 43  

        [28],34
     /     |    \
   16      *     37
   / \    / \    / \
 15   21 25  33 35 43 

           34
        /       \
      16,28      37
    /   |   \    / \
  15  21,25  33 35 43

Thanks!

The balance of a 2-3 tree is that all sub trees are the same height. It seems to me that this is the case here. — selalerer, Feb 28 '16 at 14:26
Yes right, that's a mistake. So now I'll only have to combine (28,33) in the middle node, but then they're not on the same height anymore. How would the rebalanced left and right sub-tree look like? — daniel haimanot, Feb 28 '16 at 18:23

score 2 · Accepted Answer · answered Feb 28 '16 at 19:10

To delete 22 from

       22,34
   /     |     \
  16     28     37
 / \    / \    / \
15  21 25  33 35  43 ,

we replace it by its in-order successor 25, leaving a hole (*).

       25,34
   /     |     \
  16     28     37
 / \    / \    / \
15  21 *   33 35  43

We can't fix the hole by borrowing, so we merge its parent into its sibling, moving the hole up.

       25,34
   /     |     \
  16     *      37
 / \     |     / \
15  21 28,33  35  43

The hole has two siblings now, so we can redistribute one of the parent's keys down.

         34
     /        \
  16,25        37
 /  |   \     / \
15  21 28,33 35  43

(I'm working from this set of lecture notes. Don't bother memorizing the details here unless it's for an exam. Even then... I really wish data structure courses did not emphasize balanced search trees to the degree that they do.)

Gotta agree with the emphasis on search trees comment, but that's truly where I learned how to debug code and recursion, two very important skills — OneCricketeer, Feb 28 '16 at 19:19

Proper way to Re-Balance a 2-3 Tree after deleting the root node

1 Answers1