二分木

二分木（Binary Tree）とは

二分木は、データ構造における基本的な概念の一つで、各ノード（節点）が最大で2つの子を持つ木構造のことです。これらの子は通常、「左の子」と「右の子」と呼ばれます。二分木は、そのシンプルな構造にもかかわらず、様々なアルゴリズムやデータ構造の基盤として広く利用されています。

二分木の基本用語

• - ノード（Node）: 木構造における各要素のこと。データと子ノードへの参照を持ちます。
• - 根（Root）: 木構造の最上位にあるノード。二分木には必ず一つの根があります。
• - 葉（Leaf）: 子を持たないノード。外部ノードとも呼ばれます。
• - 内部ノード（Internal Node）: 葉でないノード。少なくとも1つの子を持ちます。
• - 辺（Edge）: 親ノードと子ノードを結ぶ線。
• - 深さ（Depth）: 根からあるノードまでの経路の長さ。経由するノード数で数えます。
• - レベル（Level）: 木の特定の深さにあるノードの集合。
• - 高さ（Height）: あるノードから最も遠い葉までの経路の長さ。
• - 兄弟（Siblings）: 同じ親を持つノード。
• - 先祖（Ancestor）: あるノードから根に至る経路上のノード。
• - 子孫（Descendant）: あるノードから葉に至る経路上のノード。
• - 大きさ（Size）: あるノードとその子孫ノードの総数。

二分木の種類

二分木には、いくつかの特殊な種類があります。

全二分木（Full Binary Tree）

全てのノードが、葉であるか、またはちょうど二つの子を持つ二分木。

完全二分木（Perfect Binary Tree / Complete Binary Tree）

全ての葉が同じ深さにある二分木。または、ある深さnにおいて、深さnまたはn-1の葉を持ち、すべての葉が左に寄せられている二分木。

ほとんど完全な二分木（Almost Complete Binary Tree）

右の子を持つ場合は必ず左の子も持つが、その逆は必ずしも真でない二分木。

グラフ理論における二分木

グラフ理論では、二分木は「連結していて閉路を持たないグラフであり、各頂点の次数（接続する辺の数）が3を超えないもの」と定義されます。この定義から、葉の数は次数3のノードの数よりも2つ多いことが証明できます。根付き二分木は、根が一つだけ決まっており、各頂点の次数が2を超えないものと定義されます。

二分木の実装

二分木は、プログラミング言語の基本的な要素を用いて実装できます。

レコード型とポインタ型による実装

通常、データ、左の子へのポインタ、右の子へのポインタを持つノードを組み合わせることで木を構成します。場合によっては親へのポインタも保持します。子がない場合は、特別な値（nilやnull）で表現します。

配列による実装

完全二分木の場合、配列を使って効率的に二分木を表現できます。根のインデックスを0とすると、ノードiの子は2i+1と2i+2に、親はfloor((i-1)/2)に格納されます。この方法はメモリ効率が良いですが、木が大きくなるとメモリの確保や移動に時間がかかる場合があります。

タグ付き共有体による実装

MLのような言語では、タグ付き共有体を使って二分木を表現できます。この方法では、データと子への参照を持つノードと、データを持たない葉ノードの2種類を使います。

二分木の巡回

二分木の各ノードを訪問する方法はいくつかあり、それぞれに特徴があります。

深さ優先探索（Depth-First Search）

• - 行きがけ順（Preorder）: 根→左部分木→右部分木の順で訪問します。
• - 通りがけ順（Inorder）: 左部分木→根→右部分木の順で訪問します。
• - 帰りがけ順（Postorder）: 左部分木→右部分木→根の順で訪問します。

幅優先探索（Breadth-First Search）

根に近いノードから順に訪問します。

二分木の応用例

二分探索木（Binary Search Tree）

各ノードに値を割り当て、左の子孫が親よりも小さく、右の子孫が親よりも大きくなるように構成された二分木。データの検索やソートに利用されます。

平衡二分探索木

二分探索木の検索効率を最大化するために、木の高さをできるだけ均等にしたもの。

バイナリヒープ

半順序集合を二分木で表現したもの。親子の間に大小関係が成立するよう構成され、優先度付きキューなどに利用されます。

算術式の構文木

算術式を二分木で表現したもの。式の解析や計算に利用されます。

二分木のエンコーディング

二分木をコンパクトに表現する方法として、簡潔符号化があります。行きがけ順にノードを訪問し、内部ノードなら1、葉なら0を出力することで、木構造をビット列で表現できます。

N進木の二分木表現

一般の順序木を二分木で表現する方法もあります。順序木の各ノードの子を連結リストのように右フィールドでつなぎ、最初の要素を左フィールドに入れることで、二分木で表現できます。

まとめ

二分木は、そのシンプルさと柔軟性から、様々な分野で広く活用されている重要なデータ構造です。この記事では、二分木の基本的な概念から、実装方法、応用例まで幅広く解説しました。二分木を理解することは、コンピュータサイエンスの基礎を学ぶ上で非常に重要です。

もう一度検索