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