Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
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.