(a,b)-tree

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

An (a,b) tree has all of its leaves at the same depth, and all internal nodes have between $a$ and $b$ children, where $a$ and $b$ are integers such that $2 \le a \le (b+1)/2$. The root may have as few as zero children.

Definition

Let $a, b \in N$ such that $a \leq b$. Then a tree T is an (a,b) tree when:

• Every inner node except the root has at least $a$ and maximally $b$ child nodes.
• Root has maximally $b$ child nodes.
• All paths from the root to the leaves are of the same length.

Inner node representation

Every inner node $v$ has the following representation:

• Let $\rho_v$ be the number of child nodes of node v.
• Let $S_v[1 \dots \rho_v]$ be pointers to child nodes.
• Let $H_v[1 \dots \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

References

• Paul E. Black, (a,b)-tree at the NIST Dictionary of Algorithms and Data Structures.