部分木全体のキー範囲を保つ
重複キーを持たない二分探索木では、各ノードの左部分木にはそのキーより小さいもの、右部分木には大きいものを置きます。条件は直下の子だけでなく、その部分木全体に適用されます。根が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)を実現します。キー順の列挙や範囲検索が必要なら探索木が候補になりますが、実装が保つ平衡条件を確認します。