Next: 5.4 B-Trees
Up: 5.3 2-3 Trees
Previous: 5.3.1 2-3 Trees: Insertion
Example: See Figure 5.25.
- Locate the leaf L containing x and let v be the parent of L
- Delete L. This may leave v with only one child. If v is the root,
delete v and let its lone child become the new root. This reduces the number
of levels by 1. If v is not the root, let
- p = parent of v
- If p has a child with 3 children, transfer an appropriate one to vif this child is adjacent (sibling) to v.
- If children of p adjacent
to v have only two children, transfer the
lone child of v to an adjacent sibling of v and delete v.
- If p now has only one child, repeat recursively with p in
place of v. The recursion can ripple all the way up to the root, leading to a
decrease in the number of levels.