(a,b)-tree

From Wikipedia, the free encyclopedia

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.

[edit] 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.

[edit] Inner node representation

Every inner node has the following representation:

Let $ρ v$ be a number of nodes.
Let $S_v[1 \dots \rho_v]$ be pointers to nodes.
Let $H_v[1 \dots \rho_v - 1]$ be an array of nodes with maximal value in the subtree $S v [i]$ .