演習問題 第3回 AVL木(2014、2016度)


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

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

■ 集合、パラメーター設定
・学籍番号の最下位桁の値によって、集合、パラメーター(探索値集合の開始番号)が異なります。
    前半のグループ    後半のグループ
    集合: 整数集合    集合: 文字列集合
番号  探索用集合   探索用集合
     の開始番号   の開始番号
  0:      1        1
  1:   100000     10000
  2:   200000     20000
  3:   300000     30000
  4:   400000     40000
  5:   500000     50000
  6:   600000     60000
  7:   700000     70000
  8:   800000     80000
  9:   900000     90000

■ 留意事項
・誤った問題番号、誤った設定値でのレポートを提出は受理されません。 但し、他の除数、他のハッシュ増分に対する結果をレポート本文(提出する実行形式ファイルは上記の指定のみ)を含めることは認めます。

3a 二分探索木とAVL木の比較: 平衡化による高速化(比較回数の減少)の検証
◆ AVL木の構築と探索
(0) 探索用要素集合の配列を静的に宣言する。この配列の大きさは0.1Uで、型は上記指定のとおり。
(1) 指定された上記ファイルを読込み、AVL木を構築(add関数)する。
(2) ファイルポインターを先頭に戻す: rewind文(補足事項参照)。
(3) 指定された要素番号の直前まで、ファイルを空読みし、当該要素番号から要素を0.1U個分、(0)で宣言した配列に格納する(補足事項参照)。
(4) この探索用要素配列(成功探索)から要素を取り出し、(1)で構築したAVL木に対して探索する。この探索(search)を0.1U回行うが、0.01U毎に以下の項目を計測し、print出力する。
   (a)総比較回数、 (b)探索時間
-------------------------------------------------------
       10U要素のAVL木に対する1U個の探索操作
 要素数   総比較回数  探索時間(msec)
  0.01U     *******    ***.***
  0.02U     *******     ***.***
  0.03U     *******     ***.***
   ・・・・・
   ・・・・・
  0.09U     *******    ***.***
  0.10U      *******     ***.***
-------------------------------------------------------
◆ 二分探索木の構築と探索
 二分探索木について、上述したAVL木と同様の操作を行う。
 AVL木と二分探索木の2つの計測結果を比較し、様々な観点から分析せよ。なお、提出exeファイルは、AVL木の生成-探索main関数のexeファイルだけでよい





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

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

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

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

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