二分探索木では、左部分木の値はそのノードより小さく、右部分木の値は大きくなります。比較のたびに左右どちらかへ進むため、バランスの良い木では効率よく検索できます。
二分探索木の挿入・検索・削除シミュレーター
1. 例を読み込むか木をクリア
2. 値を入力して操作を選択
ノード数0
高さ（最長経路のノード数）0
検索の最大比較回数0
挿入と検索では根からの経路がオレンジ色になります。整列済みの値で作成すると木が偏る様子を確認できます。
検索・挿入・削除
根から検索を始め、小さい値なら左、大きい値なら右の子へ進みます。挿入も同じ経路をたどり、最初の空き位置にノードを追加します。
削除方法は子の数によって異なります。葉はそのまま削除し、子が1つならその子で置き換えます。子が2つなら右部分木の最小値で置き換え、大小関係を維持します。
木の形が性能を決める
最悪時の比較回数は木の高さと同じです。平衡な木の高さはO(log n)ですが、通常の二分探索木に整列済みデータを挿入すると高さnの鎖になります。AVL木や赤黒木は回転や平衡条件により高さをO(log n)に保ちます。