The routine for inserting items in an *M*-way search tree
follows directly from the algorithm for insertion in a binary search tree given
in Section .
The added wrinkle in an *M*-way tree is that an internal node
may contain between 1 and *M*-1 keys
whereas an internal node in a binary tree must contain exactly one key.

Program gives the implementation
of the `Insert` member function of the `MWayTree` class.
This function takes as its lone argument a reference to the `Object`
instance to be inserted into the search tree.

**Program:** `MWayTree` Class `Insert` Member Function Definition

The general procedure for insertion is to search for the item
to be inserted and then to insert it at the point where the search terminates.
If the search terminates at an external node,
that node is transformed to an internal node of the form
,
where *x* is the key just inserted (lines 5-8).

If the search terminates at an internal node,
we insert the new item into the sorted list of keys at the appropriate offset.
Inserting the key *x* in the array of keys moves all the keys larger than *x*
and the associated subtrees to the right one position (lines 17-22).
The hole in the list of subtrees is filled with an empty tree (line 23).

The preceding section gives the running time for a search
in an *M*-way search tree as

where *h* is the height of the tree.
The additional time required to insert the item into the node
once the correct node has been located is *O*(*M*).
Therefore, the total running time for the
`Insert` algorithm given in Program is

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.