(a,b)-tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 \le a \le (b+1)/2. The root has, if it is not a leaf, between 2 and b children.

Definition[edit]

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

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

See also[edit]

References[edit]