応用情報技術者試験 令和7年度 春期 午前、全80問のうちの問6。
出典：令和7年度 春期 応用情報技術者試験 午前 問6（木の図は、節ごとに左の子と右の子を並べた表に書き起こした。選択肢の木も同じ形の表にし、選択肢の文は表を指す形にした）
図の
| 節 | 左の子 | 右の子 |
|---|---|---|
| 5 | 3 | 7 |
| 3 | 2 | 4 |
| 7 | 6 | なし |
| 節 | 左の子 | 右の子 |
|---|---|---|
| 3 | 1 | 5 |
| 1 | 0 | 2 |
| 5 | 4 | 6 |
| 6 | なし | 7 |
| 節 | 左の子 | 右の子 |
|---|---|---|
| 4 | 2 | 6 |
| 2 | 1 | 3 |
| 1 | 0 | なし |
| 6 | 5 | 7 |
| 節 | 左の子 | 右の子 |
|---|---|---|
| 5 | 3 | 7 |
| 3 | 1 | 4 |
| 1 | 0 | 2 |
| 7 | 6 | なし |
| 節 | 左の子 | 右の子 |
|---|---|---|
| 5 | 3 | 6 |
| 3 | 1 | 4 |
| 1 | 0 | 2 |
| 6 | なし | 7 |
- ア表アの木
- イ表イの木
- ウ表ウの木
- エ表エの木
答えと解説を開く
正解はウです。
AVL 木は、
ほかの選択肢が違う理由
- アAVL 木の
条件は 満たしていますが、 根を 3 に 替える ほど 大きく 組み替えています。 崩れた 節の うち一番下に ある 節 2 で 1 回回転すれば、 節 3 と 節 5 の 差も 1 以下に 戻るので、 根の 5 は 動きません。 - イAVL 木の
条件は 満たしていますが、 根を 4 に 替えて 全体を 作り直しています。 元の 木に 追加して、 崩れた 節 2 だけを 回転した 結果では ありません。 - エ左の
部分木は ウと 同じですが、 右の 部分木で 7 と 6 の 親子が 入れ替わっています。 追加したのは 左の 部分木なので、 右の 部分木は 7 の 左の 子が 6 という 元の 形のままです。
仕組み
AVL 木は、
左の