演習問題 第5回 B木(2017、2019年度)

■ 実験用データ
　整数集合:　　集合の濃度(要素数): 1,000,000、　キーの型: 整数、　　 ファイル: integer1MR.dat
　文字列集合: 集合の濃度(要素数): 100,000、　　キーの型: 文字列、　ファイル: wordE100KR.dat
　　　(文字列集合: 英単語集合)

■ 計測値出力単位
整数集合　　　U = 100,000　　(要素数の1/10)
英単語集合　 U = 10,000　　　(要素数の1/10)

■ 集合、パラメーター設定
・学籍番号の最下位桁の値によって、演習問題に対するパラメーター(KKの値)が異なります)
　　　前半のグループ　　　後半のグループ
　　　集合: 文字列集合　　集合: 整数集合
番号　　 KKの値　　　　　　　KKの値
　　0: 　　4,　8,　12　　　　　　　24, 32, 48
　　1: 　　8,　12,　16　　　　　　32, 48, 64
　　2: 　 12,　16,　24　　　　　　48, 64, 96
　　3: 　 16,　24,　32　　　　　　64, 96, 128
　　4: 　 24,　32,　48　　　　　　 96, 128, 192
　　5: 　 32,　48,　64　　　　　　 128, 192, 256
　　6: 　 48,　64,　96　　　　　　192, 256, 384
　　7: 　 64,　96,　128　　　　　 256, 384, 512
　　8: 　 96,　128,　192　　　　　384, 512, 768
　　9: 　128,　192,　256　　　　　512, 768, 1024

■ 留意事項
・誤った集合、誤った設定値でのレポートは受理されません。



5a B木の記憶効率
　 指定されたファイルを読込み、B木を生成する(追加関数)。次数Kを上記のように設定する。1U, 2U, ・・・・・、9U、10Uレコード読み込んだときの各時点で、次の項目を測定する。
　　高さ、ノード数、最大要素数、構築時間
ここで、最大要素数とは格納可能最大要素数であり、ノード数×KK　の値である。B木の木の高さの算出方法は、第4回の演習問題のプログラムコードと同様である。 上記の項目を指定された次数kについて計測し、以下のような書式で出力する。

KK = **のとき
要素数　　高さ　ノード数　最大要素数　構築時間(msec.)
----------------------------------------------------------
1U　　　　・　　　　　・　　　　　　　・　　　　　・　　　　・
2U　　　　・　　　　　・　　　　　　　・　　　　　・　　　　・
　　　　　　・　　　　　・　　　　　　　・　　　　　・　　　　・
　　　　　　・　　　　　・　　　　　　　・　　　　　・　　　　・
9U　　　　・　　　　　・　　　　　　　・　　　　　・　　　　・
10U　　　　・　　　　　・　　　　　　　・　　　　　・　　　　・

　提出プログラムのメイン関数は、特定のKだけについてB木を生成し、上記書式で出力する仕様とし、その時のKKの値は3つのうちの最大の値とする(1つのメイン関数の中で、3つの異なったKについてB木を連続して生成する必要は無い)。言い換えれば、3つの異なったKについて、3回コンパイル−実行し、レポートには、3種類のKKについて上記書式の出力結果が記載されるものとする。
　記憶効率の観点から、本課題の結果と演習課題4aの結果と対比し、様々な観点から分析せよ。上記以外の項目も測定することが期待される。


5b 巡回関数(横型巡回)の作成(選択課題)
　上記の整数集合ファイルを読み込み、B木を構築する(追加関数)。このとき、B木において、次数 K = 4とする(KK = 8)。次の巡回関数を作成する。
　　　　 void　Out_Tree_H(NODE *)　:　横型巡回(最左端→最右端)
構築したB木に対しこの関数を適用し、根を含む24個の節について、節内の要素を出力する。出力する際に、節内の要素の開始と終了を示すために次のprintf文を含むものとする。
　　　節内の要素の開始: printf("< ")
　　　節内の要素の終了: printf("> \t")
また、各レベルの最右端の節内の要素が出力された後、次のレベルの節を出力する前に改行(リターン)されるものとする。
　レポートの内容としては、作成した関数のアルゴリズムおよびプログラムコードについての明確かつ詳細な説明を含むものとする。