Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Implementing M-Way Search Trees

 

In order to illustrate the basic ideas, this section describes an implementation of M-way search trees in main memory. According to Definition gif, 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 gif 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.

   figure20249
Figure: Representing a node of an M-way search tree.




next up previous contents index

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