# (a,b)-tree

Jump to navigation
Jump to 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 and children, where and are integers such that . The root has, if it is not a leaf, between 2 and b children.

## Definition

Let such that . Then a tree *T* is an **(a,b) tree** when:

- Every inner node except the root has at least and maximally child nodes.
- Root has maximally child 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 be the number of child nodes of node v.
- Let be pointers to child nodes.
- Let be an array of keys such that equals the largest key in the subtree pointed to by .

## See also

## References

- Paul E. Black, (a,b)-tree at the NIST Dictionary of Algorithms and Data Structures.