(a) オーダーが5のB木に100個のデータを登録した場合の、節点数の最小値と最大値を求める。 (b) オーダーが10のB木に100個のデータを登録した場合の、節点数の最小値と最大値を求める。

1. 問題の内容

(a) オーダーが5のB木に100個のデータを登録した場合の、節点数の最小値と最大値を求める。

(b) オーダーが10のB木に100個のデータを登録した場合の、節点数の最小値と最大値を求める。

2. 解き方の手順

(a) オーダー5のB木の場合

* 葉の数：100 (データ数と葉の数は同じ)

* 最小値の場合：各ノードができるだけ多くの子を持つようにする。

* 根は2つの子を持つ。

* 根以外の内部ノードは $\lceil m/2 \rceil = \lceil 5/2 \rceil = 3$ 個の子を持つ。

* 葉の直前の階層のノード数を $x$ とすると、 $3x \le 100$ より、$x \le 33.333...$ なので、$x = 34$。

* その上の階層のノード数を $y$ とすると、$3y \le 34$ より、$y \le 11.333...$ なので、$y = 12$。

* さらにその上の階層 (根) のノード数は1 ($z=1$)。 ($2z \le 12$)

* 節点数の合計：$100 + 34 + 12 + 1 = 147$

* 最大値の場合：各ノードができるだけ少なくの子を持つようにする。

* 根は5つの子を持つ。

* 根以外の内部ノードは $\lceil m/2 \rceil = \lceil 5/2 \rceil = 3$ 個の子を持つ。

* 根は2つの子を持つ。

* 根以外の内部ノードは $m=5$個の子を持つ。

* 葉の直前の階層のノード数を $x$ とすると、$2x \le 100$ より、$x \le 50$ なので、$x = 50$。

* その上の階層のノード数を $y$ とすると、$2y \le 50$ より、$y \le 25$ なので、$y = 25$。

* さらにその上の階層 (根) のノード数は1 ($z=1$)。 ($2 \times 1 \le 25$)

* 節点数の合計：$100 + 50 + 25 + 1 = 176$

(b) オーダー10のB木の場合

* 葉の数：100

* 最小値の場合：各ノードができるだけ多くの子を持つようにする。

* 根は2つの子を持つ。

* 根以外の内部ノードは $\lceil m/2 \rceil = \lceil 10/2 \rceil = 5$ 個の子を持つ。

* 葉の直前の階層のノード数を $x$ とすると、$5x \le 100$ より、$x \le 20$ なので、$x = 20$。

* その上の階層のノード数を $y$ とすると、$2y \le 20$ より、$y \le 10$ なので、$y = 10$。

* さらにその上の階層 (根) のノード数は1 ($z=1$)。 ($2 \times 1 \le 10$)

* 節点数の合計：$100 + 20 + 2 + 1 = 123$

* 最大値の場合：各ノードができるだけ少なくの子を持つようにする。

* 根は2つの子を持つ。

* 根以外の内部ノードは $m = 10$ 個の子を持つ。

* 葉の直前の階層のノード数を $x$ とすると、$2x \le 100$ より、$x \le 50$ なので、$x = 50$。

* その上の階層のノード数を $y$ とすると、$2y \le 50$ より、$y \le 25$ なので、$y = 25$。

* さらにその上の階層 (根) のノード数は1 ($z=1$)。 ($2 \times 1 \le 25$)

* 節点数の合計：$100 + 50 + 25 + 1 = 176$

3. 最終的な答え

(a) オーダー5のB木の場合：最小値 147, 最大値 176

(b) オーダー10のB木の場合：最小値 123, 最大値 176