Data Structures and Algorithms: n-ary trees

Data Structures and Algorithms

8.2 General n-ary trees

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

is empty or
consists of a root containing j (1<=j<m) keys, k_j, and
a set of sub-trees, T_i, (i = 0..j), such that

if k is a key in T₀, then k <= k₁
if k is a key in T_i (0<i<j), then k_i <= k <= k_i+1
if k is a key in T_j, then k > k_j and
all T_i are nonempty m-way search trees or all T_i are empty

Or in plain English ..

A node generally has m-1 keys and m children.
Each node has alternating sub-tree pointers and keys:
sub-tree | key | sub-tree | key | ... | key | sub_tree

All keys in a sub-tree to the left of a key are smaller than it.
All keys in the node between two keys are between those two keys.
All keys in a sub-tree to the right of a key are greater than it.
This is the "standard" recursive part of the definition.

The height of a complete m-ary tree with n nodes is ceiling(log_mn).

A B-tree of order m is an m-way tree in which

all leaves are on the same level and
all nodes except for the root and the leaves have at least m/2 children and at most m children. The root has at least 2 children and at most m children.

A variation of the B-tree, known as a B+-tree considers all the keys in nodes except the leaves as dummies. All keys are duplicated in the leaves. This has the advantage that is all the leaves are linked together sequentially, the entire tree may be scanned without visiting the higher nodes at all.

Key terms

n-ary trees (or n-way trees): Trees in which each node may have up to n children.
B-tree: Balanced variant of an n-way tree.
B+-tree: B-tree in which all the leaves are linked to facilitate fast in order traversal.