In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, an (a,b) tree is a kind of balanced
search tree
In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less ...
.
An (a,b)-tree has all of its
leaves
A leaf (plural, : leaves) is any of the principal appendages of a vascular plant plant stem, stem, usually borne laterally aboveground and specialized for photosynthesis. Leaves are collectively called foliage, as in "autumn foliage", wh ...
at the same depth, and all internal
nodes
In general, a node is a localized swelling (a "knot") or a point of intersection (a Vertex (graph theory), vertex).
Node may refer to:
In mathematics
*Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two ...
except for the root have between and
children
A child ( : children) is a human being between the stages of birth and puberty, or between the developmental period of infancy and puberty. The legal definition of ''child'' generally refers to a minor, otherwise known as a person younger ...
, where and are integers such that . The root has, if it is not a leaf, between 2 and children.
Definition
Let , be positive integers such that . Then a
rooted tree
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''a ...
is an (a,b)-tree when:
* Every inner node except the root has at least and at most children.
* The root has at most children.
* All paths from the root to the leaves are of the same length.
Internal node representation
Every internal node of a (a,b)-tree has the following representation:
* Let
be the number of child nodes of node .
* Let