M-way Search Trees

Binary search tree: 1 value and 2 subtrees per node.

M-way search tree: M - 1 values and M subtrees per node. M is the degree of the tree.

In fact, each may contain up to M - 1 values. A node with k values must have k + 1 subtrees.

In a node, values are stored in ascending order:

V1 < V2 < ... < Vk

The subtrees are placed between adjacent values: each value has a left and right subtree.

V(i)'s right subtree = V(i+1)'s left subtree.

All the values in V(i)'s left subtree are < V(i).

All the values in V(i)'s right subtree are > V(i).