(a,b)-tree explained

In computer science, an (a,b) tree is a kind of balanced search tree.

An (a,b)-tree has all of its leaves at the same depth, and all internal nodes except for the root have between and children, where and are integers such that . The root has, if it is not a leaf, between 2 and children.

Definition

Let, be positive integers such that . Then a rooted tree is an (a,b)-tree when:

• Every inner node except the root has at least and at most children.
• The root has at most children.
• All paths from the root to the leaves are of the same length.

Internal node representation

Every internal node of a (a,b)-tree has the following representation:

• Let

\rho _{v} be the number of child nodes of node .

• Let

S _{v[1} ... \rho _{v]} be pointers to child nodes.

• Let

H _{v[1} ... \rho _{v} - 1 ] be an array of keys such that H _{v[i]} equals the largest key in the subtree pointed to by S _{v[i]} .

See also

• B-tree
• 2–3 tree
• 2–3–4 tree