5.3.1 2-3 Trees: Insertion

For an example, see Figure 5.24.

  

Figure 5.24: Insertion in 2-3 trees: An example

  

Figure 5.25: Deletion in 2-3 trees: An Example

Insert (x)

1.

Locate the node v, which should be the parent of x

2.

If v has two children,

• make x another child of v and place it in the proper order
• adjust k₁ and k₂ at node v to reflect the new situation

3.

If v has three children,

• split v into two nodes v and v'. Make the two smallest among four children stay with v and assign the other two as children of v'.
• Recursively insert v' among the children of w where
  w = parent of  v

• The recursive insertion can proceed all the way up to the root, making it necessary to split the root. In this case, create a new root, thus increasing the number of levels by 1.