2017年度 第3回 平衡性とAVL木 演習課題
二分探索木およびAVL木の構築
後半グループ: 文字列集合(wordE100KR.dat)
番号 / 計測する回転の種類
0, 1 / LL回転・LR回転
2, 3 / LL回転・RR回転
4, 5 / LL回転・RL回転
6, 7 / RR回転・LR回転
8, 9 / RR回転・RL回転
※構築時間は実行環境により異なります
二分探索木
| 要素数 | 高さ | 構築時間[msec] |
| 1U | 44 (±1) | ***.** |
| 2U | 45 (±1) | ***.** |
| 3U | 45 (±1) | ***.** |
| 4U | 48 (±1) | ***.** |
| 5U | 48 (±1) | ***.** |
| 6U | 48 (±1) | ***.** |
| 7U | 48 (±1) | ***.** |
| 8U | 49 (±1) | ***.** |
| 9U | 50 (±1) | ***.** |
| 10U | 50 (±1) | ***.** |
AVL木
| 要素数 | 高さ | LL回転 | LR回転 | RR回転 | RL回転 | 構築時間[msec] |
| 1U | 15 (±1) | 1115 (±1) | 1458 (±1) | 1808 (±1) | 1099 (±1) | ***.** |
| 2U | 16 (±1) | 2217 (±1) | 2929 (±1) | 3582 (±1) | 2219 (±1) | ***.** |
| 3U | 17 (±1) | 3296 (±1) | 4424 (±1) | 5243 (±1) | 3307 (±1) | ***.** |
| 4U | 17 (±1) | 4338 (±1) | 5851 (±1) | 6749 (±1) | 4482 (±1) | ***.** |
| 5U | 18 (±1) | 5457 (±1) | 7277 (±1) | 8251 (±1) | 5609 (±1) | ***.** |
| 6U | 18 (±1) | 6564 (±1) | 8648 (±1) | 9736 (±1) | 6748 (±1) | ***.** |
| 7U | 18 (±1) | 7645 (±1) | 9975 (±1) | 11099 (±1) | 7924 (±1) | ***.** |
| 8U | 19 (±1) | 8715 (±1) | 11297 (±1) | 12502 (±1) | 9098 (±1) | ***.** |
| 9U | 19 (±1) | 9842 (±1) | 12587 (±1) | 13976 (±1) | 10169 (±1) | ***.** |
| 10U | 19 (±1) | 11016 (±1) | 13862 (±1) | 15338 (±1) | 11319 (±1) | ***.** |