ツリー(データ構造)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
一般的な、つまり非バイナリで、ソートされていない、一部のラベルが複製された、ツリーの任意の図。この図では、7というラベルの付いたノードには2、10、6というラベルの付いた3つの子があり、2というラベルの付いた1つの親があります。上部のルートノードには親がありません。

コンピュータサイエンスツリーが広く用いられている抽象データ型階層シミュレートするツリー構造を有するルート値と子供のサブツリーと、親ノード連結の集合として表される、ノード

ツリーデータ構造は、ノードのコレクションとして再帰的に定義できます。各ノードは、値とノードへの参照のリストで構成されるデータ構造です。ツリーの先頭は「ルートノード」であり、参照ノードは「子」です。重複する参照はなく、ルートを指すものもありません。

または、ツリーを全体として(グローバルに)順序付けられたツリーとして抽象的に定義し、各ノードに値を割り当てることもできます。これらの両方の観点が役立ちます。ツリーは全体として数学的に分析できますが、実際にデータ構造として表される場合、通常はノードごとに個別に表され、処理されます(ノードのセットおよびノー​​ド間のエッジの隣接リストとしてではありません)。たとえば有向グラフを表す場合があるため)。たとえば、ツリー全体を見ると、特定のノードの「親ノード」について話すことができますが、一般に、データ構造として、特定のノードにはその子のリストのみが含まれ、参照は含まれません。その親(もしあれば)に。

一般的な使用法

用語

ノードが値または状態を含む、または(独自のツリーであってもよい)別のデータ構造を表すことができる構造です。ツリー内の各ノードには、ツリー内のその下にある0個以上の子ノードがあります(慣例により、ツリーは下向きに成長して描画されます)。子を持つノードは、子の親ノード(または上位ノードと呼ばれます。ノードには最大で1つの親がありますが、親の親など、多くの祖先ノードが存在する可能性があります。同じ親を持つ子ノード兄弟ノードです。

内部ノード(としても知られている内部ノードiノード短いため、またはブランチノードは)子ノードを有するツリーの任意のノードです。同様に、外部ノード外部ノードリーフノード、またはターミナルノードとも呼ばれます)は、子ノードを持たないノードです。

ツリーの最上位ノードはルートノードと呼ばれます。定義に応じて、ツリーにはルートノードが必要な場合(この場合、すべてのツリーが空ではない)、または空にすることが許可されている場合があります。この場合、ツリーには必ずしもルートノードがありません。最上位ノードであるため、ルートノードには親がありません。これは、ツリー上のアルゴリズムが開始するノードです。データ構造として、親から子にのみ渡すことができるためです。一部のアルゴリズム(注文後の深さ優先探索など)はルートから始まりますが、最初にリーフノードにアクセスし(リーフノードの値にアクセス)、最後にルートにアクセスする(つまり、最初にの子にアクセスする)ことに注意してください。ルートですが、最後にルートの値にのみアクセスします)。他のすべてのノードは、エッジまたはリンクをたどることによってそこから到達できます。 (正式な定義では、このような各パスも一意です。)ダイアグラムでは、ルートノードは通常上部に描画されます。ヒープなどの一部のツリーでは、ルートノードに特別なプロパティがあります。ツリー内のすべてのノードは、そのノードをルートとするサブツリーのルートノードと見なすことができます。

ノード高さは、そのノードからリーフへの最長の下向きパスの長さです。根の高さは木の高さです。ノード深さは、そのルートまでのパスの長さ(つまり、そのルートパス)です。これは、さまざまな自己平衡ツリー、特にAVLツリーの操作で一般的に必要になります。ルートノードの深さはゼロ、リーフノードの高さはゼロ、ノードが1つしかないツリー(したがって、ルートとリーフの両方)の深さと高さはゼロです。従来、空のツリー(ノードが許可されている場合はノードのないツリー)の高さは-1です。

サブツリー木のTは、ノードからなるツリーであり、Tおよびその子孫のすべてのT[a] [1]したがって、ノードはサブツリーに対応します(各ノードはそれ自体のサブツリーとそのすべての子孫に対応します)–ルートノードに対応するサブツリーはツリー全体であり、各ノードはそれが決定するサブツリーのルートノードです; 他のノードに対応するサブツリーは、適切なサブツリーと呼ばれます適切なサブセットと同様に)。

木で使用される他の用語:

近所の人
親または子。
祖先
子から親への繰り返しの進行によって到達可能なノード。
子孫
親から子への繰り返しの進行によって到達可能なノード。サブチャイルドとも呼ばれます
ブランチノード
内部ノード
少なくとも1つの子を持つノード。
程度
特定のノードについて、その子の数。葉は必然的に次数がゼロになります。
木の次数
ツリーの次数は、ツリー内のノードの最大次数です。
距離
2つのノード間の最短パスに沿ったエッジの数。
レベル
ノードのレベルは、ノードとルートノードの間の一意のパスに沿ったエッジの数です。[2]
レベル内のノードの数。
葉の数。
一連のN ≥0互いに素木。
注文したツリー
各頂点の子に順序が指定されているルートツリー。
木のサイズ
ツリー内のノードの数。

予備定義

ツリーではありませんA→BとC→D→Eの2つの接続されていない部分。複数のルートがあります。
ツリーではありません:無向サイクル1-2-4-3。4には複数の親(インバウンドエッジ)があります。
ツリーではありません:サイクルB→C→E→D→B。Bには複数の親(インバウンドエッジ)があります。
ツリーではありません:サイクルA→A。Aはルートですが、親もあります。
各線形リストは自明なツリーです

ツリーは、線形データ構造である配列、リンクリスト、スタック、およびキューと比較して、非線形データ構造です。ツリーはノードなしで空にすることができます。または、ツリーはルートと呼ばれる1つのノードと、0個または1つ以上のサブツリーで構成される構造です。

木を描く

木はしばしば平面に描かれます。順序付けされたツリーは、平面内で本質的に一意に表すことができるため次のように平面ツリーと呼ばれます。従来の順序を固定し(たとえば、反時計回り)、子ノードをその順序で配置する場合(最初の入力親エッジ、次に最初の子エッジなど)、これにより、アンビエントイソトピーまではユニークな、平面へのツリーの埋め込みが生成されます。逆に、そのような埋め込みは子ノードの順序を決定します。

ルートを一番上に配置し(家系図のように子の上の親)、ルートから指定された距離にあるすべてのノード(エッジの数:ツリーの「レベル」)を指定された場所に配置する場合水平線、1つは木の標準的な図面を取得します。二分木が与えられると、最初の子は左側(「左ノード」)にあり、2番目の子は右側(「右ノード」)にあります。

一般的な操作

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

トラバーサルと検索方法

親子のつながりを利用して、木のアイテムをステップスルーすることを「木の散歩」と呼び、アクションは「木の散歩」です。多くの場合、ポインタが特定のノードに到達したときに操作が実行されることがあります。各親ノードが子の前にトラバースされるウォークは、プレオーダーウォークと呼ばれます。それぞれの親がトラバースされる前に子供がトラバースされるウォークは、ポストオーダーウォークと呼ばれます。ノードの左側のサブツリー、ノード自体、最後に右側のサブツリーがトラバースされるウォークは、インオーダートラバーサルと呼ばれます。 (この最後のシナリオは、左のサブツリーと右のサブツリーの2つのサブツリーを正確に参照しており、具体的には二分木。)レベル順ウォークは、ツリー全体に対して幅優先探索を効果的に実行します。ツリー内のすべてのノードがトラバースされるまで、ノードはレベルごとにトラバースされます。ルートノードが最初に訪問され、次に直接の子ノードとその兄弟、次に孫ノードとその兄弟などが訪問されます。

表現

木を表現する方法はたくさんあります。一般的な表現は、ノードを、子、親、またはその両方へのポインタを持つ動的に割り当てられたレコードとして、または配列内のアイテムとして表し、ノード間の関係は配列内の位置によって決定されます(たとえば、バイナリヒープ)。

実際、バイナリツリーはリストのリスト(値がリストであるリスト)として実装できます。リストの先頭(最初の項の値)は左の子(サブツリー)であり、末尾(リスト)は2番目以降の用語の)は正しい子(サブツリー)です。これは、Lisp S式のように、値も許可するように変更できます。ここで、head(第1項の値)はノードの値であり、テールの先頭(第2項の値)は左の子であり、テールのテール(3番目以降の用語のリスト)は正しい子です。

一般に、ツリー内のノードにはその親へのポインターがありませんが、この情報を含める(データ構造を拡張して親へのポインターも含める)か、個別に格納することができます。または、スレッド化されたバイナリツリーのように、上向きのリンクを子ノードデータに含めることもできます

一般化

有向グラフ

(子ノードへの)エッジが参照と見なされる場合、ツリーはダイグラフの特殊なケースであり、ツリーデータ構造は、ノードが最大で1つの親を持つ可能性のある制約を削除することにより、有向グラフを表すように一般化できます。また、サイクルは許可されていません。エッジは依然として抽象的にノードのペアと見なされますが、という用語は通常、異なる用語(たとえば、ソースターゲット)に置き換えられます。さまざまな実装戦略存在する:「子のリスト」が参照のリストであると仮定すると、ダイグラフはツリーと同じローカルデータ構造(値と子のリストを持つノード)で表すことができますまたは、隣接リストなどの構造でグローバルに表すことができます

グラフ理論ツリーが接続非環式グラフ。特に明記しない限り、グラフ理論では、ツリーとグラフは無向であると見なされます。このようなツリーとデータ構造などのツリーの間には、1対1の対応はありません。任意の無向ツリーを取得し、その頂点の1つをルートとして任意に選択し、それらをルートノードから遠ざけることによってすべてのエッジを有向にし、樹木を生成し、すべてのノードに順序を割り当てることができます。結果はツリーデータ構造に対応します。別のルートまたは別の順序を選択すると、別のルートが生成されます。

ツリー内のノードが与えられると、その子は順序付けられたフォレストを定義します(すべての子によって与えられたサブツリーの結合、または同等にノード自体によって与えられたサブツリーを取得してルートを消去します)。サブツリーが(深さ優先探索のように)再帰的に自然であるように、フォレストは(幅優先探索のように)コア再帰に対して自然です

相互再帰を介して、フォレストはツリーのリスト(ルートノードで表される)として定義できます。ここで、(ツリーの)ノードは値とフォレスト(その子)で構成されます。

f:[n [1]、...、n [k]]
n:vf

データ型とデータ構造

リストリンクリストの違いに似た、抽象データ型と具体的なデータ構造としてのツリーには違いがあります

データ型として、ツリーには値と子があり、子自体がツリーです。ツリーの値と子は、ルートノードの値とルートノードの子のサブツリーとして解釈されます。有限の木を許可するには、子のリストを空にするか(この場合、木は空でない必要があり、代わりに「空の木」はゼロの木の森で表されます)、または木に次のことを許可する必要があります。空にする必要があります。この場合、子のリストは固定サイズ(分岐係数、特に2または「バイナリ」)にすることができます。

データ構造として、リンクされたツリーはノードのグループであり、各ノードには値と他のノード(その子)への参照のリストがあります2つの「下向き」参照が同じノードを指さないという要件もあります。実際には、ツリー内のノードには通常、次/前の参照、親ノードへの参照など、他のデータも含まれます。

リンクされたツリーデータ構造でツリーへ参照が使用されているため、ツリーはルートノードへの参照によって表されていると想定して暗黙的に説明されることがよくあります。これは、実際に実装される方法であることが多いためです。たとえば、空のツリーではなく、null参照がある場合があります。ツリーは常に空ではありませんが、ツリーへの参照はnullである可能性があります。

再帰的

再帰的に、データ型として、ツリーは、その子のサブツリーであるツリーのリスト(おそらく空のリスト)とともに、(あるデータ型の、場合によっては空の)値として定義されます。象徴的に:

t:v [t [1]、...、t [k]]

(ツリーtは、値vと他のツリーのリストで構成されます。)

よりエレガントに、ツリーが最も基本的な例の1つである相互再帰を介して、ツリーはフォレスト(ツリーのリスト)の観点から定義できます。ここで、ツリーは値とフォレスト(そのサブツリー)で構成されます。子供達):

f:[t [1]、...、t [k]]
t:vf

この定義は値に関するものであり、関数型言語で適切であることに注意してください参照透過性を前提としています)。異なるツリーは単なる値のリストであるため、接続はありません。

データ構造として、ツリーはノード(ルート)として定義されます。ノード自体は、他のノードへの参照のリスト(リストは空、参照はnull)とともに、値(あるデータ型、場合によっては空)で構成されます。 ); 象徴的に:

n:v [&n [1]、...、&n [k]]

(ノードnは、値vと他のノードへの参照のリストで構成されます。)

このデータ構造は有向グラフを定義し[b]、それがツリーであるためには、そのグローバル構造(そのトポロジー)に条件を追加する必要があります。つまり、最大で1つの参照が任意のノードを指すことができます(ノードは最大で単一の親)であり、ツリー内のノードがルートを指していません。実際、すべてのノード(ルートを除く)には親が1つだけ存在する必要があり、ルートには親が存在しない必要があります。

実際、ノードのリストと、各ノードの子への参照のリストが与えられた場合、この構造がツリーであるかどうかは、そのグローバル構造を分析せずに判断できず、以下に定義するように、実際にはトポロジ的にツリーであることがわかります。

型理論

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

値:TE
子供:TF
nil :()→ F
ノード:E × FT

公理で:

value(node(ef))= e
children(node(ef))= f

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

数学用語

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

  • 根ざした木「離れルートから」方向とは、(より狭い用語は、「ある樹枝意味します、」):
    • 有向グラフ
    • その基礎となる無向グラフツリーです(任意の2つの頂点が1つの単純なパスで接続されています)。
    • 区別されたルート(1つの頂点がルートとして指定されます)を使用して、
    • これはエッジの方向を決定します(矢印はルートから離れる方向を指します。エッジが与えられると、エッジが指すノード呼ばれ、エッジが指すノードはと呼ばれます)、

一緒に:

  • 特定のノードの子ノードでの順序付け、および
  • 各ノードの(あるデータ型の)値。

多くの場合、ツリーには固定された(より適切には有界の)分岐係数outdegree)があり、特に常に2つの子ノード(おそらく空であるため、最大で2つの空でない子ノード)、つまり「バイナリツリー」があります。

空のツリーを許可すると、一部の定義がより単純になり、さらに複雑になります。ルートツリーは空でない必要があるため、空のツリーが許可されている場合、上記の定義は代わりに「空のツリーまたはルートツリー...」になります。一方、空のツリーは、固定分岐係数の定義を簡素化します。空のツリーが許可されている場合、バイナリツリーは、すべてのノードに正確に2つの子があり、それぞれがツリー(おそらく空)であるようなツリーです。ツリーの操作の完全なセットには、fork操作が含まれている必要があります。

数学的定義

順序付けられていないツリー

数学的には、順序付けられていないツリー[3] または「代数ツリー」)[4]のように定義することができる代数構造 X、親)ここで、Xは、非空のキャリアセットされているノード親がオン関数でXれる割り当てます各ノードxその「親」ノード、parent(x。構造は、すべての空でない部分代数が同じ不動点を持たなければならないという条件に従います。すなわち、ユニークな「ルート」ノードが存在しなければならないR、例えばその親(R)= rであり、すべてのノードxについて、いくつかの反復アプリケーションparent(parent(⋯parent(x)⋯))rに等しくなります。

いくつかの同等の定義があります。

最も近い代替案として、親(rを未定義にすることにより、上記の全代数から得られる代数 X、親)として順序付けられていないツリーを定義できますすなわち、ルートrがその上に唯一のノードである関数が定義されていないと、すべてのノードのためのX、ルートは到達からXにおける有向グラフX、親)この定義は、実際には反樹枝状の定義と一致しています。TAoCPの本は、用語を使用しています 指向ツリー[5]

順序付けられていないツリーは構造であるX、≺)Xがセットされたノードある子対親のように、ノード間の関係:
(1)Xは空ではありません。
(2)Xは、弱くされた接続
(3)機能的です。
(4)満たすACC:NO無限配列が存在しないX 1X 2X 3 ≺⋯は

右側のボックスは、偏代数X、親)関係構造 X、≺)として説明しています。(1)をに置き換えた場合

  1. Xは正確に一つ含ま -最大ノード。

その後、条件(2)は冗長になります。

この定義を使用すると、リストされた条件の識別されたサブセットに対応する順序付けられていないツリーの一般化に専用の用語を提供できます。

順序付けられていないツリーのもう1つの同等の定義は、単一ルートであり、高さが最大でωである集合論的ツリー(「有限っぽい」ツリー)の定義です[6]つまり、代数的構造X、親)最上位要素rを持ち、すべての主動揺(別名主フィルター)が有限連鎖である半順序X、≤)同等です。正確には、集合論的定義は通常反対の順序を使用するため、集合論的ツリーについて話す必要があります。

X、親)X、≤)の間の対応は再帰的な推移閉包/縮小によって確立され、縮小によってルートサイクルのない「部分的な」バージョンが生成されます。

記述集合論(DST)でのツリーの定義は、有限シーケンス間の接頭辞次数として半順序X、≥)の表現を利用します。アップ判明において同型(の逆)DSTの木、これまで定義されたツリー構造との間に1対1の対応があります。

私たちは、への4つの同等の特性評価を参照することができます代数として木部分的代数などの木木半順序として、およびプレフィックス順序としてツリー。 5番目の同等の定義もありますこれは、接続された非巡回 ルートグラフであるグラフ理論のルートツリーの定義です。


(偏代数関数グラフとも呼ばれるX、親)としてのツリーの表現は親ポインターを使用したツリー構造の実装に直接続きます通常、ルートノードに親が定義されていない部分バージョンが使用されます。ただし、一部の実装またはモデルでは、parent(r)= rの循環性も確立されます。注目すべき例:

  • LinuxのVFS「ルートのdentryはそれ自体にポイントd_parentを持っています」。[7]
  • インスタンス化ツリーの概念[8] [9] [10]

オブジェクト指向プログラミングこの場合、ルートノードは最上位のメタクラスであり、それ自体の直接インスタンスである唯一のクラスです。

上記の定義は無限の木を認めていることに注意してくださいこれにより、遅延評価を介して一部の実装でサポートされる無限構造の記述が可能になります注目すべき例はRubyオブジェクトモデルから固有クラス無限後退です[11]このモデルでは、非末端オブジェクト間のリンクを介して確立されたツリーは無限であり、無限の分岐があります(「らせん」オブジェクトの単一の無限分岐-図を参照)。 superclass

兄弟セット

すべての順序付けられていないツリーX、親)には、ノードのセットX兄弟セットへの識別されたパーティションがありますparent(x)= parent(y)の場合2つの非ルートノードxyは同じ兄弟セットに属します。ルートノードrは、シングルトン兄弟セット{ r }を形成します。[c]兄弟セットのそれぞれが有限である場合、ツリーは局所的に有限または有限に分岐していると言われます

別個の兄弟の各ペアは比較できませんこれが、unorderedという単語が定義で使用されている理由です。このような用語は、すべての兄弟セットがシングルトンである場合、つまり、すべてのノードのセットXによって完全に順序付けられている(したがって、適切に順序付けられている場合、誤解を招く可能性があります。そのような場合、代わりに単一分岐ツリーについて話すことがあります

セット包含の使用

すべての半順序集合と同様に、木構造Xは、≤)で表すことができる封入順-によってセットシステムものでと一致する、誘導された封入順序。構造検討U、ℱ)のように、Uは非空集合であり、ℱは、サブセットの集合であるU、以下の(によって満たされることがネストされたセットのコレクションの定義):

  1. ∅∉ℱ(つまり、U、ℱ)ハイパーグラフです。)
  2. U ∈ℱ
  3. すべてのためのXYからXY ∈{∅、XY }。(つまり、層状のファミリーです。)[12]
  4. すべてのためにXから、有限個しか存在しYからようにXY

その場合、構造(ℱ、⊆)は、ルートがUに等しい順序付けられていないツリーになります。逆に、U、≤)が順序付けられていないツリーであり、が集合{↓ x | XU }のすべての主要な理想U、≤)次に、設定されたシステムU、ℱ)を満たす上記特性を。

セットの層流システムとしてのツリー(入れ子集合モデルからコピー

ツリー構造のセットシステムビューは、デフォルトのセマンティックモデルを提供します。最も一般的なケースの大部分では、ツリーデータ構造は包含階層を表しますこれは、ルートが一番上にある注文方向の正当化も提供します。ルートノードは他のどのノードよりも大きなコンテナです。注目すべき例:

根拠のある木

厳密な部分順序<十分に根拠のある関係である場合、順序付けられていないツリーX、≤)十分に根拠があります特に、すべての有限ツリーは十分な根拠があります。従属選択公理を仮定すると、ツリーには無限の分岐がない場合に限り、十分な根拠があります。

十分に根拠のあるツリーは、小さなツリーの非交和からツリーを形成することにより、再帰的定義できます。正確な定義のために、Xがノードのセットであると仮定します。半順序反射性使用してXのサブセット上の任意のツリーY、≤)をその半順序(≤)-X × Xのサブセットで識別することができます。セットすべての関係のは、R、そのフォームよく設立ツリーYRサブセット上でYXが段階的に定義されは、そのようℛ=⋃{ℛ I | は普通です}。序数 iが、聞かせてRをに属しI番目ステージI場合に限り、 Rは、に等しいです。

⋃ℱ∪((dom(⋃ℱ)∪{ x })×{ x })

ここℱは、の部分集合である{ℛの⋃ K | ℱの要素がペアごとにであり、xdom(⋃ℱ)に属さないノードであるようなk < i }。 (我々は、使用DOM(S示すために、ドメイン関連のSを。)最低の段階ことを確認0は、単一ノードツリー{(から成るXXので)}のみ空ℱが可能です。各段階で、(おそらく)新しい木Rが森をとることによって構築されます⋃ℱ下段のコンポーネントℱを使用⋃ℱの上に新しいルートx接続します。

樹高が最大でωであるのとは対照的に、十分に根拠のある樹木のランクは無制限です[13]展開」の特性を参照してください

再帰ペアの使用

コンピューティングでは、十分に根拠のあるツリーを定義する一般的な方法は、再帰的な順序対 Fx)を使用することです。ツリーは、「新しい」ノードxを持つフォレストFです。[14]F次に、ノードの対の互いに素なセットと木の可能性が空集合です。正確な定義については、強制の集合論的手法で使用される名前の作成と同様に進めます。ましょXはノードの集合とします。X上部構造、それぞれ木と森のセットT、およびマップを定義します。 ノード:T →℘(X各ツリー割り当てTようにノードの基礎となるセット。

X上の木 TT tは対でFXからℱ× XようにすべてのためのSF
X ∉ノード(複数可
X上の森 F ∈ℱ Fは、の部分集合であるTようにすべてのためのSTFST
ノード(S)∩ノード(T)=∅
(木のノード) Y ∈ノード(T T =(FX)∈ T
のいずれか、Y = X又はY ∈ノード(複数可、いくつかのためのSF

上記の条件での循環は、前のサブセクションのように、T、およびノードのそれぞれを段階に階層化することによって排除できます続いて、T上の「サブツリー」関係、ツリー間で定義された「即時サブツリー」関係の反射推移閉包として定義します。

Sトン Sπ 1T

ここで、π 1tはである投影Tの第1の座標上に、すなわち、それは森林であるFように、T =(FXいくつかについてのxX。その観察することができるTは、≤)であるmultitreeすべての場合:TT、主理想tが順に並べられ半順序としてよく設立木です。また、すべてのツリーのTT 、構造-ORDERその"ノード" (ノード(T)、≤ tはによって与えられるXT yの場合、森林が存在する場合にのみ、FG ∈ℱように双方FXGYtのサブツリーであり、Fx)≤(Gy

矢印を使用する

順序付けられていないツリーの一般化と同様に別の形式化は、ノードの親子ペアを具体化することによって取得できますこのような順序付けられた各ペアは、抽象的なエンティティ、つまり「矢印」と見なすことができます。これにより、マルチダイグラフ XAstが生成されます。ここで、Xはノードのセット、A矢印のセットstAからXまで関数で、各矢印にソースターゲットを割り当てます。、 それぞれ。構造には次の条件があります。

(1)Ast –1は、総代数としての順序付けられていないツリーです。
(2)tマップは、矢印とノードの間全単射です。

(1)では、合成記号○は左から右に解釈されます。この条件は、矢印[d]の逆連続性が完全な子から親へのマップであることを示しています。矢印の間のこの親マップをpと表記します。つまり、p = st −1です。次に、s = ptもあります。したがって、(1,2)を満たすマルチダイグラフは、sの代わりに親マップpを使用してXAptとして公理化することもできます。定義的な構成要素として。ルート矢印は必然的にループであることに注意してください。つまり、そのソースとターゲットが一致します。

デントリー構造

矢印ツリー:VFSのハードリンク構造

上記の構造の重要な一般化は、ターゲットマップtを多対1にすることによって確立されます。これは、(2)がに弱められることを意味します

(2 ')tマップは全射です–各ノードはいくつかの矢印のターゲットです。

条件(1)は、葉の矢印のみが同じターゲットを持つことが許可されていることを示していることに注意してください。つまりtp範囲制限すること単射です。

(1,2 ')を満たすマルチダイグラフは、「矢印ツリー」と呼ぶことができます。それらのツリー特性は、ノードではなく矢印に課されます。これらの構造は、ファイルシステムのハードリンク構造を反映しているため、LinuxVFSの最も重要な抽象化と見なすことができます。ノードはiノードと呼ばれ、矢印はデント(またはハードリンク)です。親マップとターゲットマップptは、それぞれdentryデータ構造のd_parentd_inodeフィールドで表されます。[15]各iノードには固定ファイルタイプが割り当てられており、そのディレクトリタイプは「設計された親」の特別な役割を果たします。

(a)ディレクトリiノードのみがハードリンクソースとして表示され、
(b)ディレクトリiノードを複数のハードリンクのターゲットとして表示することはできません。

ルートループの前半に破線のスタイルを使用することは、親マップと同様に、ルート矢印のソースが定義されていないソースマップ部分的なバージョンがあることを示しますこのバリアントは、さらに一般化するために使用されますmultidigraphでのパスの使用を参照してください

有向グラフでパスを使用する

セットメンバーシップの展開 すべてのセットのためのX、リレーショナル構造X ∪{ X }、∈)及びTC({ xは})、∈)の両方APGはあります。[apg 1]

折りたたまれたフォンノイマン序数5

(5、∈)折りたたまれた

展開されたフォンノイマン序数5

(5、∈)展開

5 =4∪{4} = TC({4})= {0,1,2,3,4 }は フォンノイマンの序数です。

順序付けられていないツリーは、アクセス可能な尖ったグラフの「展開」によって自然に発生します[16]

LET ℛ=(XRRである尖ったリレーショナル構造、すなわちように、Xはノードの集合であり、Rは、ノード間の関係(のサブセットであるX × X)、及びrは区別「ルート」ノードであります。さらに、アクセス可能であると仮定します。これは、XRの反射推移閉包の下{ r }のプレイメージ等しいことを意味し、そのような構造をアクセス可能な尖ったグラフまたはapgと呼びます。略して。[apg 2]次に、次のように別のapgℛ '=(X 'R 'r '展開導出できます。

  • X 'は、rの逆パスのセット、つまり、(a)pの連続するメンバーが逆にRに関連し、(b)最初のメンバーとなるようなノード(Xの要素)の空でない有限シーケンスpセットです。Pルートでrは
  • R「は、からのパスの間の関係であり、X」パスように、PQがであるR」 -関連場合にのみ、P = Q ⁎[ X ]いくつかのノードのためのX(すなわち、qが最大適切である接頭語P、「ポップ" p)、および
  • r 'は1要素シーケンス[ r ]です。

明らかに、構造X 'R 'は、「偏代数」バージョンでは順序付けられていないツリーです。R 'は、パスポップによってX 'の各非ルート要素をその親に関連付ける部分マップですルート要素は明らかに r 'です。さらに、次のプロパティが満たされます。

  • 木である場合に限り、その展開ℛ 'と同型です。[apg 3](特に、展開は同型を除いてべきです。)
  • 展開すると、十分な根拠が維持されます。Rが十分に根拠がある場合、R 'も同様です。
  • 展開するとランクが保持されます。Rが十分に根拠がある場合RR 'のランクは一致します。

ノート:

  1. ^ 集合メンバーシップ∈のような非環式関係は、最大で1つの可能なルートrのみがapgを形成することを許可します。その後、ルートは暗黙的に指定され、署名から除外できます。
  2. ^ Rマップの 間の一致を確立するために、提示された定義は逆のアクセシビリティを使用ます。rは任意のノードから到達可能です。このアプローチはnLabでも使用されていますメンバーシップグラフを参照してください P. Aczelによる元の定義では、すべてのノードはrから到達可能です(したがって、「preimage」の代わりに「image」という単語が適用されます)。
  3. ^ 順序付けされていないツリーの定義をapgsとして暗黙的に導入しました。reductXRが偏代数として順序付けられていないツリーである場合、apgℛ =(XRrツリーと呼びます。これは次のように解釈できます。すべてのノードは、正確に1つのパスでアクセスできます。

マルチダイグラフでパスを使用する

ファイルシステムのハードリンク構造の例に示されているように、コンピューティングの多くのデータ構造では、ノード間の複数のリンクが許可されています。したがって、データ構造間で順序付けられていないツリーの外観を適切に表示するには、アクセス可能なポインテッドグラフをマルチダイグラフ設定に一般化する必要があります。用語を単純化するために、「multidigraph」の確立された同義語である用語quiver使用します

アクセス可能な先の尖った矢筒

アクセ尖った矢筒(APQ):の一般APG multidigraphsへ。

アクセシブルな先の尖った矢筒または略してapqを構造として定義し ましょう

ℳ=(XAst

ここで、 XノードのセットA矢印のセットsAからXソースマップ)まで部分関数tAからXターゲットマップ)まで合計関数です。したがって、は「部分的なマルチダイグラフ」です。

構造には次の条件があります。

  1. 1「ルート」の矢印は、まさにそこにあるRソースが、Srを定義されていません。
  2. 各ノードのxX矢印ルートから始まる連続した矢印の有限のシーケンスを介して到達可能であるR

ターゲットマップtが矢印とノード間の全単射である場合、ツリーであると言われます展開、(2)で説明したシーケンスによって形成されます。これはアクセシビリティパスですパス代数を参照)。 apqとして、展開は次のように記述できます。ℳ '=(X 'A 's 't ' ここで、 X'はアクセシビリティパスのセット、 A 'X'と一致しs 'はパスポップと一致します。そして t 'X 'のアイデンティティです。apgsと同様に、展開はべき等であり、常にツリーになります。

下地APGは、構造体として得られる XRTR)) ここで、 R = {(T)、S))| A \ { R }}

上の図は、1 +14の矢印を持つapqの例を示しています。JavaScriptPythonの又はルビー、構造は、以下の(全く同じ)コードによって作成することができます。

r  =  {};  
r [ 1 ]  =  {};  r [ 2 ]  =  r [ 1 ];  r [ 3 ]  =  {};  r [ 4 ]  =  {};  
r [ 1 ] [ 5 ]     =  {};    r [ 1 ] [ 14 ]     =  r [ 1 ] [ 5 ]; 
r [ 3 ] [ 7 ]     =  {};    NS[ 3 ] [ 8 ]      =  r [ 3 ] [ 7 ];   r [ 3 ] [ 13 ]  =  {}; 
r [ 4 ] [ 9 ]     =  r [ 4 ];  r [ 4 ] [ 10 ]     =  r [ 4 ];      r [ 4 ] [ 11 ]  =  {}; 
r [ 3 ] [ 7 ] [ 6 ]  =  r[ 3 ];  r [ 3 ] [ 7 ] [ 12 ]  =  r [ 1 ] [ 5 ];

名前の使用

順序付けられていないツリーとその一般化は、ネーミングシステムの本質を形成しますネーミングシステムには、ファイルシステムと(ネストされた)連想配列の2つの顕著な例があります前のサブセクションのマルチダイグラフベースの構造は、両方のケースに匿名の抽象化を提供しました命名機能を取得するには、矢印に識別子として名前付ける必要があります名前はローカルで一意である必要があります。兄弟の矢印の各セット[e]内には、指定された名前でラベル付けされた矢印を最大1つまで含めることができます。

source name target
sa σa ta

これは構造として形式化できます

ℰ=(XΣAsσt

ここで、 XノードのセットΣ名前のセットA矢印のセットsAからXまで部分関数σAからΣまで部分関数tAから合計関数ですX。矢印aの場合、トリプルの構成要素sa)、σa)、ta))それぞれソース名前、およびターゲットです。

構造には次の条件があります。

  1. reduct XAstは、前に定義しようにアクセス可能な先の尖った矢筒(apq)です。
  2. 名前関数σは、ソースのないルート矢印に対してのみ定義されていません。
  3. 名前関数σは、すべての兄弟の矢印のセットへの制限に単射です。つまり、すべての非ルート矢印abについて、sa)= sbおよびσa)= σb)の場合、a = b

この構造は呼び出すことができ、ネストされた辞書命名APQ。コンピューティングでは、そのような構造は至る所にあります。上の表は、矢印が集合A ' = {(sa)、σa)、ta))|として「未修正」と見なすことができることを示していますA \ { R }}ソース名対象トリプル。これによりリレーショナルデータベースと見なすことができるリレーショナル構造XΣA '作成されます。テーブル。に下線を引き、主キーsourcename示します

構造は決定的と言い換えることができる標識された移行システムXは、「状態」の集合であり、Σは、「ラベル」の集合であり、A」は、 『標識された遷移』のセットです。(さらに、ルートノードr = ta rは「初期状態」であり、アクセシビリティ条件は、すべての状態が初期状態から到達可能であることを意味します。)

ネストされた辞書

ネストされた辞書

右の図は、前のサブセクションの例と同じ基礎となるマルチダイグラフを持つネストされた辞書示しています。構造は以下のコードで作成できます。以前と同様に、JavaScript、Python、Rubyにもまったく同じコードが適用されます。

まず、下部0は、単一の割り当てによって作成されたリテラル {...}r実線で示されているこの構造は、「矢印ツリー」です(したがって、スパニングツリーです)。順番にリテラルがあるように思われるJSONののシリアライズ0

その後、残りの矢印は、既存のノードの割り当てによって作成されます。サイクルを引き起こす矢印は青色で表示されます。

r  =  { "a" { "a" 5 "b" 5 }、"c" { "a" { "w" 5 }、"c" {}}、"d" { "w" 1.3 }}

r [ "b" ]            =  r [ "a" ];  r [ "c" ] [ "b" ]  =  r [ "c" ] [ "a" ] 
r [ "c" ] [ "a" ] [ "p" ]  =  r [ "c" ];  r [ "d" ] [ "e" ]  =  r [ "d" ] [ "self" ]  =  r [ "d"]

Linux VFSでは、名前関数σd_namedentryデータ構造のフィールドで表されます。[15]0上記構造はJSON-表現構造およびファイルシステムのハードリンク構造との対応関係を示しています。どちらの場合も、「ノード」の組み込みタイプの固定セットがあり、その1つのタイプはコンテナータイプです。ただし、JSONには、実際にはObjectとArrayの2つのタイプがあります。後者が無視される場合(および個々のプリミティブデータ型の区別)、提供されるファイルシステムとJSONデータの抽象化は同じです。どちらも名前付けσとコンテナーノードの区別を備えた矢印ツリーです。

コンテナノードの区別と2分割を使用したツリー構造(「JSONツリー」)の正式な説明については、#Nestedデータ参照してください

パス名

ネストされた辞書の命名関数σは、自然に矢印から矢印パスに拡張されます。連続する矢印の各シーケンスp = [ a 1、...、a n ]には、暗黙的にパス名が割り当てられますパス名を参照)–シーケンスσp)= [ σa 1)、...、σa n)]矢印の名前。[NS] ローカルの一意性は矢印パスに引き継がれます。兄弟パスが異なれば、パス名も異なります。特に、ルート元の矢印パスは、パス名と1対1で対応しています。この対応は、展開の「シンボリックな」表現を提供パス名を介しを-のノードℰはグローバルパス名のツリーを介して識別されます。

順序付けられたツリー

前のサブセクションで紹介した構造は、コンピューティングに表示されるツリーデータ構造のコア「階層」部分を形成します。ほとんどの場合、兄弟間に追加の「水平」順序もあります。で探索木順序は、一般に「キー」または各兄弟に関連付けられた値によって確立されていますが、多くの木にそれはそうではありません。たとえば、XMLドキュメント、JSONファイル内のリスト、およびその他の多くの構造には、ノードの値に依存しない順序がありますが、それ自体がデータです。小説の段落をアルファベット順に並べ替えると、その意味が変わります。

前述のツリー構造X、≤)の対応する展開は、次のように各兄弟セットに線形順序を与えることによって定義できます。[17] [18]

久保山[3]による別の定義は、次のサブセクションで提示されます。

ANは、ツリーが規則正しい構造であるX、≤ V、≤ SXは、ノードの非空集合であり、VおよびSに関係しているXが呼び出されるのV ertical(又はも階層[3] の順序及びS iblingそれぞれ注文します。構造には次の条件があります。

  1. X、≤ Vは前のサブセクションで定義されるように順序付けられていない木である部分順序です。
  2. X、≤ Sは 半順序です。
  3. 個別のノードは、兄弟である場合に限り< Sで比較できます。
    (< S)∪(> S)=((≺ V)○(≻ V))∖のID X
  4. すべてのノードが唯一の有限個の前の兄弟、すなわちのすべての主要な理想的な持っているX、≤ Sを有限です。(有限ツリーの場合、この条件は省略できます。)

条件(2)及び(3)と言うX、≤ Sは各成分が兄弟設定され、成分ごとの線形順序です。条件(4)は、兄弟が設定されている場合と主張Sが無限大で、次いでS、≤ Sがと同型です、≤)、自然数の通常の順序。

これを考えると、次の処方箋によって一意に与えられる3つの(別の)区別された半順序があります。

(< H = (≤ V)○(< S)○(≥ V 時間orizo​​ntal順
(< L - = (> V)∪(< H 「不一致」l inear order)、
(< L + = (< V)∪(< H 「一致する」l inear order)。

この"VSHLの量± 5つの部分注文の"システムVSHL +Lは、-同一のセットの上にXノード、ここで、ペアを除い{≤ S、≤ H }、任意の2つの関係が他の3つを一意に決定します決定性の表を参照してください

表記規則に関する注記:

  • 関連組成シンボル○このサブセクションで用いられるように(左から右に解釈されるべきです)。
  • 記号<およびは、部分的な順序の厳密なバージョン厳密ないバージョンを表します。
  • 記号>およびは逆関係を表します。
  • シンボルのために使用される被覆関係即時半順序のバージョン。

これにより、単一の部分次数関係に対して6つのバージョン≺、<、≤、≻、>、≥が生成されます。除い、各バージョンが一意に他を決定します。から<に渡すには、<が一時的に削減可能である必要があります。これは、常にすべてのために満足している< V< S< Hだがために保持されない場合があります< L +または< L -場合Xは無限です。


半順序VおよびHは相補的です:

(< V)⊎(> V)⊎(< H)⊎(> H)= X × X ∖のID X

結果として、「一致する」線形次数< L +は、< Vの線形拡大です同様に、< Lは-の線形拡張である> V

カバー関係L -及びL +に対応するプリオーダートラバーサル後順トラバースそれぞれ。場合xは≺ L - Y次に、かどうかに応じて、Yは前の兄弟を有するかどうか、Xのノードは、前の兄弟の「右端の」非厳密子孫のいずれかであるY又は、後者の場合、xは最初の子でありますYペア後者の場合、フォーム関連の(≺ L - ∖(<)Hそのノード各非リーフを割り当てる部分的マップである最初の子ノード。同様に、(≻ L +)∖(> Hは有限多くの子供を持つ各非リーフノードの割り当て、最後の子ノードを。

水平方向を使用した定義

「根ざし順序木」の久保山の定義は、[3]は、水平ための利用可能H definitory関係などを。[g](Suppesも参照してください。[19]

これまでに紹介した表記法と用語を使用すると、定義は次のように表すことができます。

順序木は構造であるX、≤ V、≤ H条件(1-5)を満足するように。

  1. X、≤ Vはである部分順序で順序付けられていない木V erticalため。)
  2. X、≤ Hは半順序です。時間orizo​​ntalの順)。
  3. 部分的な注文VおよびH相補的である:(< V)⊎(> V)⊎(< H)⊎(> H)= X × X ∖のID X
    (つまり(< V)で比較できないノードのペアは(< H)で比較でき、その逆も同様です。)
  4. 部分的な注文VおよびH "一致"である:(< H)=(≤ V)○(< H)○(≥ V
    (つまり、すべてのノードのためにxはyのように、X < H yの、すべての子孫のxのすべての子孫先行しなければならないYを。)
  5. すべてのノードには、有限個の先行する兄弟しかありません。(すなわち、すべての無限のために、ある兄弟セット SS、≤ H有する注文タイプ自然数である。)(同様前に、この条件は、有限木の場合には省略することができます。)

兄弟注文(≤ Sはによって得られる(< S)=(< H)∩((≺ V)○(≻ V)) すなわち、二つの別個のノードがあれば順兄弟であり、それらは水平順序である場合のみと兄弟です。

決定性テーブル

次の表は、「VSHL ±」システムの決定性を示しています。テーブルの体内の関係式のいずれかに等しい< V< S< H< L - または< L +カラムに従います。ペアを除いことになる{≤ Sは、≤ H }、順序木をX、...)を一意5つの関係のうちのいずれか2つによって決定されます。

< V < S < H < L - < L +
V、S (≤ V)○(< S)○(≥ V
V、H (< H)∩((≺ V)○(≻ V)) (> V)∪(< H (< V)∪(< H
V、L - (< L -)∩((≺ V)○(≻ V)) (< L -)∖(> V
V、L + (< L +)∩((≺ V)○(≻ V)) (< L +)∖(< V
H、L - (> L -)∖(< H
H、L + (< L +)∖(< H
L -、L + (> L -)∩(< L + (< L -)∩(< L +
S、L - XVの YyはINF = L - YYは、の画像である{ Xを下}(≥ S)○(≻ L -
S、L + XVの YY = SUPのL +YYは、の画像である{ X下}(≤ S)○(≺ L +

最後の2行では、INF L - Yは意味infimumYにおけるX、≤ Lを- )及びSUPのL +Yは意味supremumYにおけるX、≤ L +を。両方の列で、(≤ S RESP。(≥ Sは同等兄弟で置き換えることができる等価 (≤ S)○(≥S。具体的に、のいずれかと一緒にセット兄弟にパーティションL -又はL +はまた、順序木を決定するのに十分です。以下のための最初の処方Vは、のように読み取ることができる:非ルートノードの親xはの兄弟のすべての即時先行の組のinfimum等しいX単語「infimum」および「先行」がに関して意図されています、L - 2と同様の処方で、単に「supremum」、「後継者」と使うL +を

関係SHは明らかdefinitoryペアを形成することはできません。最も単純な例として、正確に2つのノードを持つ順序付けられたツリーを考えてみましょう。そうすると、どちらがルートであるかがわかりません。

XPath軸

XPath軸 関係
ancestor < V
ancestor-or-self V
child V
descendant > V
descendant-or-self V
following < H
following-sibling < S
parent V
preceding > H
preceding-sibling > S
self id X

右側の表は、導入された関係とXPath軸の対応を示しています。これは、構造化ドキュメントシステムで、開始「コンテキスト」ノードと特定の順序関係を持つノードにアクセスするために使用されます。コンテキストノード[20] xの場合、左側の列の指定子によって指定されたその、対応する関係の下{ x }のイメージ等しいノードのセットです 。のとしてのXPath 2.0、ノードはに「返却」されている文書順序「不一致」線形順序で、L - 「一致」が達成されます、垂直次数≤の場合Vは反対に定義され、自然の木による集合論のように、下から上への方向が根の外側になります[NS]

トラバーサルマップ

以下は、順序付けられたツリートラバーサルに通常使用される部分マップのリストです[21]各マップは区別される機能のsubrelation L -又はその反対。

  • V ...親ノード部分のマップ、
  • S ...以前、兄弟部分のマップ、
  • S ...次-兄弟部分のマップ、
  • (≺ L -)∖(< H ...第一子の部分的なマップ、
  • (≻ L +)∖(> H ...最後の子部分のマップ、
  • L - ...前のノード部分のマップ、
  • L - ...次のノード部分のマップ。

構造の生成

トラバーサルマップは、部分的な単項代数[22] X、親、previousSibling、...、nextNode)を構成し、リンクされたデータ構造としてツリーを表すための基礎を形成します。少なくとも概念的には、親リンク、兄弟隣接リンク、および最初/最後の子リンクがあります。これは、一般に順序付けされていないツリーにも当てはまります。これは、LinuxVFSのdentryデータ構造で確認できます[23]

半順序の「VSHL ±」システムと同様に、順序付けられたツリー構造全体を一意に決定するトラバーサルマップのペアがあります。当然のことながら、そのような発生構造であるX、≺ V、≺ Sとして転写することができるX、親、nextSibling) -親と次の兄弟リンクの構造。もう1つの重要な生成構造は、左子右兄弟二分木として知られるX、firstChild、nextSibling)です。この偏代数は、二分木と順序付けられた木の間の1対1の対応を確立します。

二分木を使った定義

二分木への対応は、偏代数としての順序付けられた木の簡潔な定義を提供します。

順序木は構造ですここで、Xは、非空のノードの設定され、LCRSは、上の部分の地図であるXと呼ばれるL eft- Cヒルド及び R ight- S iblingそれぞれ。構造には次の条件があります。

  1. 部分マップlcrsは互いに素です。つまり、lc)∩(rs)=∅です。
  2. lc)∪(rsの逆関数は、偏代数Xpが順序付けられていないツリーであるような偏マップpです。

半順序構造X、≤ V、≤ Sは次のように得られます。

(≺ S = rs
(≻ V = LC)○(≤ S

レベルごとの順序付け

破線を示し、< B -順序を)

「VSHL ±」システムの可能な拡張として、ツリーのレベル構造に基づいて、ノード間の別の区別された関係を定義できます。まず、私たちはで表してみましょうEによって定義された同値関係XE yの場合をしている場合にのみ、XYは、先祖の同じ番号を持っています。この収率にノードの集合の分割レベル L 0L 1、...(L N - coarsementにパーティションの組の兄弟。次に、関係を定義します<E < B -< B +によって

その観察することができる。< Eは厳密半順序となる< B -< B +は厳密合計オーダーです。また、「VSL間の類似性がある±」と「VEB ±:」システム< Eは、に成分的線形と直交する< V< B -の線形拡張である< Eとの> V、そして< B +は< Eおよび< Vの線形拡大です

シーケンスによるエンコード

順序付けられたツリーは、自然数の有限シーケンスによって自然にエンコードできます。[24] [i]を表します自然数のすべての有限シーケンスのセット。空でない部分集合W すべてのu vがからの場合ツリードメイン[25] [26]と呼ばれますおよびすべてのi jから次のことが成り立ちます(連結演算子です):

  1. もしUVW   、その後   のuWWプレフィックスが閉じています。)
  2. もしU ⁎[ I ]∈ WJ < I   その後、   U ⁎[ J ]∈ WWは左-兄弟-閉じています。)

上の誘起構造Wは、順序木を生じさせる:接頭辞の注文を取るV辞書順のためL - [NS]

逆に、順序付けられたツリーに対してT =(X、≤ V、≤ L - 各ノードを割り当てるxは配列WX兄弟インデックスのを、すなわち、ルートが空のシーケンスが割り当てられ、すべての非ルートノードのためのX、せwx)= w(parent(x))⁎[ i ]ここで、ixの先行する兄弟の数です。置くW = { WXの)| XX}その場合、WTと同型の誘導構造を持つツリードメインです。

ネストされたリスト

ネストされたリスト

ネストされたリスト
R  =  [ 5 5 ]、[ 5 ]、[]、[ 1.3 ]]] 
R [ 3 ]  =  R [ 0 ]  
、R [ 1 ] [ 2 ]  =  R [ 1 ] [ 0 ] 
、R [ 1 ] [ 0 ] [ 1 ]  =  r [ 1 ]  
r [ 2 ] [ 2 ]  =  r [ 2 ] [ 1 ] =  r [ 2 ]

兄弟の順序付けは、順序付けされていないツリーに導入されたマルチダイグラフの一般化に自然に適用できます。移動、兄弟インデックスは特別な名前と見なすことができます。ツリードメインは、ちょうど木のあるパス名その結果、ネストされた辞書に対応するものとしてネストされたリスト取得します。

右に示す例は、前に示したネストされた辞書のネストされたリストバージョンを提供します。以前と同様に、リテラルをに1回割り当てることによって作成される初期構造(実線で表される矢印ツリー)があります。その後、構造は、追加のリンクを導入する割り当てによって変更されます。 [...]r

このコードはJavaScriptとRubyに適用できます。Pythonでは、初期構造に存在しない兄弟インデックスを使用しているため、割り当ての変更は許可されていません。[k]

ネストされたデータ

ネストされた辞書とネストされたリスト(それぞれ、順序付けされていない/順序付けられたツリーの一般化)の概念は、ネストされたデータの統一概念に組み合わせることができます。このような構造は、JSONデータ形式に関連して最も一般的です。これらの構造は、コンテナノードの識別されたセットを持つマルチディグラフであり、各コンテナはディクショナリまたはリストのいずれかです。以下のテキストでは、辞書やリストのセットがそれぞれ示されているX O及びX Aを。これは、対応する2つのタイプのコンテナーがオブジェクトと配列と呼ばれるJSONの用語によるものです。非コンテナノードの補完的なセットは、「プリミティブ値」を表します。 JSON固有の形式化[27] [28] は、サポートされているデータ型に応じてさらに改良を加えています

ネストされたデータは、構造として形式化できます ℳ=(XΣAX OX Astσιここで、 XノードのセットΣ名前のセットAはセットです矢印はX O及び X Aは、の区別サブセットであるXSはから部分関数であるAXソース・マップ)、 tはからの全機能であるAXターゲット・マップ)、 σはから部分関数であるAΣその矢印割り当てる名前を、および ιはから部分関数であるA組に矢印にその兄弟インデックスを割り当てる自然数の数

してみましょうℳが呼び出されるネストされたデータツリー、以下の条件が満たされている場合:

  1. 1「ルート」の矢印は、まさにそこにあるRソースが、Srを定義されていません。
  2. 各ノードは、矢印ルートから始まる矢印の経路を介して到達可能であるR
  3. 以下からのすべてのノードX O  ∪  X Aは正確に一つの矢印のターゲットです。
  4. 矢印の元であるすべてのノードからなるX O  ∪  X A
  5. 集合X OX Aは互いに素です。
  6. 矢印命名関数σは、すべての矢印abについて、次の条件を満たす
    1. σaは定義されている場合にのみ   、SA)∈  X O
    2. 場合σ及びσbは両方の定義のいずれか等しくさ  =  Bまたは S)≠  SB
  7. 矢印索引付け関数ιは、すべての矢印abについて、以下を満たします
    1. ι場合にのみ定義され、   S)∈ X A
    2. 場合ι及びιbは両方の定義のいずれか等しくさ  =  Bまたは S)≠  SB
    3. 場合ιはに定義され、非ゼロ次いで ι)= ι')+ 1いくつかについては、矢印 ように、S)= S'

特に、(1)と(2)は、アクセス可能な先の尖った矢筒XAst)を定義していることに注意してください条件式(1-4)の公理化を提供矢印ツリーを容器の区別とX O  ∪  X A(3)コンテナへの一意のリンクがあり、(4)非コンテナはリーフノードである必要があります(ファイルシステムのハードリンクについては、条件(b)および(a)を参照)。(1–4)の重要な結果は、非周期性の条件です

  1. 連続する矢印の円形のパスはありません。

この条件は、(3)の弱い代替手段を提供します。

全順序

辞書には順序付けされていないコレクションのセマンティクスがありますが、プログラミング環境では、多くの場合、固有の順序付けが装備されています。このような順序付けは、Python、Ruby、JavaScriptのすべてでサポートされています。[l]

したがって、順序付けられたネストされたデータツリーも検討する価値があります。これは、すべての兄弟セットが順序付けられているネストされたデータツリーの改良版です(条件(7a)はルート以外のすべての矢印aに対してιaが定義されるように変更されます。)

命名法

上記の条件の特定のサブセットおよび/またはℳの特定の構成要素のみを考慮することにより、ツリーデータ構造の命名法を取得します。アクセス可能な先の尖った矢筒XAstは、「最小公分母」を形成します–条件(1)および(2)は常に必要です。条件(4-7)か否かを適切に課される X OX Aσまたはιが定義されています。

「ツリー」属性は、条件(3)によって確立されます。

必須 定義 区別
独自性
(3)
非周期性
(3 ')
σの命名 注文ι X O X A
セマンティック 合計
アクセス可能な先の尖った矢筒
順序付けられていないツリー はい はい
注文したツリー はい はい はい はい
コンテナを区別した矢印ツリー
はい はい
はい X OX A
ネストされた辞書
Perl: ハッシュ
Python: 辞書
ルビー: ハッシュ
JavaScript: 物体
全般的 はい はい
非巡回 はい はい はい
はい はい はい はい
順序付けられました はい はい
ネストされたリスト
Perl: 配列
Python: リスト
Ruby、JavaScript: 配列
全般的 はい はい はい
非巡回 はい はい はい はい
はい はい はい はい はい
ネストされたデータ 全般的 はい はい はい はい
非巡回 はい はい はい はい はい
はい はい はい はい はい はい
順序付けられました はい はい はい はい はい

も参照してください

その他の木

注意事項

  1. ^ これは、ツリーを形成するサブグラフであるグラフ理論で使用されるサブツリーの正式な定義とは異なります。すべての子孫を含める必要はありません。たとえば、ルートノード自体はグラフ理論の意味ではサブツリーですが、データ構造の意味ではサブツリーではありません(子孫がない場合を除く)。
  2. ^ 正しく、根付いた、順序付けられた有向グラフ。
  3. ^ あるいは、「部分的」バージョンは、除外することによって採用することができます
  4. ^ ta)= sb場合、矢印abそれぞれ連続していると言われます
  5. ^ つまり、同じソースノードを持つ矢印。
  6. ^ ここでは、矢印ルートと仮定し、rはしていないのp
  7. ^ 残念ながら、著者は水平順序関係に兄弟順序という用語を使用しています。これは、誤称ではないにしても、非標準です。
  8. ^ これにより、XPath軸を順軸逆軸に分類することで、不等式シンボルの2つの可能な方向の一致も確立されます。
  9. ^ 一般に、自然数と同型の順序を備えた任意のアルファベットを使用できます。
  10. ^ このステートメントは、条件(ii)に関係なく有効です。
  11. ^ これは例えばによって解決することができますr = [[5,5],[[5,0],[],0],[[1.3],0,0],0]
  12. ^ Python 3.7、Ruby 1.9、およびECMAScript 2020( tc39.es/proposal-for-in-order)以降。

参考文献

  1. ^ ワイスタイン、エリックW. 「サブツリー」MathWorld
  2. ^ スザンナS.エップ(2010年8月)。アプリケーションを使用した離散数学カリフォルニア州パシフィックグローブ:Brooks / Cole PublishingCo.p。694. ISBN 978-0-495-39132-6
  3. ^ a b c d 久保山哲二(2007)。「木のマッチングと学習」(PDF)東京大学博士論文
  4. ^ 「LinuxVFSモデル:命名構造」
  5. ^ ドナルドクヌースThe Art of Computer Programming、第1巻:基本的なアルゴリズム、第3版。Addison-Wesley、1997年。セクション2.3.4.2:方向付けられた
  6. ^ Unger、Spencer(2012)。「集合論の木」(PDF) Cite journal requires |journal= (help)
  7. ^ ブルースフィールズ。「Linuxカーネルに関する注意」
  8. ^ ピエールコインテ(1987)。「メタクラスはファーストクラス:ObjVlispモデル」。オブジェクト指向プログラミングシステム、言語、およびアプリケーションに関するOOPSLA'87会議議事録の議事録北ホラント。
  9. ^ Wolfgang Klas、Michael Schrefl(1995)。メタクラスとその応用:データモデルの調整とデータベース統合スプリンガー。
  10. ^ 「メタクラスとは何ですか?」
  11. ^ 「Rubyオブジェクトモデル:データ構造の詳細」
  12. ^ B. Korte、およびJ. Vygen(2012)。組み合わせ最適化スプリンガー、ハイデルベルク。
  13. ^ Dasgupta、Abhiit(2014)。集合論:実際の点集合の紹介付きニューヨーク:ビルクホイザー。
  14. ^ Makinson、David(2012)。計算のためのセット、論理および数学シュプリンガーサイエンス&ビジネスメディア。ISBN  978144712​​4993
  15. ^ a b ボベット、ダニエル; Cesati、Marco(2005)。Linuxカーネルを理解するオライリー。ISBN  9780596554910
  16. ^ Aczel、Peter(1988)、十分に根拠のないセット。、CSLI Lecture Notes、14、カリフォルニア州スタンフォード:スタンフォード大学、言語と情報の研究センター、ISBN 0-937073-22-9MR  0940014
  17. ^ Jan Hidders; フィリップミシェルズ; Roel Vercammen(2005)。「XQueryパス式での並べ替えと重複排除の最適化」(PDF) Cite journal requires |journal= (help)
  18. ^ フリットヨフダウ; マークシファー(2007)。「XMLドキュメント構造をナビゲートおよび編集するための形式」(PDF)ネットワーク情報システムにおけるデータベースに関する国際ワークショップスプリンガー、ベルリン、ハイデルベルク。
  19. ^ サップス、パトリック(1973)。「自然言語の文脈自由断片の意味論」。自然言語へのアプローチスプリンガー、ドルトレヒト:370–394。CiteSeerX 10.1.1.398.2289土井10.1007 / 978-94-010-2506-5_21ISBN   978-90-277-0233-3
  20. ^ 「XMLパス言語(XPath)3.1」World WideWebコンソーシアム2017年3月21日。
  21. ^ 「ドキュメントオブジェクトモデルトラバーサル」W3C。2000年。
  22. ^ 「単項代数」
  23. ^ JTMühlberg、G.Lüttgen(2009)。「コンパイルされたファイルシステムコードの検証」。形式手法:基礎と応用:形式手法に関する第12回ブラジルシンポジウム。スプリンガー、ベルリン、ハイデルベルク。CiteSeerX 10.1.1.156.7781  Cite journal requires |journal= (help)
  24. ^ L。アファナシエフ; P.ブラックバーン; I. Dimitriou; B.ガイフ; E.ゴリス; M.マルクス; M. de Rijke(2005)。「注文された木のPDL」(PDF)Journal of Applied Non-ClassicalLogics15(2):115–135。土井10.3166 /jancl.15.115-135S2CID 1979330  
  25. ^ Michaelis、Jens(2001)。「線形文脈自由書き換えシステムを最小限の文法に変換する」。計算言語学の論理的側面に関する国際会議スプリンガー、ベルリン、ハイデルベルク。pp。228–244。
  26. ^ Morawietz、フランク(2008)。自然言語形式主義へ​​の2段階のアプローチWalter de Gruyter ISBN  9783110197259
  27. ^ Bourhis、P。; Reutter、JL; Vrgoč、D。(2020)。「JSON:データモデルとクエリ言語」情報システム89
  28. ^ Botoeva、E。; Calvanese、D。; Cogrel、B。; Xiao、G。(2018)。「MongoDBクエリの表現度と複雑さ」データベース理論に関する第21回国際会議(ICDT 2018)SchlossDagstuhl-Leibniz-ZentrumfürInformatik。
  29. ^ Miltiadou、Milto; キャンベル、ニールDF; コスカー、ダレン; グラント、マイケルG.(2021年1月)。「3Dポリゴンモデル作成中にボクセル化された全波形空中LiDARデータの効率的な管理に使用されるデータ構造に関する比較研究」リモートセンシング13(4):559 Bibcode2021RemS ... 13..559M土井10.3390 / rs13040559

さらに読む

外部リンク