[30, 80]
/ | \
/ | \
/ | \
[20] [50, 60] [90]
/ \ / | \ / \
[10] [25] [35, 40] [55] [70] [82, 85] [95]
When 55 is removed, we borrow from the left sibling
and get the following tree.
[30, 80]
/ | \
/ | \
/ | \
[20] [40, 60] [90]
/ \ / | \ / \
[10] [25] [35] [50] [70] [82, 85] [95]
To remove the 40 we first replace it by
35 and then resolve the deficiency in the former
node for 35 by combining with its right sibling.
The result is shown below.
[30, 80]
/ | \
/ | \
/ | \
[20] [60] [90]
/ \ / \ / \
[10] [25] [35, 50] [70] [82, 85] [95]
To remove the 70, we borrow from the left sibling.
The result is shown below.
[30, 80]
/ | \
/ | \
/ | \
[20] [50] [90]
/ \ / \ / \
[10] [25] [35] [60] [82, 85] [95]
The removal of 35, requires two combining steps.
The result is shown below.
[80]
/ \
/ \
/ \
[20, 30] [90]
/ | \ / \
[10] [25] [50, 60] [82, 85] [95]
Removing 60 is easy.
The result is shown below.
[80]
/ \
/ \
/ \
[20, 30] [90]
/ | \ / \
[10] [25] [50] [82, 85] [95]
When 95 is removed, we borrow from a left
sibling.
The result is shown below.
[80]
/ \
/ \
/ \
[20, 30] [85]
/ | \ / \
[10] [25] [50] [82] [90]
When 90 is removed, we do a node combining
followed by a borrow from a sibling.
The result is shown below.
[30]
/ \
/ \
/ \
[20] [80]
/ \ / \
[10] [25] [50] [82, 85]
Removing 82 is easy.
The result is shown below.
[30]
/ \
/ \
/ \
[20] [80]
/ \ / \
[10] [25] [50] [82]
To remove 80 we first replace it by
50 to get the tree
[30]
/ \
/ \
/ \
[20] [50]
/ \ / \
[10] [25] [ ] [82]
Next we combine two siblings to get the tree
[30]
/ \
/ \
/ \
[20] [ ]
/ \ /
[10] [25] [50, 82]
We again combine two siblings to get the tree
[ ]
/
/
/
[20, 30]
/ | \
[10] [25] [50, 82]
Finally, the root is discarded to get the following tree.
[20, 30]
/ | \
[10] [25] [50, 82]