In computer science, an (a,b) tree is a kind of balanced 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 ≤ a ≤ (b+1)/2. The root has, if it is not a leaf, between 2 and b children.
Let a, b be positive integers such that 2 ≤ a ≤ (b+1)/2. Then a rooted tree T is an (a,b)-tree when:
- Every inner node except the root has at least a and at most b children.
- The root has at most b children.
- All paths from the root to the leaves are of the same length.
Every internal node v of a (a,b)-tree T 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 .
![{displaystyle S_{v}[1dots rho _{v}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/940e5aaddc38a94cb4dfbc7717d73831ecc0292b)
![{displaystyle H_{v}[1dots rho _{v}-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/991ab321ee4d679a64de75c26e9bfa0d0008dea8)
![{displaystyle H_{v}[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19724308bb4f9c608be8ab9c29460bb789d4433b)
![{displaystyle S_{v}[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a51cbe22f47a52c0f164ddf8505f583be9ea4f1c)
This article incorporates public domain material from Paul E. Black. “(a,b)-tree”. Dictionary of Algorithms and Data Structures. NIST.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |