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


■ 実験用データ
　整数集合:　　集合の濃度(要素数): 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) 探査回数、実行時間等、測定結果をプログラムの最後に出力する。