5.3.2 2-3 Trees: Deletion

Delete (x)

1.

Locate the leaf L containing x and let v be the parent of L

2.

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.