演習問題 第4回 多分探索木(2014、2016年度)

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

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

■ 集合、パラメーター設定
・学籍番号の最下位桁の値によって、演習問題に対する集合、パラメーター(対象集合、等)が異なります)

   前半グループ:   後半グループ:
    文字列集合    整数集合
番号  KKの値      KKの値
  0:     4         12
  1:     8         16
  2:    12         20
  3:    16         24
  4:    20         28
  5:    24         32
  6:    28         36
  7:    32         40
  8:    36         44
  9:    40         48

■ 留意事項
・誤った問題番号、誤った設定値でレポートを提出、また複数の問題に対してレポート提出は受理されません。



4a 多分探索木と二分探索木の比較
指定されたファイルを読み込み、指定された次数Kで多分探索木を生成する(追加関数)。このとき、U要素単位で、以下の項目を計測する。
  (a)木の高さ、 (b)節(ノード)数、 (c)格納可能要素数、(d)構築時間
     格納可能要素数(c): KK × 節数
 出力書式のイメージは以下のとおり。

     多分探索木(KK = **)
格納要素数  高さ 節数  格納可能要素数 構築時間(秒)
    1U  ***  ***  ******      **.**
    2U  ***  ***  ******      **.**
          ・ ・ ・ ・
          ・ ・ ・ ・
    9U  ***  ***  ******      **.**
   10U  ***  ***  ******      **.**

    多分木の高さ計測については、二分木の高さ計測用プログラムコードが参考なる。
 次に、同一のファイル(集合)について、二分探索木を生成する(追加関数)。このとき、U要素単位で、以下の項目を計測する。
  (a)木の高さ、 (b)節(ノード)数、 (d)構築時間
 出力書式のイメージは以下のとおり。

     二分探索木
格納要素数  高さ 節数  構築時間(秒)
    1U  ***  ***  **.**
    2U  ***  ***  **.**
          ・ ・ ・ ・
          ・ ・ ・ ・
    9U  ***  ***  **.**
   10U  ***  ***  **.**

 上記の2種類の木構造に関する、計測結果を比較し、様々な観点から分析せよ。なお、提出exeファイルは、多分探索木main関数のexeファイルだけでよい。



4b 巡回関数の作成【選択問題】
指定されたファイルを読み込み、多分探索木を構築する(追加関数)。このとき、多分探索木において、次数 K = 16(KK = 32)とする(学籍番号の末尾の数字にかかわらない) 。
 次の巡回関数を作成する。
     全節のキーの昇順出力
上述した多分探索木に対しこの関数を適用し、先頭から200個の要素を出力する。出力する際に、1つの節の内の要素を出力後に空白行を出力する。レポートの内容としては、作成した関数のアルゴリズムおよびプログラムコードについての明確かつ詳細な説明を含むものとする。



・4bは選択問題です。



演習問題プログラム作成における注意事項

下記の要件を必ず満たすようにプログラムを作成せよ。

 (1) 最初に読み込むファイル名は絶対パスとしてmainプログラム中で記述し、コマンドライン上の引数による指定、およびリダイレクトによる入力指定はしないこと。

   例. char infile[80] = "/home/algorithm_data/texte.dat" ;

 (2) 比較回数、実行時間等、測定結果をプログラムの最後に出力する。