データ構造とアルゴリズム
空の二分探索木に、1, 2, 3, …, 1000 の順に値を挿入した(つり合いをとる操作はしない)。この木で1000を探すとき、根から比べ始めて、見つかるまでに比べる節の数はいくつか。
- A10
- B500
- C1,000
答えと解説を見る
正解：C. 1,000
昇順に挿入すると、新しい値は毎回それまでの最大値の右の子になるので、木は右にだけ伸びた1本の列(高さ999)になります。1000はいちばん下にあるので、1, 2, …, 1000 の1,000個の節と比べることになり、連結リストを先頭からたどるのと同じ O(n) です。つり合いのとれた木なら段の数は約 log₂ 1000 ≈ 10 なので、AVL木や赤黒木のように挿入や削除のたびに形を整える平衡二分探索木を使えば、最悪でも O(log n) を保てます。
- A. つり合いのとれた木なら約10回ですが、この木は1本の列になっています。
- B. 平均の位置の値を探す場合に近い数で、1000は末尾にあります。
- C. 正しい。木が1本の列になり、1000を探すには全部の節と比べます。