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

Definition

Let $a,b\in \mathbb {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]$ .