ツリー（抽象データ型）

コンピュータサイエンスにおいて、ツリーは広く使用されている抽象データ型であり、接続されたノードのセットを持つ階層的なツリー構造を表します。ツリー内の各ノードは、（ツリーの種類に応じて）多くの子に接続できますが、ルートノードを除いて、正確に 1 つの親に接続する必要があります^[1] 。ルートノードには親がありません（つまり、ルートノードはツリー階層の最上位ノードです）。これらの制約は、サイクルまたは「ループ」がないこと（ノードが自分の祖先になることはできない）と、各子を自分のサブツリーのルートノードのように扱うことができることを意味し、再帰はツリーのトラバーサルに役立つ手法になります。線形データ構造とは対照的に、多くのツリーは、隣接するノード（対象ノードの親ノードと子ノード（存在する場合））間の関係を 1 つの直線（隣接する 2 つのノード間のエッジまたはリンクと呼ばれる）で表すことはできません。

二分木はよく使用されるタイプで、各親の子の数が最大 2 に制限されます。子の順序が指定されている場合、このデータ構造はグラフ理論の順序付き木に対応します。値または他のデータへのポインタは、木内のすべてのノードに関連付けられる場合もあれば、子ノードを持たない リーフ ノードにのみ関連付けられる場合もあります。

抽象データ型(ADT) は、子へのポインタを持つ親のリスト、親へのポインタを持つ子のリスト、ノードのリストと親子関係の別のリスト (特定の種類の隣接リスト) など、さまざまな方法で表現できます。パフォーマンスのためにインデックスや祖先リストを使用するなど、表現がより複雑になる場合もあります。

コンピューティングで使用されるツリーは、グラフ理論のツリー、集合論のツリー、記述集合論のツリーなどの数学的構成と似ていますが、異なる場合があります。

ツリーは、次のようなアプリケーションで階層データを表現または操作するためによく使用されます。

• 以下のファイルシステム:
  • サブディレクトリとファイルを整理するために使用されるディレクトリ構造(シンボリック リンクは、同じファイルまたはディレクトリへの複数のハード リンクと同様に、非ツリー グラフを作成します)
  • ストレージデバイス上のデータブロックを割り当ててリンクするために使用されるメカニズム
• クラス階層または「継承ツリー」は、オブジェクト指向プログラミングにおけるクラス間の関係を示します。多重継承では、ツリー以外のグラフが生成されます。
• コンピュータ言語の抽象構文木
• 自然言語処理:
  • 解析木
  • 生成文法による発話のモデル化
  • 会話を生成するためのダイアログツリー
• XMLおよびHTMLドキュメントのドキュメント オブジェクト モデル(「DOM ツリー」)
• 検索ツリーは、ツリーのトラバーサルを介して効率的な検索アルゴリズムを可能にする方法でデータを保存します。
  • 二分探索木は二分木の一種である
• ソートされたデータのリストを表現する
• コンピューター生成画像:
  • 空間分割（バイナリ空間分割を含む）
  • デジタル合成
• 銀河をシミュレートするために使用されたバーンズハットツリーの保存
• ヒープの実装
• ネストされたセットコレクション
• デューイ十進分類法などの階層的な分類法で、セクションごとに詳細度が増します。
• 階層的時間記憶
• 遺伝的プログラミング
• 階層的クラスタリング

ツリーは、次のようなさまざまな数学的構造を表現したり操作したりするために使用できます。

• 複数のパスで使用される各グラフノードに対してツリー内に複数のノードを作成することにより、任意のノードとエッジのグラフ（マルチグラフを含む）を通過するパス
• あらゆる数学的階層

ツリー構造は、次のようなものの間の関係をマッピングするためによく使用されます。

• 分解図で視覚化できるコンポーネントとサブコンポーネント
• サブルーチン呼び出しは、プログラム内のどのサブルーチンが他のサブルーチンを非再帰的に呼び出すかを識別するために使用されます。
• 進化による種間の DNA の継承、ソフトウェア プロジェクトによるソース コード (例: Linux ディストリビューションのタイムライン)、さまざまな種類の自動車のデザインの継承など。
• 階層的名前空間の内容

JSONおよびYAMLドキュメントはツリーとして考えることができますが、通常はネストされたリストと辞書で表されます。

ノードは、データや他のノードへの接続（エッジまたはリンクと呼ばれることもある）を含む構造です。ツリー内の各ノードには、ツリー内でそのノードの下位にある0 個以上の子ノードがあります（慣例により、ツリーは子孫が下に向かうように描画されます）。子を持つノードは、子の親ノード（または上位ノード）と呼ばれます。最上位のルート ノードを除き、すべてのノードには親が 1 つだけあります。ノードには、親の親などの祖先ノードが多数存在する場合があります。同じ親を持つ子ノードは、 兄弟ノードと呼ばれます。通常、兄弟には順序があり、最初の兄弟は通常左側に描画されます。定義によっては、ツリーにノードがまったく存在しないことが許可されており、その場合は空 と呼ばれます。

内部ノード(インナー ノード、略してinode 、またはブランチ ノードとも呼ばれる) は、子ノードを持つツリーの任意のノードです。同様に、外部ノード(アウター ノード、リーフ ノード、またはターミナル ノードとも呼ばれる) は、子ノードを持たない任意のノードです。

ノードの高さは、そのノードからリーフへの最長の下向きのパスの長さです。ルートの高さは、ツリーの高さです。ノードの深さは、そのルートへのパス (つまり、ルート パス) の長さです。したがって、ルート ノードの深さは 0、リーフ ノードの高さは 0、ノードが 1 つだけのツリー (つまり、ルートとリーフの両方) の深さと高さは 0 です。慣例的に、空のツリー (ノードがないツリー (許可されている場合)) の高さは -1 です。

ルート以外のノードはそれぞれ、そのノードとその子孫すべてを含むサブツリーのルートノードとして扱うことができる。^{[a] [2]}

木に関して使用されるその他の用語:

近所の人

親か子か。

祖先

子から親への繰り返し処理によって到達可能なノード。

子孫

親から子へと繰り返し進むことで到達可能なノード。サブ子とも呼ばれます。

程度

特定のノードの子の数。定義により、リーフの次数は 0 です。

木の度合い

ツリーの次数とは、ツリー内のノードの最大次数です。

距離

2 つのノード間の最短パスに沿ったエッジの数。

レベル

ノードのレベルとは、そのノードとルートノードの間の一意のパスに沿ったエッジの数です。^[3]これは深さと同じです。

幅

レベル内のノードの数。

幅

葉の数。

森

1 つ以上の互いに素なツリーのセット。

整列した木

各頂点の子に対して順序が指定されたルート付きツリー。

木の大きさ

ツリー内のノードの数。

• すべての項目を列挙する
• ツリーのセクションを列挙する
• アイテムの検索
• ツリー上の特定の位置に新しいアイテムを追加する
• アイテムの削除
• 剪定：木の一部を切り落とす
• 接ぎ木: 木にセクション全体を追加する
• 任意のノードのルートを見つける
• 2つのノードの最下位共通祖先を見つける

親と子の間の接続によってツリーの項目をステップスルーすることをツリーのウォーキングと呼び、そのアクションをツリーのウォークと呼びます。多くの場合、ポインタが特定のノードに到達したときに操作が実行されます。各親ノードをその子より先にトラバースするウォークを事前順序ウォークと呼びます。子をそれぞれの親より先にトラバースするウォークを事後順序ウォークと呼びます。ノードの左サブツリー、次にノード自体、最後に右サブツリーの順にトラバースするウォークを順序通りのトラバーサルと呼びます。(この最後のシナリオは、正確に 2 つのサブツリー、左サブツリーと右サブツリーを指し、特にバイナリ ツリーを想定しています。)レベル順序ウォークは、ツリー全体に対して実質的に幅優先検索を実行します。ノードはレベルごとに走査され、最初にルート ノードが走査され、次にその直接の子ノードとその兄弟ノード、さらにその孫ノードとその兄弟ノードというように、ツリー内のすべてのノードが走査されるまで続けられます。

ツリーを表現する方法は多種多様です。作業メモリでは、ノードは通常、子、親、またはその両方へのポインタと、関連データを含む動的に割り当てられたレコードです。固定サイズの場合、ノードはリストに格納されることがあります。ノードとノード間の関係は、別の特殊なタイプの隣接リストに格納されることがあります。リレーショナル データベースでは、ノードは通常、親と子の間のポインタを容易にするインデックス付きの行 ID を持つテーブル行として表現されます。

ノードは配列内の項目として格納することもでき、ノード間の関係は配列内の位置によって決まります (バイナリ ヒープの場合など)。

バイナリツリーは、リストのリストとして実装できます。リストの先頭 (最初の項の値) は左の子 (サブツリー) で、末尾 (2 番目以降の項のリスト) は右の子 (サブツリー) です。これは、Lisp S 式のように値を許可するように変更することもできます。この場合、先頭 (最初の項の値) はノードの値、末尾の先頭 (2 番目の項の値) は左の子、末尾の末尾 (3 番目以降の項のリスト) は右の子になります。

順序付き木は、例えば自然数などの有限シーケンスによって自然にエンコードすることができます。^[4]

抽象データ型として、何らかの型Eの値を持つ抽象ツリー型T は、抽象フォレスト型F (ツリーのリスト) を使用して、次の関数によって定義されます。

値: T → E

子供: T → F

ゼロ: () → F

ノード: E × F → T

公理は次の通りです:

値(ノード( e , f )) = e

子(ノード( e , f )) = f

型理論の観点から見ると、ツリーは、コンストラクタnil (空のフォレスト) とnode (指定された値と子を持つルート ノードを持つツリー) によって定義される帰納的型です。

全体として見ると、ツリー データ構造は順序付けられたツリーであり、通常は各ノードに値が関連付けられています。具体的には、次のようになります (空でないことが要求される場合)。

• 「根から離れる」方向を持つ根付いた木（より狭い用語は「樹枝状構造」）は、次のことを意味します。
  • 有向グラフ、​
  • 基礎となる無向グラフが木（任意の2つの頂点が1つの単純なパスで接続されている）であるもの
  • 区別されたルート（1つの頂点がルートとして指定される）を持つ
  • これはエッジの方向を決定します (矢印はルートから離れる方向を指します。エッジが与えられた場合、エッジが指すノードは親と呼ばれ、エッジが指すノードは子と呼ばれます)。また、次のものも決定します。
• 与えられたノードの子ノードの順序付け、および
• 各ノードにおける値（何らかのデータ型）。

多くの場合、ツリーには固定された（より正確には、制限された）分岐係数（出次数）があり、特に常に 2 つの子ノード（空の可能性があり、したがって最大2 つの空でない子ノード）があるため、「バイナリ ツリー」になります。

空の木を許可すると、定義が単純化されるものもあれば、より複雑になるものもあります。ルート付き木は空であってはならないため、空の木が許可されている場合、上記の定義は「空の木、またはルート付き木で、...」になります。一方、空の木は固定分岐係数の定義を単純化します。空の木が許可されている場合、バイナリ ツリーは、すべてのノードに 2 つの子があり、それぞれがツリー (空の場合もある) であるツリーです。

• 分散ツリー検索
• カテゴリ: ツリー (データ構造) (計算ツリーの種類のカタログ)

• ドナルド・クヌース。 『コンピュータプログラミングの技法：基礎アルゴリズム』、第3版。Addison-Wesley、1997年。ISBN 0-201-89683-4。セクション2.3：ツリー、pp. 308–423。 
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション 10.4: ルート付きツリーの表現、pp. 214–217。第 12 章から第 14 章 (二分探索木、赤黒木、データ構造の拡張)、pp. 253–320 。 

ウィキメディア・コモンズには、ツリー構造に関連するメディアがあります。

• アルゴリズムとデータ構造の辞書からの説明