(a,b)-tree

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 a and b children, where a and b are integers such that 2 ≤ a ≤ (b+1)/2. The root has, if it is not a leaf, between 2 and b children.

Definition

Let a, b be positive integers such that 2 ≤ a ≤ (b+1)/2. Then a rooted tree T is an (a,b)-tree when:

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

Internal node representation

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

• Let [math]\displaystyle{ \rho_v }[/math] be the number of child nodes of node v.
• Let [math]\displaystyle{ S_v[1 \dots \rho_v] }[/math] be pointers to child nodes.
• Let [math]\displaystyle{ H_v[1 \dots \rho_v - 1] }[/math] be an array of keys such that [math]\displaystyle{ H_v[i] }[/math] equals the largest key in the subtree pointed to by [math]\displaystyle{ S_v[i] }[/math].

See also

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

References

•  This article incorporates public domain material from the NIST document: Black, Paul E.. "(a,b)-tree". https://xlinux.nist.gov/dads/HTML/abtree.html.