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!
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.)