We’re rewarding the question askers & reputations are being recalculated! Read more.

Hot answers tagged


Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children. If we imagine to construct a minimun nodes b-tree, we'll have: $n = 1 + 2 + 2\lceil m/2\rceil + 2\lceil m/2\rceil^2 + ... + 2\lceil m/2\rceil^{h-2}$where every addend is the number of nodes ...


Augment each node to contain the key of the node with maximum value, among all nodes that are underneath it (among all of its descendants). You can easily maintain/update this augmented information each time you modify the tree, by using the fact that the maximum for any node can be recomputed using just the information in its direct children (you don't ...

Only top voted, non community-wiki answers of a minimum length are eligible