(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.


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

Internal node representation[]

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

See also[]