基本情報技術者 予想問題｜A 第22問

解説

正解はイ。二分木では各ノードが最大2つの子を持つため、深さが1増えるごとに配置できるノード数が約2倍になる。高さhの完全な二分木は最大2^(h＋1)−1個のノードを持つので、n個のノードを格納するために必要な高さはおよそlog₂nであり、オーダーはO(log n)となる。AVL木や赤黒木などの平衡二分探索木はこのバランスを自動的に維持し、探索・挿入・削除をO(log n)で実現する。ウのO(n)は、一方向に偏って連結リスト状になった二分木の最悪ケースの高さであり、バランスが取れた場合の説明ではない。アのO(1)とエのO(n²)は二分木の高さとして該当しない。基本情報では二分探索木の探索効率が頻出であり、平衡時O(log n)・偏り時O(n)の対比を押さえること。