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

Definition

Let $a,\; b\; in\; N$ such that $a\; leq\; b$. Then tree T is (a,b) tree when:
* Every inner node except the root has at least $a$ and maximally $b$ nodes.
* Root has maximally $b$ nodes.
* All paths from the root to the leaves are of the same length.

Inner node representation

Every inner node has the following representation:
* Let $ho\_v$ be a number of nodes.
* Let $S\_v\; [1\; dots\; ho\_v]$ be pointers to nodes.
* Let $H\_v\; [1\; dots\; ho\_v\; -\; 1]$ be an array of nodes with maximal value in the subtree $S\_v\; [i]$.

ee also

B-tree