|Data Structures and
|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, kj, and
a set of sub-trees,
Ti, (i = 0..j), such that
- if k is a key in T0, then k <=
- if k is a key in Ti
(0<i<j), then ki <= k
- if k is a key in Tj, then k >
- all Ti are nonempty m-way search trees or all
Ti are empty
|Or in plain English ..
- A node generally has m-1 keys and m
Each node has alternating sub-tree pointers and
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
- 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
A B-tree of order m is an m-way tree in which
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.
- 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.
- n-ary trees (or n-way trees)
- Trees in which each node may have up to n children.
- Balanced variant of an n-way tree.
- B-tree in which all the leaves are linked to facilitate fast in order
© John Morris, 1998