Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

M-Way Search Trees

 

Definition (M-way Search Tree)  An M-way search tree    T is a finite set of keys. Either the set is empty, tex2html_wrap_inline63628; or the set consists of n M-way subtrees tex2html_wrap_inline63638, tex2html_wrap_inline63404, ..., tex2html_wrap_inline64388, and n-1 keys, tex2html_wrap_inline64392, tex2html_wrap_inline64394, ..., tex2html_wrap_inline64396,

displaymath64364

where tex2html_wrap_inline64398, such that the keys and nodes satisfy the following data ordering properties :

  1. The keys in each node are distinct and ordered, i.e., tex2html_wrap_inline64400 for tex2html_wrap_inline64402.
  2. All the keys contained in subtree tex2html_wrap_inline64404 are less than tex2html_wrap_inline64406, i.e., tex2html_wrap_inline64408 for tex2html_wrap_inline64402. The tree tex2html_wrap_inline64404 is called the left subtree  with respect to the key tex2html_wrap_inline64406.
  3. All the keys contained in subtree tex2html_wrap_inline63460 are greater than tex2html_wrap_inline64406, i.e., tex2html_wrap_inline64420 for tex2html_wrap_inline64402. The tree tex2html_wrap_inline64424 is called the right subtree with respect to the key tex2html_wrap_inline64406.

Figure gif gives an example of an M-way search tree for M=4. In this case, each of the non-empty nodes of the tree has between one and three keys and at most four subtrees. All the keys in the tree satisfy the data ordering properties. Specifically, the keys in each node are ordered and for each key in the tree, all the keys in the left subtree with respect to the given key are are less than the given key, and all the keys in the right subtree with respect to the given key are larger than than the given key. Finally, it is important to note that the topology of the tree is not determined by the particular set of keys it contains.

   figure18704
Figure: An M-way Search Tree


next up previous contents index

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