Notes
Suppose L is the least number of children a node is allowed to have, while U is the most number. Then each node will always have between L and U children, inclusively, with one exception: the root node may have anywhere from 2 to U children inclusively, or in other words, it is exempt from the lower bound restriction, instead having a lower bound of its own (2). This allows the tree to hold small numbers of elements. The root having one child makes no sense, since the subtree attached to that child could simply be attached to the root. Giving the root no children is also unnecessary, since a tree with no elements is typically represented as having no root node.
Robert Tarjan proved that the amortized number of splits/merges is 2.
References
Original papers:
- Rudolf Bayer, Binary B-Trees for Virtual Memory, ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219-235.
- Rudolf Bayer and McCreight, E. M Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1, 173-189, 1972.
Summary:
- Donald E. Knuth, "The Art of Computer Programming", second edition, volume 3, section 6.2.4, 1997.
External links
Source | Copyright