**For an example, see Figure 5.24.
**

**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*_{1}and*k*_{2}at node*v*to reflect the new situation

- make
- 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.

- split