問題プレビューID: 85cfbe26応用情報技術者試験 2025年(令和7年度)春期 午前

問 6
応用情報技術者試験 2025年(令和7年度)春期 午前

図の 2 分探索木に 1 と 0 の二つの要素を順に追加した AVL 木として,適切なものはどれか。

解説

正解は「ウ」です。

2 分探索木に 1 と 0 を順に追加します。まず 1 は,5→3→2 とたどって 2 の左の子として追加されます。この時点では各節点で左右の部分木の高さの差は 1 以下であり,回転は不要です。

次に 0 は,5→3→2→1 とたどって 1 の左の子として追加されます。このとき節点 2 で左部分木の高さが 2 大きくなり,AVL 木の平衡条件(左右の部分木の高さの差が 1 以下)を満たさなくなります。これは左の子の左側が伸びた「左左(LL)型」の不均衡なので,節点 2 を中心に右回転を行います。

その結果,節点 1 が 2 の位置に上がり,1 の左の子が 0,右の子が 2 となります。最終的な木は,根が 5,左部分木が 3(左に 1(その左に 0,右に 2),右に 4),右部分木が 7(左に 6)となり,選択肢ウと一致します。

  • ア・イ・エ: 追加後の平衡条件を満たすように回転した結果とは一致しません。

関連問題

本文が同じ・似ている問題を表示しています