2分探索木の可視化 — 挿入・探索・中間順巡回

2分探索木（BST）とは

各ノードが最大2つの子（左・右）を持つ木のうち、「左の子 ＜ 親 ＜ 右の子」という大小関係を、どのノードでも満たすものを2分探索木といいます。この一貫したルールがあるので、値を探すときに「今のノードより小さければ左、大きければ右」と降りていくだけで、比べるたびに探す範囲が半分ずつ絞られていきます。考え方は 二分探索 と同じで、それを「並べ替え済みの配列」ではなく「木」で実現したものです。

挿入と探索のしくみ

挿入も探索も、やることは同じ「大小をたどって降りる」です。ルートから始め、入れたい（探したい）値とノードの値を比べ、小さければ左の子へ、大きければ右の子へ進みます。探索なら一致したノードで成功、行き止まり（子がいない）に達したら「見つからない」。挿入なら、その行き止まりの位置に新しいノードをぶら下げます。上の可視化で、ルートからオレンジ色にたどっていく経路がこの動きです。

中間順巡回するとソート済みになる

木のすべてのノードを「左の子 → 自分 → 右の子」の順にたどるのが中間順巡回（inorder）です。2分探索木では、これを行うと必ず値が小さい順（昇順）に並びます。「左は自分より小さい・右は自分より大きい」というルールを、木全体で貫いているからです。上の「中間順で巡回」ボタンで、緑色に並んでいく順番を確かめてください。ちなみに「自分 → 左 → 右」は前順（preorder）、「左 → 右 → 自分」は後順（postorder）です。

つまずきやすいポイント

偏ると遅くなる（最悪 O(n)）。 2分探索木が速いのは、木の高さが低い（バランスが取れている）ときだけです。たとえば 1→2→3→4→5 とすでに小さい順に挿入すると、右へ右へと一直線に伸びた木になり、実質は連結リストと同じ。探索は1つずつたどることになり、速さは O(log n) ではなく O(n) に落ちます。ランダムボタンで作った木と、昇順に挿入した木の形を見比べてみてください。

だから「バランス木」がある。 この偏りを自動で直しながら木の高さを低く保つ工夫が、AVL木や赤黒木といった平衡2分探索木です。データベースの索引などで使われるB木・B+木も、同じ「高さを抑えて探索を速くする」発想の仲間です。

巡回の3種類（前順・中間・後順）を混同しない。 「自分をいつ訪れるか」が違うだけです。前順は最初、中間は左と右の間、後順は最後。2分探索木で昇順に取り出したいときは中間順、と覚えておくと試験で迷いません。

基本情報技術者試験ではこう出る

「2分探索木の性質（左＜親＜右）」「木に値を挿入した後の形」「前順・中間・後順の巡回結果を答える」「中間順巡回すると昇順になる」「偏った木の計算量」が定番です。大小で左右に降りる・中間順で昇順・偏るとO(n)の3点を、上の可視化で手を動かして押さえておきましょう。関連：データ構造 ／ 探索アルゴリズム ／ 可視化一覧。

📖 記事で深掘り：スタック・キュー・木構造をやさしく図解 ／ 計算量とO記法