Glossary |
For the deletion examples we'll start very simply then get complicated very fast. One large example shows all the ways in which delete affects the tree.
Starting with a simple node, we delete E
.
Then we delete A
.
This leaves us with an empty node.
Now we start with a large example tree. We want to delete G
. It's
got children, so we find the successor J
, delete G
and put
J
in its place. If the key doesn't have any children, this this stage
can be skipped.
Now we have transformed the problem into a leaf being deleted. Unfortunately
this leaves us with a deficient node !
. Our siblings don't have any
keys we can steal to make up our numbers, so to fix this, we will have to
combine with a sibling.
We have demoted K
and adopted O
from our right-hand sibling.
Unfortunately that leaves us with a deficient node !
, so we work on
that node next. This time we have a sibling with a key we can steal. To keep
the tree in order, we will promote E
and demote J
.
If you look closely, you will see that one of the nodes (containing F
)
has swapped sides of the tree. Because the pointers on-disk only point
downwards, the the F
node isn't changed.
Once a steal has occurred, the operation is complete.