Loading article…
コンピュータサイエンスでは、ツリーは、接続されたノードの集合を持つ階層的なツリー構造を表す、広く使用されている抽象データ型です。ツリー内の各ノードは、（ツリーの種類に応じて）多くの子に接続できますが、正確に 1 つの親に接続する必要があります[ 1 ] [ 2 ]。ただし、ルートノードは親を持ちません（つまり、ルートノードはツリー階層の最上位ノードです）。これらの制約により、サイクルや「ループ」（どのノードも自身の祖先になることはできません）は存在せず、また、各子は自身のサブツリーのルートノードのように扱うことができるため、再帰はツリー走査に役立つ手法となります。線形データ構造とは対照的に、多くのツリーは、隣接するノード間の関係（考慮対象のノードの親ノードと子ノードが存在する場合）を単一の直線（隣接する 2 つのノード間のエッジまたはリンクと呼ばれます）で表すことはできません。
二分木はよく使われるデータ構造で、各親ノードの子ノードの数は最大でも2つに制限されます。子ノードの順序が指定されている場合、このデータ構造はグラフ理論における順序付き木に対応します。値または他のデータへのポインタは、木のすべてのノードに関連付けられる場合もあれば、子ノードを持たない葉ノードのみに関連付けられる場合もあります。
抽象データ型（ADT）は、親ノードと子ノードへのポインタのリスト、子ノードと親ノードへのポインタのリスト、ノードのリストと親子関係のリスト（特定の種類の隣接リスト）など、さまざまな方法で表現できます。パフォーマンス向上のためにインデックスや祖先リストを使用するなど、より複雑な表現方法もあります。
コンピューティングで使用されるツリーは、グラフ理論におけるツリー、集合論におけるツリー、記述集合論におけるツリーといった数学的な構成物と似ているが、異なる場合もある。
ノードは、データと他のノードへの接続（エッジまたはリンクと呼ばれることもあります）を含む構造です。ツリー内の各ノードには、0 個以上の子ノードがあり、子ノードはツリー内でそのノードの下に位置します（慣例として、ツリーは子孫が下に向かって描画されます）。子を持つノードは、その子の親ノード（または上位ノード）と呼ばれます。すべてのノードは、親を 1 つだけ持ちますが、最上位のルート ノードには親がありません。ノードは、親の親など、複数の祖先ノードを持つ場合があります。同じ親を持つ子ノードは兄弟ノードです。通常、兄弟には順序があり、慣例として最初の兄弟が左側に描画されます。定義によっては、ツリーにノードがまったくない場合もあり、その場合は空のツリーと呼ばれます。
内部ノード（インナーノード、略してinode、またはブランチノードとも呼ばれる）とは、子ノードを持つツリーのノードのことです。同様に、外部ノード（アウターノード、リーフノード、またはターミナルノードとも呼ばれる）とは、子ノードを持たないノードのことです。
ノードの高さは、そのノードから葉ノードまでの最長下方パスの長さです。ルートの高さは、ツリーの高さです。ノードの深さは、そのルートまでのパスの長さ（つまり、ルートパス）です。したがって、ルートノードの深さはゼロ、葉ノードの高さはゼロ、ノードが1つしかないツリー（つまり、ルートと葉の両方があるツリー）の深さと高さはゼロです。慣例として、空のツリー（ノードがまったくないツリー、そのようなツリーが許容される場合）の高さは-1です。
各非ルートノードは、そのノードとそのすべての子孫を含むサブツリーのルートノードとして扱うことができます。 [ a ] [ 3 ]
樹木に関連するその他の用語：
親と子の間の接続を介してツリーの項目を順にたどることをツリーのウォーキングといい、その動作をツリーのウォーキングといいます。多くの場合、ポインタが特定のノードに到達したときに操作が実行されます。各親ノードが子ノードより先にたどられるウォーキングを前順ウォーキング、子ノードがそれぞれの親ノードより先にたどられるウォーキングを後順ウォーキング、ノードの左サブツリー、次にノード自体、最後に右サブツリーの順にたどられるウォーキングを順方向トラバーサルといいます。（この最後のシナリオは、左サブツリーと右サブツリーのちょうど 2 つのサブツリーを参照しており、特に二分木を想定しています。）レベル順ウォーキングは、実質的にツリー全体に対して幅優先探索を実行します。ノードはレベルごとに走査され、最初にルートノードが訪問され、次にその直接の子ノードとその兄弟ノード、次にその孫ノードとその兄弟ノード、といった具合に、ツリー内のすべてのノードが走査されるまで続きます。
ツリー構造を表現する方法は数多くあります。ワーキングメモリでは、ノードは通常、子ノード、親ノード、またはその両方へのポインタ、および関連データを含む動的に割り当てられるレコードです。ノードのサイズが固定されている場合は、リストに格納されることもあります。ノードとノード間の関係は、別の特殊な隣接リストに格納される場合もあります。リレーショナルデータベースでは、ノードは通常、テーブルの行として表現され、インデックス付きの行IDによって親ノードと子ノード間のポインタが管理されます。
ノードは配列の項目として格納することもでき、それらの間の関係は配列内の位置によって決定されます（バイナリヒープと同様）。
二分木はリストのリストとして実装できます。リストの先頭（最初の項の値）は左の子（部分木）であり、末尾（2番目以降の項のリスト）は右の子（部分木）です。LispのS式のように、値も扱えるように変更することもできます。この場合、先頭（最初の項の値）はノードの値であり、末尾の先頭（2番目の項の値）は左の子、末尾の末尾（3番目以降の項のリスト）は右の子となります。
順序付き木は、例えば自然数などの有限シーケンスによって自然に符号化することができる。[ 5 ]
抽象データ型として、抽象ツリー型T（値を持つ型E）は、抽象フォレスト型F（ツリーのリスト）を用いて、以下の関数によって定義されます。
公理は以下のとおりです。
型理論の観点から言えば、ツリーは、nil（空の森）とnode（特定の値を持つルートノードと子ノードを持つツリー）というコンストラクタによって定義される帰納型です。
ツリーデータ構造は全体として見ると、順序付けられたツリーであり、一般的には各ノードに値が付加されています。具体的には、（空でないことが求められる場合）次のようになります。
多くの場合、木構造は固定された（より正確には、境界のある）分岐係数（出次数）を持ち、特に常に2つの子ノード（空の場合もあるため、最大で2つの空でない子ノード）を持つため、「二分木」と呼ばれます。
空のツリーを許容すると、定義が単純になるものと複雑になるものがあります。ルート付きツリーは空であってはならないため、空のツリーが許容される場合、上記の定義は「空のツリー、または...のようなルート付きツリー」となります。一方、空のツリーは固定分岐係数の定義を簡素化します。空のツリーが許容される場合、二分木は、すべてのノードがちょうど2つの子を持ち、それぞれの子がツリー（空の場合もある）であるようなツリーです。
ツリーは、以下のようなアプリケーションにおいて、階層的なデータを表現または操作するためによく使用されます。
ツリーは、次のようなさまざまな数学的構造を表現したり操作したりするために使用できます。
ツリー構造は、次のようなもの間の関係をマッピングするためによく使用されます。
しかし、子ノードは複数の親ノードを持つことはできません。子ノードが複数の親ノードを持つ場合、それはグラフと呼ばれます。