【解説】 ２分探索木について
**2分探索木（Binary Search Tree, BST）**は、データの検索、挿入、削除を効率的に行うためのデータ構造です。
単なる「2分木（各ノードが最大2つの子を持つ木）」に、特定のルール（順序関係）を加えたものだと考えると分かりやすいですよ。
1. 2分探索木の基本ルール
すべてのノードにおいて、以下の条件が守られている必要があります。
-
左の子ノードの値は、親ノードの値よりも小さい。
-
右の子ノードの値は、親ノードの値よりも大きい。
2. なぜこの構造が嬉しいのか？（メリット）
最大のメリットは、**「探しものがとにかく早い」**ことです。
例えば、ある数字を探すとき、現在のノードと比較するだけで「次は左（小さい方）か右（大きい方）か」を即座に判断できます。これにより、探索の範囲を毎回半分に絞り込めるため、計算量は平均して
となります。
例： 1,000個のデータがあっても、たった10回程度の比較で見つけ出せる計算です。
3. 基本操作のイメージ
探索 (Search)
-
探したい値が今のノードより小さければ左へ、大きければ右へ進む。
-
一致すれば見つかり、どこにも行けなくなれば「存在しない」と判定。
具体的には，
・pがさしているノードをaとする。もしa=NULLならばNULLを返して処理を終了し，x=a.keyならばpを答えとして「返して処理を終了する。
・もしx<a.keyならばp←a.leftとし，x>a.keyならばp←a.rightとして次のループに移る。
例えば，上の図において，7を検索するとき次のステップを経て，検索値を得る。
「7を探したい」
「7<8なので左へ」
「3<7なので右へ」
「6<7なので右へ」
挿入 (Insertion)
-
探索と同じ手順で進み、空いている場所（リーフ）に新しい値を配置する。
削除 (Deletion)
削除は少し工夫が必要です。
-
子がいない場合： そのまま消すだけ。
-
子が1つの場合： 子を自分のいた場所に昇格させる。
-
子が2つの場合： 「右側の木の中で一番小さい値」または「左側の木の中で一番大きい値」を持ってきて入れ替える。