基本情報技術者試験「平衡2分探索木」の問題
AVL木などの平衡2分探索木を用いる主な目的として最も適切なものはどれか。
アノードを連結するポインタを完全に廃止し全要素を連続したメモリ領域に詰めて格納することでメモリ使用量を大きく削減すること
イ要素を一切並べ替えず到着順に末尾へ追加し、挿入を必ずO(1)で完了させること
ウ同じ値の重複登録を物理的に禁止し、集合演算の和や積を高速化すること
エ挿入や削除のたびに木の高さの偏りを抑え、探索を常にO(log n)に近く保つこと
正解
エ．挿入や削除のたびに木の高さの偏りを抑え、探索を常にO(log n)に近く保つこと
AVL木は各ノードで左右部分木の高さの差を一定以下に保つよう回転で再平衡する。これにより木が一方向に偏って高さがnに近づくのを防ぎ、探索・挿入・削除をO(log n)に保てるため正しい。
?選択肢ごとの解説
ア ×ポインタを廃止し連続領域に格納するのは配列の発想であり、ノードをポインタでつなぐ木構造の説明ではない。平衡化の目的とも無関係である。
イ ×並べ替えず末尾へ追加して挿入O(1)にするのはスタックやキューの挙動であり、順序を保ちながら平衡を維持するAVL木の目的とは異なる。
ウ ×重複禁止と集合演算高速化は集合データ型の目的に近く、AVL木が高さの偏りを抑えて探索効率を保つという本来の目的とは別である。
エ ○AVL木は各ノードで左右部分木の高さの差を一定以下に保つよう回転で再平衡する。これにより木が一方向に偏って高さがnに近づくのを防ぎ、探索・挿入・削除をO(log n)に保てるため正しい。
✎くわしく
単純な2分探索木は挿入順によって一方向に偏り高さがO(n)に劣化しうる。AVL木やB木系は再平衡操作(回転など)で高さをO(log n)に抑え、最悪計算量を保証する。平衡を保つコストと引き換えに探索性能の安定を得る点が要点である。
✓本番での押さえどころ
試験のコツ
『平衡木=高さの偏りを抑えてO(log n)を保証する木』と一文で押さえる。偏ると最悪O(n)に劣化する点と対で覚える。
覚え方
AVLは『天秤(バランス)を取り続ける木』。傾いたら回転で水平に戻す、と天秤でイメージする。
よくある誤り
平衡木の目的を『メモリ削減』や『挿入を速くするだけ』と誤解する例がある。狙いは高さの偏り抑制による安定した探索効率である。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0126