next up previous
Next: 5.4 B-Trees Up: 5.3 2-3 Trees Previous: 5.3.1 2-3 Trees: Insertion

5.3.2 2-3 Trees: Deletion

Delete (x)

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.
Example: See Figure 5.25.