このソートされていないツリーは、一意ではない値（例えば、値2が単一のノードではなく複数のノードに存在する）を持ち、非バイナリツリーです（バイナリツリーでは、親ノードごとに最大2つの子ノードしか存在しません）。最上位のルートノード（ここでは値2）は、ツリー階層の最上位であるため、親ノードがありません。

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

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

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

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

用語

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

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

ノードの高さは、そのノードから葉への最長のパスの長さです。ルートの高さは、ツリーの高さです。ノードの深さは、そのルートへのパス（つまり、ルートパス）の長さです。したがって、ルートノードの深さは0、葉ノードの高さは0です。また、1つのノード（つまり、ルートと葉の両方）のみを持つツリーは、深さと高さが0です。慣例的に、空のツリー（ノードが存在しないツリー（そのようなノードが存在する場合））の高さは-1です。

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

木に関連するその他の用語:

近所の人
親か子か。
祖先
子から親への繰り返し進行によって到達可能なノード。
子孫
親から子へと繰り返し進むことで到達可能なノード。子ノードとも呼ばれます。
程度
特定のノードの子ノードの数。定義により、リーフノードの次数は0です。
木の度合い
ツリーの次数とは、ツリー内のノードの最大次数です。
距離
2 つのノード間の最短パスに沿ったエッジの数。
レベル
ノードのレベルとは、そのノードとルートノード間の一意のパスに沿ったエッジの数です。[4]これは深さと同じです。
幅
レベル内のノードの数。
幅
葉の数。
完全なツリー
最後のレベルを除くすべてのレベルが埋められたツリー。
森
1 つ以上の分離したツリーのセット。
順序付けられた木
各頂点の子に対して順序が指定されたルート付きツリー。
木の大きさ
ツリー内のノードの数。

一般的な操作

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

トラバーサルと検索方法

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

表現

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

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

二分木はリストのリストとして実装できます。リストの先頭（最初の項の値）は左の子（サブツリー）、末尾（2番目以降の項のリスト）は右の子（サブツリー）です。これは、LispのS式のように、値を持つように変更することもできます。その場合、先頭（最初の項の値）はノードの値、末尾の先頭（2番目の項の値）は左の子、末尾の末尾（3番目以降の項のリスト）は右の子となります。

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

木と非木の例

型理論

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

値: T → E
子供: T → F
ゼロ: () → F
ノード: E × F → T

公理は次のとおりです。

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

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

数学用語

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

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

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

空木を許可すると、定義が単純化されるものと複雑化されるものがあります。根付き木は空であってはならないため、空木を許可する場合、上記の定義は「空木、または…となる根付き木」となります。一方、空木は固定分岐係数の定義を簡素化します。空木を許可する場合、二分木とは、すべてのノードがちょうど2つの子を持ち、それぞれの子が木（空の可能性もある）である木です。

アプリケーション

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

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

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

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

参照

注記

  1. ^ これはグラフ理論における部分木の正式な定義とは異なります。部分木とは木を構成する部分グラフのことで、必ずしもすべての子孫を含む必要はありません。例えば、ルートノード自体はグラフ理論の意味で部分木ですが、データ構造の意味で部分木ではありません（子孫が存在しない場合を除きます）。

参考文献

  1. ^ Subero, Armstrong (2020). 「3. ツリーデータ構造」.コードレスデータ構造とアルゴリズム. カリフォルニア州バークレー: Apress. doi :10.1007/978-1-4842-5725-8. ISBN 978-1-4842-5724-1親ノードは複数の子ノードを持つことができます。 …ただし、子ノードは複数の親を持つことはできません。子ノードが複数の親を持つ場合、それはグラフと呼ばれます。
  2. ^ 「抽象ツリー/ツリーADT | 抽象データ型 | ECE 250 | ウォータールー大学」ece.uwaterloo.ca . 2024年12月13日閲覧。
  3. ^ Weisstein, Eric W.「サブツリー」。MathWorld。
  4. ^ スザンナ・S・エップ（2010年8月）『離散数学とその応用』パシフィックグローブ、カリフォルニア州：ブルックス／コール出版、p.694、ISBN 978-0-495-39132-6。
  5. ^ L. アファナシエフ; P.ブラックバーン。 I. ディミトリウ; B. ガイフ; E. ゴリス; M. マルクス; M. デ ライケ (2005)。 「順序付きツリーの PDL」(PDF)。応用非古典論理学のジャーナル。15 (2): 115–135 .土井:10.3166/jancl.15.115-135。S2CID  1979330。
  6. ^ レビン、オスカー（2018年12月31日）『離散数学：オープン入門』（第3版）Amazon Digital Services LLC - Kdp. 247ページ。ISBN 978-1792901690。

さらに読む

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