データ構造の基礎知識：根なし二分木（アンルーテッド・バイナリツリー）とは？

本記事では、データ構造の一種である根なし二分木（unrooted binary tree）について解説します。根なし二分木は、閉路（サイクル）を持たない連結な無向グラフとして定義される木構造です。

根なし二分木の基本概念

根なし二分木には「根」となる特定の頂点が存在せず、すべての頂点が対等な立場で扱われる点が大きな特徴です。この木構造における各要素は、以下のように分類されます。

• 葉（リーフ）：隣接する頂点（近傍ノード）を1つだけ持つ頂点
• 内部ノード：葉以外の残りのすべての頂点

また、頂点の次数（degree）とは、その頂点に隣接する頂点の数を指します。2つ以上のノードを持つ木において、葉は次数1の頂点と定義されます。

フリーツリー（自由木）との関係

フリーツリー（free tree）は根なし二分木の一種であり、すべての内部ノードがちょうど次数3を持つという性質を持ちます。つまり、各内部ノードは必ず3つの隣接頂点と結ばれているため、全体として均整の取れた構造になります。

コンピュータサイエンスにおける位置づけ

コンピュータサイエンスの分野では、二分木はデータ構造として扱われる際、根付き（rooted）かつ順序付き（ordered）の形式で用いられることが一般的です。例えば、二分探索木やヒープなどがその代表例です。

しかしながら、根なし二分木にも重要な応用分野があります。特に以下の2つの領域において、その有用性が高く評価されています。

• 階層的クラスタリング（hierarchical clustering）：データ間の類似度に基づいて、クラスタを段階的に統合・分割していく分析手法。根なし二分木はクラスタ間の関係を柔軟に表現できます。
• 系統樹の再構成（evolutionary tree reconstruction）：生物種や遺伝子の進化の過程を推定する際に用いられる手法。進化の方向性が不確実な場合、根を設けない木構造が適しています。

このように、根なし二分木は一見シンプルな構造ながら、機械学習やバイオインフォマティクスなど、幅広い分野で活用されている重要なデータ構造です。