Characteristics of M-way Search Tree

M-way Search Tree

If we relax the restriction that each node can have only one key, we can reduce the height of the tree. An M-way search tree means a search tree with degree M. An M-way search tree T may be an empty tree. If T is a non-empty tree, then it satisfies the following properties:

1. Every node of T has at least one key value and at most M-1 key values.
2. If in a node there are n keys k₀, k₁,…..k_n-1 then k₀ < k₁ <…….< k_n-1
3. All keys in the left sub-tree of a key are less than it and all keys in the right sub-tree of a key are greater than it.
4. Each of the sub-trees of a node is also an M-way search tree.