二分探索木（BST）
値を入れるたびに 「小さければ左、大きければ右」で木が組み上がり、探索が速くなる仕組みを見ます。
0
挿入する数列
値を探す：
二分探索木は、どのノードも「左の子孫はすべて自分より小さい／右の子孫はすべて大きい」を満たす木です。
値を挿入するときも探すときも、根から比べて小さければ左・大きければ右へ降りるだけ。 木のバランスが良ければ 1 回降りるごとに候補が半分になり、探索は O(log n) です。
値を 1 つずつ挿入して木が育つ様子を見て、最後に探索もしてみてください。
値を挿入するときも探すときも、根から比べて小さければ左・大きければ右へ降りるだけ。 木のバランスが良ければ 1 回降りるごとに候補が半分になり、探索は O(log n) です。
値を 1 つずつ挿入して木が育つ様子を見て、最後に探索もしてみてください。
いま何をしている？
ここがポイント
- 挿入・探索とも 根から「小さければ左／大きければ右」をたどるだけ。
- 左部分木 < 親 < 右部分木 ── この順序が常に保たれる（中順走査でソート済みになる）。
- 木が高く偏ると O(n) に劣化する。これを防ぐのが平衡二分探索木（AVL 木・赤黒木）。