Question

Give an upper bound and a lower bound for the height of a B-tree of degree k with n leaves.

Short answer

Therefore, the upper bound and a lower bound for the height of B-tree of degree k with n leaves are\({\bf{lo}}{{\bf{g}}_{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil }}\left( {\frac{{\bf{n}}}{{\bf{2}}}} \right){\bf{ + 1}}\) and \({\bf{lo}}{{\bf{g}}_{\bf{k}}}{\bf{n}}\).

Step-by-step solution

General form

Definition of tree: A tree isa connected undirected graph with no simple circuits.

Definition of Circuit:It isa path that begins and ends in the same vertex.

B-tree of degree k(Definition): It is a rooted tree such that all its leaves are at the same level, its root has at least two and at most k children unless it is a leaf, and every internal vertex other than the root has at least \(\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil \), but no more than k, children. Computer files can be accessed efficiently when B-trees are used to represent them.

Definition of Upper bound of a set: An element in a poset greater than all other elements in the set.

Definition of Lower bound of a set: An element ina poset less than all other elements in the set.

Evaluation of the given statement

Given that, a B-tree of degree k with n leaves.

Lower bound for the number of leaves:

A B-tree of degree k has at most k children at every internal vertex.

At level 0, we only have the root.

At level 1, the tree then has at most k vertices, as the root can have at most k children.

At level 2, the tree has at most \({\bf{k}}*{\bf{k = }}{{\bf{k}}^{\bf{2}}}\) vertices.

At level 3, the tree has at most \({\bf{k}}*{{\bf{k}}^{\bf{2}}}{\bf{ = }}{{\bf{k}}^{\bf{3}}}\) vertices.

Since, a B-tree of degree k with height h has at most \({{\bf{k}}^{\bf{h}}}\) vertices. So, the number of leaves is \({\bf{n}} \le {{\bf{k}}^{\bf{h}}}\).

Let us take the logarithm with base k on both sides.

\({\bf{lo}}{{\bf{g}}_{\bf{k}}}{\bf{n}} \le {\bf{h}}\)

So, the lower boundary for the height is \({\bf{lo}}{{\bf{g}}_{\bf{k}}}{\bf{n}}\).

Upper bound for the number of leaves

A B-tree of degree k has at least \(\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil \) children at every internal vertex, except the root which has at least 2 children.

At level 0, we only have the root.

At level 1, the tree then has at least 2 vertices, as the root can have at least 2 children.

At level 2, the tree has at least \({\bf{2}}*\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil {\bf{ = 2}}\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil \) vertices.

At level 3, the tree has at least \({\bf{2}}\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil *\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil {\bf{ = 2}}{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil ^{\bf{2}}}\) vertices.

Since, a B-tree of degree k with height h has at most \({\bf{2}}{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil ^{{\bf{h - 1}}}}\) vertices. So, the number of leaves is \({\bf{n}} \ge {\bf{2}}{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil ^{{\bf{h - 1}}}}\).

Now divide 2 on both sides and take logarithm with base \(\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil \) on both sides.

\(\begin{array}{l}{\bf{lo}}{{\bf{g}}_{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil }}\left( {\frac{{\bf{n}}}{{\bf{2}}}} \right) \ge {\bf{h - 1}}\\{\bf{lo}}{{\bf{g}}_{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil }}\left( {\frac{{\bf{n}}}{{\bf{2}}}} \right){\bf{ + 1}} \le {\bf{h}}\end{array}\)

So, the upper boundary for the height is \({\bf{lo}}{{\bf{g}}_{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil }}\left( {\frac{{\bf{n}}}{{\bf{2}}}} \right){\bf{ + 1}}\).

Conclusion: The upper bound for the number of leaves is \({\bf{lo}}{{\bf{g}}_{\left\lceil {\frac{{\bf{k}}}{{\bf{2}}}} \right\rceil }}\left( {\frac{{\bf{n}}}{{\bf{2}}}} \right){\bf{ + 1}}\) and the lower bound for the number of leaves is \({\bf{lo}}{{\bf{g}}_{\bf{k}}}{\bf{n}}\).