アルゴリズム・データ構造図鑑 · 入門

二分探索木:高さが操作時間を決める

左右のキー範囲という不変条件と、偏った木で検索が遅くなる理由を学ぶ。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 部分木全体のキー範囲を保つ
  2. 検索経路を追う
  3. 削除後にも範囲条件を守る
  4. 平衡化しない場合の限界
  5. この記事をロゲイアに質問する理解を確かめる

部分木全体のキー範囲を保つ

重複キーを持たない二分探索木では、各ノードの左部分木にはそのキーより小さいもの、右部分木には大きいものを置きます。条件は直下の子だけでなく、その部分木全体に適用されます。根が8なら左の枝を何段下っても8未満でなければなりません。この範囲の条件により、検索時に比較結果から一方の部分木全体を候補から外せます。重複キーの扱いは別途規則を決めます。

検索経路を追う

8、3、10、1、6、14を順に挿入すると、6を探す経路は8→3→6です。6は8より小さいため左へ進み、3より大きいため右へ進みます。子への参照がなくなるまで一致しなければ、そのキーはありません。比較回数はノード数そのものではなく、その木の高さhに支配され、検索はO(h)です。中順走査では左部分木、ノード、右部分木の順に訪ねるため、キーを昇順で列挙できます。

削除後にも範囲条件を守る

葉の削除は参照を外すだけですが、子が二つあるノードを削除するときは工夫が必要です。たとえば右部分木の最小キーで置き換えれば、左側より大きく右側の残りより小さい関係を保てます。ただ値を任意の子と入れ替えるだけでは、部分木の範囲が壊れることがあります。最小要素への経路などの補助操作を含めても、基本操作の時間は高さhを基準に評価します。

平衡化しない場合の限界

1、2、3、4、5を素朴な二分探索木へ昇順に挿入すると、右側だけへ伸びた鎖のようになります。このとき高さはnに比例し、検索も最悪O(n)です。「二分」だから自動的にO(log n)にはなりません。AVL木や赤黒木などは回転等で高さを制御し、基本操作の最悪O(log n)を実現します。キー順の列挙や範囲検索が必要なら探索木が候補になりますが、実装が保つ平衡条件を確認します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ