二分探索木（BST）とは？ 探索・削除・AVL木の回転・赤黒木まで図解で理解する

01｜二分探索木とは何か

例えば、商品番号から商品情報を探す場面を想像してください。番号が大小順に整理されていれば、すべての番号をひとつずつ見る必要はありません。二分探索木は、比較結果で左か右を選びながら目的の値を絞り込むデータ構造です。

二分探索木（Binary Search Tree：BST）は、節点（ノード）ごとにキーを持ち、大小関係に従って左・右の部分木を配置するデータ構造です。一般に左部分木のすべてのキーはその節点より小さく、右部分木のすべてのキーは大きいという規則を満たします。

ここでは重複しない整数キーを扱います。重複キーを許す場合は、同じ値を片側へ寄せる、出現回数を保持するなど、別途規則を定義する必要があります。

02｜根・葉・部分木・高さの用語を整理する

最上位にある節点を根（root）、子を持たない節点を葉（leaf）と呼びます。ある節点以下に広がる木を部分木と呼び、根から葉までの距離を基に木の高さを定義します。

高さは辺の数で数える流儀と節点の数で数える流儀があります。実装や解説を比較するときは定義を確認しましょう。

03｜探索は大小比較を繰り返します

例えば13を探す場合、まず根の12と比較します。13は12より大きいので右の14へ移動します。13は14より小さいので左の13へ移動し、目的のキーが見つかります。

探索経路にない節点を調べる必要はありません。ただし、木が大きく片側に偏ると、比較回数が増える点には注意が必要です。

type Node = { key: number; left: Node | null; right: Node | null };
function find(root: Node | null, target: number): boolean {
  let current = root;
  while (current !== null) {
    if (current.key === target) return true;
    current = target < current.key ? current.left : current.right;
  }
  return false;
}

04｜挿入では適切な空き位置を探します

新しいキーを挿入するときも探索と同じ比較を行います。例えば8を追加する場合、12より小さいので左の9へ進み、9より小さいのでその左側の空き位置へ接続します。既存の節点の順序は変えません。

挿入する順序によって完成する木の形は異なります。昇順に1、2、3、4、5と挿入すると、右に偏った木になるため、効率が落ちます。

05｜削除は子の数によって3つに分かれます

二分探索木の削除は、削除対象の子が0個・1個・2個のどれかで処理が異なります。特に子が2個ある場合は、左右の部分木の大小関係を壊さない代わりの節点を選びます。

「12を削除して13を移動する」ケースでは、12の右部分木の最小値が13なので、13が代わりのキーとして選べます。これは中順後継（inorder successor）に相当します。

06｜中順後継と中順先行を使う理由

ある節点を中順走査の並びで見たとき、直後の値が中順後継、直前の値が中順先行です。キー12の直後は13、直前は11です。子が2個ある節点の置換候補は、通常このいずれかを使います。

右部分木の最小値は、右の子へ一度進んだあと、左の子を辿れるだけ辿って求めます。後継ノードは左の子を持たないため、元の場所から削除するときの接続変更は比較的単純です。

07｜なぜ9・10・14などを自由に移せないのか

新しい根を9にすると、もともと左部分木にある10や11が9より大きくなり、左部分木のキーは根より小さいという規則に反します。同様に根を14にすると、右部分木にある13が14より小さいため規則を壊します。

単に近くにある節点や値が近い節点ならよいわけではありません。左部分木の最大値、または右部分木の最小値を選ぶことが重要です。置換元の枝を調整できるなら、これらの値によって正しい木を再構成できます。

08｜中順走査はキーを昇順で取り出せます

BSTを「左部分木→根→右部分木」の順で走査すると、重複しないキーが昇順に現れます。木の形を変えずにソートされた順番の値を列挙できるため、範囲検索や順序付き集合を考える際に重要な性質です。

function inorder(root: Node | null): number[] {
  if (root === null) return [];
  return [...inorder(root.left), root.key, ...inorder(root.right)];
}

前順走査は根→左→右、後順走査は左→右→根の順です。それぞれ木の複製や後処理などに応用できます。

09｜計算量は木の高さで決まります

探索・挿入・削除では、基本的に根から一方の子へ進んでいくため、計算量は木の高さをhとしてO(h)です。平衡に近い木ではhがO(log n)となり、片側に偏った木ではhがO(n)になる場合があります。

単に二分探索木を使えば常にO(log n)になるわけではありません。データの投入順序と木のバランスを考慮する必要があります。

10｜なぜ平衡木が必要なのでしょうか

商品番号や顧客IDを順番に登録すると、通常の二分探索木は片側へ伸びることがあります。例えば10、20、30、40をこの順に挿入すると、全ての節点が右の子へつながります。この場合、末端を探すには4節点を順番に調べる必要があります。

BSTの操作は木の高さhに比例するため、バランスが良ければO(log n)、偏りが大きければO(n)です。データが追加される順序に性能を左右されにくくするため、AVL木や赤黒木などの自己平衡二分探索木が考えられました。

11｜AVL木：高さの差を厳密に管理します

AVL木は、各節点について左部分木と右部分木の高さの差が最大1になるように保つ木です。平衡係数を「左の高さ − 右の高さ」と定義すると、許される値は−1、0、+1です。高さが空の部分木を0、葉を1として数える場合も、この条件は変わりません。

節点を挿入・削除すると、祖先の平衡係数が+2または−2になる場合があります。そのときは局所的に回転して高さの偏りを直します。

例えば30、20、10を登録した場合はLL型になり、30を右回転すると20が根になります。重要なのは回転しても、左に小さい値・右に大きい値という規則を壊さないことです。

12｜AVL木の4種類の回転を図で確認しましょう

下の図は、3つのキーを順番に挿入したときに現れる最小の例です。LR型とRL型では、1回の回転だけでは中央のキーが適切な位置へ来ないため、2段階で回転します。

実際の木では、この3節点以外にも部分木がぶら下がることがあります。その場合も、回転の際に必要な部分木を付け替えることでBSTの大小関係を保ちます。AVL木では探索・挿入・削除がいずれも最悪O(log n)に抑えられます。

13｜赤黒木：色の規則で偏りを抑えます

赤黒木（Red-Black Tree）は各節点に赤・黒の色を持たせ、色の規則で木の高さが大きくなりすぎないようにする自己平衡木です。AVL木より高さの差を緩やかに許容し、その代わり再調整の規則を使います。

主な規則は、①すべての節点が赤または黒であること、②根は黒であること、③赤い節点の子は黒であること、④各節点から子孫のNIL葉に至る経路で黒い節点の数が同じであることです。ここでNIL葉は通常、黒として扱います。

赤い節点が2つ連続してはいけない一方、黒い節点は連続しても構いません。また、黒い節点数の制約により、最長経路が最短経路の2倍を超えないように保たれます。この性質から探索・挿入・削除を最悪O(log n)で扱えます。

14｜赤黒木は挿入後に回転と色変更を行います

赤黒木では新しい節点を通常は赤として追加します。もし親も赤であれば規則に反するため、親・叔父・祖父の色と位置に応じて修正します。例えば親と叔父が赤なら色変更で対応し、叔父が黒なら木の形に応じて回転と色変更を行うのが代表的な考え方です。

ただし、回転方法や色変更は「親が左か右か」「挿入位置が内側か外側か」で変わるため、単純にすべて同じ操作にはなりません。削除も黒い節点数の規則を保つための再調整が必要です。実装ではNIL葉や親参照などを正確に管理します。

15｜回転が分かる追加ラボで確認しましょう

次のラボではAVL木のLL・RR・LR・RLの4パターンを切り替え、挿入順・回転前・回転後を見比べられます。通常のBSTが偏る形と、平衡化した形の違いを確認してください。

16｜TypeScriptで二分探索木の削除を実装する

type Node = { key: number; left: Node | null; right: Node | null };
function remove(root: Node | null, key: number): Node | null {
  if (root === null) return null;
  if (key < root.key) return { ...root, left: remove(root.left, key) };
  if (key > root.key) return { ...root, right: remove(root.right, key) };
  if (root.left === null) return root.right;
  if (root.right === null) return root.left;
  let successor = root.right;
  while (successor.left !== null) successor = successor.left;
  return {
    key: successor.key,
    left: root.left,
    right: remove(root.right, successor.key),
  };
}

この実装は、新しいオブジェクトを返す方式で参照を再構築しています。元の木を直接書き換えないため、Reactの状態更新にも応用しやすい書き方です。重複キーは存在しない前提で説明しています。

17｜操作ラボ：挿入・探索・削除を体験する

数値を入力して挿入・削除し、木の形を確認できます。探索対象を変えると比較経路が強調表示されます。中順・前順・後順の走査順序や木の高さも同時に確認してみましょう。平衡化は上のAVL回転ラボで確認できます。

最初に12を削除し、13が新しい根になる様子を確認してください。次に昇順でいくつか値を追加すると、片側へ木が伸びていくことも分かります。

18｜まとめと理解度チェック

二分探索木では、左部分木のキーは根より小さく、右部分木のキーは根より大きくなるように配置します。探索・挿入・削除はいずれも木の高さに依存します。子が2個ある節点を削除するときは、中順後継または中順先行を選び、元の節点も適切に取り除くことが重要です。

参考資料

• Binary Search Trees — Open Data Structures
• Introduction to Algorithms — MIT OpenCourseWare
• The AVL Tree — Open Data Structures