2019年度 第3回 平衡性とAVL木 演習課題




二分探索木およびAVL木の構築

前半グループ: 整数集合(integer1MR.dat)
番号 / 計測する回転の種類
0, 1 / LL回転・LR回転
2, 3 / LL回転・RR回転
4, 5 / LL回転・RL回転
6, 7 / RR回転・LR回転
8, 9 / RR回転・RL回転


二分探索木
要素数高さ構築時間[msec]
1U41 (± 1)----
2U44 (± 1)----
3U45 (± 1)----
4U46 (± 1)----
5U47 (± 1)----
6U48 (± 1)----
7U49 (± 1)----
8U49 (± 1)----
9U49 (± 1)----
10U49 (± 1)----



AVL木
学籍番号末尾 = 0, 1
要素数高さLL回転LR回転構築時間[msec]
1U19 (± 1)11662 (± 1)11483 (± 1)----
2U20 (± 1)23321 (± 1)23130 (± 1)----
3U21 (± 1)35057 (± 1)34778 (± 1)----
4U22 (± 1)46572 (± 1)46496 (± 1)----
5U22 (± 1)58341 (± 1)58144 (± 1)----
6U22 (± 1)69995 (± 1)69732 (± 1)----
7U23 (± 1)81665 (± 1)81360 (± 1)----
8U23 (± 1)93389 (± 1)93055 (± 1)----
9U23 (± 1)105002 (± 1)104663 (± 1)----
10U23 (± 1)116847 (± 1)116293 (± 1)----


学籍番号末尾 = 2, 3
要素数高さLL回転RR回転構築時間[msec]
1U19 (± 1)11662 (± 1)11657 (± 1)----
2U20 (± 1)23321 (± 1)23314 (± 1)----
3U21 (± 1)35057 (± 1)35066 (± 1)----
4U22 (± 1)46572 (± 1)46857 (± 1)----
5U22 (± 1)58341 (± 1)58683 (± 1)----
6U22 (± 1)69995 (± 1)70304 (± 1)----
7U23 (± 1)81665 (± 1)81917 (± 1)----
8U23 (± 1)93389 (± 1)93651 (± 1)----
9U23 (± 1)105002 (± 1)105234 (± 1)----
10U23 (± 1)116847 (± 1)116785 (± 1)----


学籍番号末尾 = 4, 5
要素数高さLL回転RL回転構築時間[msec]
1U19 (± 1)11662 (± 1)11463 (± 1)----
2U20 (± 1)23321 (± 1)23147 (± 1)----
3U21 (± 1)35057 (± 1)34770 (± 1)----
4U22 (± 1)46572 (± 1)46249 (± 1)----
5U22 (± 1)58341 (± 1)57986 (± 1)----
6U22 (± 1)69995 (± 1)69655 (± 1)----
7U23 (± 1)81665 (± 1)81371 (± 1)----
8U23 (± 1)93389 (± 1)92956 (± 1)----
9U23 (± 1)105002 (± 1)104435 (± 1)----
10U23 (± 1)116847 (± 1)115923 (± 1)----


学籍番号末尾 = 6, 7
要素数高さRR回転LR回転構築時間[msec]
1U19 (± 1)11657 (± 1)11483 (± 1)----
2U20 (± 1)23314 (± 1)23130 (± 1)----
3U21 (± 1)35066 (± 1)34778 (± 1)----
4U22 (± 1)46857 (± 1)46496 (± 1)----
5U22 (± 1)58683 (± 1)58144 (± 1)----
6U22 (± 1)70304 (± 1)69732 (± 1)----
7U23 (± 1)81917 (± 1)81360 (± 1)----
8U23 (± 1)93651 (± 1)93055 (± 1)----
9U23 (± 1)105234 (± 1)104663 (± 1)----
10U23 (± 1)116785 (± 1)116293 (± 1)----


学籍番号末尾 = 8, 9
要素数高さRR回転RL回転構築時間[msec]
1U19 (± 1)11657 (± 1)11463 (± 1)----
2U20 (± 1)23314 (± 1)23147 (± 1)----
3U21 (± 1)35066 (± 1)34770 (± 1)----
4U22 (± 1)46857 (± 1)46249 (± 1)----
5U22 (± 1)58683 (± 1)57986 (± 1)----
6U22 (± 1)70304 (± 1)69655 (± 1)----
7U23 (± 1)81917 (± 1)81371 (± 1)----
8U23 (± 1)93651 (± 1)92956 (± 1)----
9U23 (± 1)105234 (± 1)104435 (± 1)----
10U23 (± 1)116785 (± 1)115923 (± 1)----