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] |
1U | 41 (± 1) | ---- |
2U | 44 (± 1) | ---- |
3U | 45 (± 1) | ---- |
4U | 46 (± 1) | ---- |
5U | 47 (± 1) | ---- |
6U | 48 (± 1) | ---- |
7U | 49 (± 1) | ---- |
8U | 49 (± 1) | ---- |
9U | 49 (± 1) | ---- |
10U | 49 (± 1) | ---- |
AVL木
学籍番号末尾 = 0, 1
要素数 | 高さ | LL回転 | LR回転 | 構築時間[msec] |
1U | 19 (± 1) | 11662 (± 1) | 11483 (± 1) | ---- |
2U | 20 (± 1) | 23321 (± 1) | 23130 (± 1) | ---- |
3U | 21 (± 1) | 35057 (± 1) | 34778 (± 1) | ---- |
4U | 22 (± 1) | 46572 (± 1) | 46496 (± 1) | ---- |
5U | 22 (± 1) | 58341 (± 1) | 58144 (± 1) | ---- |
6U | 22 (± 1) | 69995 (± 1) | 69732 (± 1) | ---- |
7U | 23 (± 1) | 81665 (± 1) | 81360 (± 1) | ---- |
8U | 23 (± 1) | 93389 (± 1) | 93055 (± 1) | ---- |
9U | 23 (± 1) | 105002 (± 1) | 104663 (± 1) | ---- |
10U | 23 (± 1) | 116847 (± 1) | 116293 (± 1) | ---- |
学籍番号末尾 = 2, 3
要素数 | 高さ | LL回転 | RR回転 | 構築時間[msec] |
1U | 19 (± 1) | 11662 (± 1) | 11657 (± 1) | ---- |
2U | 20 (± 1) | 23321 (± 1) | 23314 (± 1) | ---- |
3U | 21 (± 1) | 35057 (± 1) | 35066 (± 1) | ---- |
4U | 22 (± 1) | 46572 (± 1) | 46857 (± 1) | ---- |
5U | 22 (± 1) | 58341 (± 1) | 58683 (± 1) | ---- |
6U | 22 (± 1) | 69995 (± 1) | 70304 (± 1) | ---- |
7U | 23 (± 1) | 81665 (± 1) | 81917 (± 1) | ---- |
8U | 23 (± 1) | 93389 (± 1) | 93651 (± 1) | ---- |
9U | 23 (± 1) | 105002 (± 1) | 105234 (± 1) | ---- |
10U | 23 (± 1) | 116847 (± 1) | 116785 (± 1) | ---- |
学籍番号末尾 = 4, 5
要素数 | 高さ | LL回転 | RL回転 | 構築時間[msec] |
1U | 19 (± 1) | 11662 (± 1) | 11463 (± 1) | ---- |
2U | 20 (± 1) | 23321 (± 1) | 23147 (± 1) | ---- |
3U | 21 (± 1) | 35057 (± 1) | 34770 (± 1) | ---- |
4U | 22 (± 1) | 46572 (± 1) | 46249 (± 1) | ---- |
5U | 22 (± 1) | 58341 (± 1) | 57986 (± 1) | ---- |
6U | 22 (± 1) | 69995 (± 1) | 69655 (± 1) | ---- |
7U | 23 (± 1) | 81665 (± 1) | 81371 (± 1) | ---- |
8U | 23 (± 1) | 93389 (± 1) | 92956 (± 1) | ---- |
9U | 23 (± 1) | 105002 (± 1) | 104435 (± 1) | ---- |
10U | 23 (± 1) | 116847 (± 1) | 115923 (± 1) | ---- |
学籍番号末尾 = 6, 7
要素数 | 高さ | RR回転 | LR回転 | 構築時間[msec] |
1U | 19 (± 1) | 11657 (± 1) | 11483 (± 1) | ---- |
2U | 20 (± 1) | 23314 (± 1) | 23130 (± 1) | ---- |
3U | 21 (± 1) | 35066 (± 1) | 34778 (± 1) | ---- |
4U | 22 (± 1) | 46857 (± 1) | 46496 (± 1) | ---- |
5U | 22 (± 1) | 58683 (± 1) | 58144 (± 1) | ---- |
6U | 22 (± 1) | 70304 (± 1) | 69732 (± 1) | ---- |
7U | 23 (± 1) | 81917 (± 1) | 81360 (± 1) | ---- |
8U | 23 (± 1) | 93651 (± 1) | 93055 (± 1) | ---- |
9U | 23 (± 1) | 105234 (± 1) | 104663 (± 1) | ---- |
10U | 23 (± 1) | 116785 (± 1) | 116293 (± 1) | ---- |
学籍番号末尾 = 8, 9
要素数 | 高さ | RR回転 | RL回転 | 構築時間[msec] |
1U | 19 (± 1) | 11657 (± 1) | 11463 (± 1) | ---- |
2U | 20 (± 1) | 23314 (± 1) | 23147 (± 1) | ---- |
3U | 21 (± 1) | 35066 (± 1) | 34770 (± 1) | ---- |
4U | 22 (± 1) | 46857 (± 1) | 46249 (± 1) | ---- |
5U | 22 (± 1) | 58683 (± 1) | 57986 (± 1) | ---- |
6U | 22 (± 1) | 70304 (± 1) | 69655 (± 1) | ---- |
7U | 23 (± 1) | 81917 (± 1) | 81371 (± 1) | ---- |
8U | 23 (± 1) | 93651 (± 1) | 92956 (± 1) | ---- |
9U | 23 (± 1) | 105234 (± 1) | 104435 (± 1) | ---- |
10U | 23 (± 1) | 116785 (± 1) | 115923 (± 1) | ---- |