|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
In order to illustrate the basic ideas,
this section describes an implementation
of M-way search trees in main memory.
According to Definition 
,
each internal node of an M-way search tree has n subtrees,
where n is at least two and at most M.
Furthermore, if a node has n subtrees,
it must contain n-1 keys.
Figure shows how we can implement
a single node of an M-way search tree.
The idea is that we use two arrays in each node--the first holds the keys
and the second contains pointers to the subtrees.
Since there are at most M subtrees but only M-1 keys,
the first element of the array of keys is not used.
Figure: Representing a node of an M-way search tree.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.