演習課題 第3回 平衡木(2017、2019年度)

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

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

■ 集合、パラメーター設定
・学籍番号の最下位桁の値によって、集合、パラメーター(探索値集合の開始番号)が異なります。
　　　　前半のグループ　　　　後半のグループ
　　　　集合: 整数集合　　　　集合: 文字列集合
番号　　探索用集合　　　探索用集合
　　　　　回転の種類　　　回転の種類
　　0, 1:　　LL, LR　　　　　 LL, LR
　　2, 3: 　 LL, RR　　　　　 LL, RR
　　4, 5: 　 LL, RL　　　　　 LL, RL
　　6, 7: 　 RR, LR　　　　　 RR, LR
　　8, 9: 　 RR, RL　　　　　 RR, RL

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



3a 平衡化(回転操作)の計測
　上記のファイルを読み込み、二分探索木、AVL木の2つを生成する(追加関数)。
読込みレコード数(要素数)を以下のようにUずつ増加させた時点で、
　　　1U、2U、3U、・・・・・、9U、10U
それぞれ以下の項目について計測する(例えば番号0, 1)。
　　　二分探索木: 木の高さ、構築時間
　　　AVL木:　　 　木の高さ、LL回転、LR回転、構築時間
　例えば、以下のような書式で出力する。

二分探索木
　　　要素数　　高さ　　構築時間(msec.)
　　　1U　　　　　　　　　　　
　　　2U　　　　　　　　　　　
　　　　　　・　・　・　・
　　　　　　・　・　・　・
　　10U　　　　　　　　　　　

AVL木(例えば番号0, 1)
　　　要素数　　高さ　LL回転　　LR回転　構築時間(msec)
　　　1U　　・　・　・　・　・　・　・　・　・　・　・　・　・　秒
　　　2U　　・　・　・　・　・　・　・　・　・　・　・　・　・　秒
　　　　　　・　・　・　・　・　・　・　・　・　・　・　
　　　　　　・　・　・　・　・　・　・　・　・　・　・　
　　　9U　　　・　・　・　・　・　・　・　・　・　・　・　
　　 10U　　・　・　・　・　・　・　・　・　・　・　・　・　・　秒
* 構築時間はミリ秒(msec.)で測定する。　これらのデータを様々な観点から分析せよ。
　なお、提出exeファイルは、AVL木main関数のexeファイルだけでよい。


3b 平衡度測定関数の作成【選択問題: 両グループ】
二分探索木およびAVL木を対象とした個々の節の平衡度を測定する関数を作成する(平衡度測定関数)。先頭の5Uレコード(要素)を対象に、二分探索木およびAVL木を生成し、それぞれの木の全節に対して、平衡度測定関数を適用する(節の巡回)。結果として、それぞれの木の総平衡度および平均平衡度を算出する。
　次に、1Uレコードに対して、上記と同様の処理を行う。
　レポートの内容としては、作成した平衡度測定関数のアルゴリズムおよびプログラムコードについての明確かつ詳細な説明および、2つの要素集合に対する2種類の木の平衡度についての解析結果についての説明を含むものとする(対象集合は整数集合とする)。