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.
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 .
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|