In the data structure known as a B-tree of order 5, each node of the tree can contain

Chapter 6, Problem 54

(choose chapter or problem)

In the data structure known as a B-tree of order 5, each node of the tree can contain multiple data values, maintained in sorted order. Between and around the data values at an internal node are arcs that lead to children of the node. New data values are inserted into the leaf nodes of the tree, but when a leaf (or internal node) gets up to five values, it splits in two and the median value pops up to the next level of the tree. The figure shows the tree at various points as the data values 1 through 8 are inserted into an initially empty tree. Section 6.2 Trees and Their Representations 527 a. The minimum number of data values to insert into a B-tree of order 5 to force it to have two levels is 5. Find the minimum number of data values required to force the tree to have three levels. b. Prove that when a B-tree of order 5 has the minimum number of data values to force it to have n levels, n 2, the bottom level contains 2(3n2 ) nodes. c. Find (and justify) a general expression for the minimum number of data values required to force a B-tree of order 5 to have n levels. aHint: 30 + 31 + c+ 3n2 = a 3n 3 6 b.b