2分探索木(ニブンタンサクギ)とは | 意味や読み方など丁寧でわかりやすい用語解説

2分探索木は、データを効率的に格納し、検索、挿入、削除といった操作を高速に行うための基本的なデータ構造の一つである。主に、データが数値や文字列のように順序付け可能な場合に利用される。このデータ構造は、各ノードが最大で二つの子ノードを持つ「木構造」を基本とし、その名の通り「2分」という特性から、データの探索が非常に効率的になるように設計されている。

具体的な特性として、2分探索木では、任意のノードが持つ値よりも小さい値を持つノードは常にそのノードの左の子孫に、大きい値を持つノードは常にそのノードの右の子孫に配置されるという規則が厳密に守られる。この規則のおかげで、ある特定の値を探索する際に、すべてのデータを一つずつ確認する線形探索とは異なり、探索のたびに候補となるデータの範囲を半分に絞り込むことが可能となる。そのため、データの量が増えるほど、その探索効率のメリットは顕著になる。システム開発においては、データベースのインデックスや辞書の実装など、高速なデータアクセスが求められる様々な場面でその概念が活用されている。

次に、2分探索木の構造と具体的な操作について詳しく説明する。 2分探索木は、「ノード」と呼ばれる要素の集まりで構成される。各ノードは通常、データ（値）と、左の子ノードと右の子ノードへの参照（ポインタ）を持っている。最も上位にあるノードは「根（ルート）ノード」と呼ばれ、探索や挿入などの操作は常にこの根ノードから開始される。子ノードを持たないノードは「葉（リーフ）ノード」と呼ばれる。また、あるノードを根とする、その下位のノード群を「部分木」と呼ぶ。

探索操作は、特定の値を木の中から見つけ出すプロセスである。探索を開始する際は、まず根ノードの値を探索対象の値と比較する。もし探索対象の値がノードの値よりも小さい場合は左の子ノードへ、大きい場合は右の子ノードへと進む。この比較と移動を繰り返すことで、探索対象の値を持つノードが見つかるまで木を下っていく。もし途中で次に進むべき子ノードが存在しないにもかかわらず探索対象の値が見つからなかった場合、その値は木の中に存在しないと判断される。

挿入操作は、新しいデータを木に追加するプロセスである。挿入したい値のノードをどこに配置するかを決定するために、探索操作とほぼ同じ手順を踏む。根ノードから開始し、挿入したい値と各ノードの値を比較しながら、左または右の子ノードへと進んでいく。最終的に、次に進むべき子ノードが存在しない位置に到達したとき、その位置に新しいノードとして値を挿入する。このとき、既存の2分探索木の規則（左の子孫は小さく、右の子孫は大きい）が破られないように、適切な位置に挿入される。挿入されるデータの順序によって木の形状が大きく変わり、これが性能に影響を与える可能性がある。

削除操作は、既存のノードを木から取り除くプロセスであり、最も複雑な操作の一つである。削除対象のノードが見つかった場合、そのノードが持つ子ノードの数によって処理が異なる。 まず、削除対象のノードが子ノードを持たない「葉ノード」である場合、そのノードを単に削除するだけで良い。 次に、削除対象のノードが1つの子ノードを持つ場合、削除対象のノードを木から取り除き、その子ノードを削除対象ノードの親ノードに直接繋ぎ変える。 最後に、削除対象のノードが2つの子ノードを持つ場合、このケースが最も複雑である。この場合、削除対象ノードの右部分木の中から最も小さい値を持つノード、または左部分木の中から最も大きい値を持つノードを見つけ出す。そして、その見つけ出したノードの値を削除対象ノードの値と入れ替える。その後、入れ替えたノード（もともと最も小さい値または最も大きい値だったノード）を、先述した「子ノードが0個または1個の場合」のルールに従って削除する。この手順により、木の2分探索木の特性を維持しつつノードを削除できる。

これらの操作にかかる時間は、木の高さに比例する。理想的な2分探索木（平衡の取れた木）の場合、高さはデータの数Nに対してlog₂Nに比例するため、探索、挿入、削除の平均計算量はO(log N)となる。これはデータ量Nが増えても非常に高速であることを意味する。しかし、データが既にソートされた順序で挿入された場合など、特定の状況下では木が片側に偏った形状となり、探索が線形探索に近いO(N)の計算量になってしまうことがある。このような最悪のケースを避けるためには、「平衡2分探索木」（例えば、AVL木や赤黒木など）と呼ばれる、木のバランスを自動的に調整する仕組みを持った高度なデータ構造を利用する必要があるが、これは2分探索木の基本的な理解を超えた内容となる。

2分探索木は、そのシンプルながらも強力なデータ整理能力により、コンピュータサイエンスの基礎として、そして実用的なシステム開発における効率的なデータ管理手段として広く利用されている。