ツリー(データ構造)

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

コンピュータサイエンスではツリーは広く使用されている抽象データ型であり、階層ツリー構造をシミュレートします。ルート値と、リンクされたノードのセットとして表される親ノードを持つ子のサブツリーがあります。

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

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

一般的な使用法

用語

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

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

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

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

ツリーTサブツリーは、 TのノードとTのすべての子孫で構成されるツリーです。[a] [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つ以上のサブツリーで構成される構造です。

木を描く

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

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

一般的な操作

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

トラバーサルと検索方法

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

表現

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

実際、バイナリツリーはリストのリスト(値がリストであるリスト)として実装できます。リストの先頭(最初の項の値)は左の子(サブツリー)であり、末尾(リスト)は2番目以降の用語の)は正しい子(サブツリー)です。これは、Lisp S式のように、値を許可するように変更できます。ここで、ヘッド(第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つの子があり、それぞれがツリー(おそらく空)であるようなツリーです。ツリーの操作の完全なセットには、フォーク操作が含まれている必要があります。

数学的定義

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

数学的には、順序付けられていないツリー[3](または「代数ツリー」)[4]は、代数的構造 X、親)として定義できます。ここで、Xは空でないノードのキャリアセットであり、親はX上の関数であり、各ノードxその「親」ノード、parent(x構造は、すべての空でない部分代数が同じ不動点を持たなければならないという条件に従います。つまりparent 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を満たします:無限シーケンスx1≺x2≺x3≺ ありませ

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

  1. Xにはちょうど1つの≺-最大ノードが含まれます。

次に、条件(2)が冗長になります。

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

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

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

記述集合論(DST)でのツリーの定義は、有限シーケンス間の接頭辞順序として半順序X、≥)の表現を利用します。同型写像までは、DSTツリー(の逆)とこれまでに定義されたツリー構造との間に1対1の対応があることがわかります。

ツリーを代数ツリーを偏代数ツリーを半順序ツリーを半順序として、4つの同等の特性を参照できます5番目の同等の定義もあります。これは、接続された非巡回 ルートグラフであるグラフ理論のルートツリーの定義です。

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

  • 「ルートdentryにはそれ自体を指すd_parentがある」LinuxVFS [7]
  • インスタンス化ツリーの概念[8] [9] [10]

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

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

兄弟セット

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

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

セット包含の使用

すべての半順序集合と同様に、ツリー構造X、≤)は包含順序で表すことができます–≤が誘導された包含順序あると一致する集合システムによって。Uが空でないセットであり、ℱがUのサブセットのセットであり、次の条件が満たされるような構造(U、ℱ)を考えます(ネストセットコレクションの定義による)。

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

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

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

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

根拠のある木

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

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

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

ここで、ℱは⋃ { ℛk |のサブセットです。の要素がペアごとに素であり、xがdom(⋃ℱ)に属さないノードであるようなk < i }関係Sの定義域を表すためにdom(Sを使用します。)空ののみが可能であるため、最下位ステージℛ0が単一ノードツリー{(x x }で構成されていることに注意してください。各段階で、(おそらく)新しい木Rは森をとることによって建てられます⋃ℱ下段のコンポーネントℱを使用し、 ⋃ℱの上に新しいルートxを接続します。

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

再帰ペアの使用

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

( X上の木 t∈T _ _ tは、 ℱ× XからペアFxであり、すべてs∈Fに対して x∉ノード(s
( X上の森 F∈ℱ _ FTのサブセットであり、すべてのst∈F stに対して、
nodes(s)∩nodes(t =
(木のノード) y∈nodest t =(Fx)∈Tあり、いくつかs∈Fに対してy = xまたはy∈nodess
のいずれかです。

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

s≺t _ _ s∈π1 t_ _ _

ここで、π1(t)はt最初座標射影ですつまり、あるx∈Xに対してt =FxとなるようなフォレストFですT、≤)はマルチツリーであることがわかります。すべてのt∈Tに対して、 順序付けられた主イデアルtは、半順序としての十分に根拠のあるツリーですさらに、すべてのツリーに対してt∈T 、その「ノード」順序構造(nodes(t)、≤t は、 FxGy 両方のようなフォレストFG∈ℱがある場合にのみ、x≤ty与えられます。 tのサブツリーであり、Fx)≤(Gy

矢印を使用する

順序付けされていないツリーの一般化と同様に別の形式化は、ノードの親子ペアを具体化することによって取得できます。そのような順序付けられた各ペアは、抽象的なエンティティ、つまり「矢印」と見なすことができます。これにより、マルチダイグラフ XAstが生成されます。ここで、 Xはノードのセット、A矢印のセット、stはAから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_parentます。[15]各iノードには固定ファイルタイプが割り当てられており、そのディレクトリタイプは「設計された親」の特別な役割を果たします。 d_inode

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

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

有向グラフでのパスの使用

セットメンバーシップの展開 すべての集合xについて、関係構造( x∪ { x }、∈)TC({ x })、∈)は両方ともapgsです。[apg 1]

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

(5、∈)折りたたむ

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

(5、∈)展開

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

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

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

  • X 'は、 rの逆パスのセット、つまり、(a) pの連続するメンバーが逆にRに関連し、(b)最初のメンバーとなるようなノード(Xの要素)の空でない有限シーケンスpのセットです。 pはルートrであり、
  • R 'はX'からのパス間の関係であり、あるノードxに対してp = q⁎ [ x ]の場合にのみ、パスpqR 'に関連します(つまり、 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として暗黙的に導入しました。reduct (XRが偏代数として順序付けられていないツリーである場合、 apgℛ=(XRrツリーと呼びます。これは次のように解釈できます。すべてのノードは、正確に1つのパスでアクセスできます。

マルチダイグラフでのパスの使用

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

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

アクセス可能な尖った矢筒(apq):apgのマルチダイグラフへの一般化。

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

ℳ=(XAst

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

構造は次の条件に従います。

  1. ソースsa r が定義されていないルート」矢印が1つだけあります。
  2. すべてのノードx∈Xはルート矢印arで始まる有限シーケンスの連続する矢印を介して到達可能です

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

基礎となるapgは、構造 XRta r))として取得されます。 ここで、 R = {(ta)、sa))| a∈A \ { ar } } _

上の図は、1 +14の矢印を持つapqの例を示しています。JavaScriptPython、またはRubyでは、構造は次の(まったく同じ)コードで作成できます。

r  =  {};  
r [ 1 ]  =  {};  r [ 2 ]  =  r [ 1 ];  r [ 3 ]  =  {};  r [ 4 ]  =  {};  
r [ 1 ] [ 5 ]     =  {};    r [ 1 ] [ 14 ]     =  r [ 1 ] [ 5 ]; 
r [ 3 ] [ 7 ]     =  {};    r[ 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からΣまでの部分関数、 tはAからの合計関数です。 X矢印aの場合、トリプルの構成要素sa)、σa)、ta))それぞれソース名前、およびターゲットです。

構造は次の条件に従います。

  1. 還元XAstは、前に定義したように、アクセス可能な先の尖った矢筒(apq)です。
  2. 名前関数σは、ソースのないルート矢印に対してのみ定義されていません。
  3. 名前関数σは、すべての兄弟の矢印のセットへの制限に単射です。つまり、すべての非ルート矢印abに対してsa)= sbおよびσa)= σbの場合、a = b
ネストされた辞書は構造です
ℰ=(XVΣ、𝒜、r
ここで、Xノードのセット、V(プリミティブ)値のセット、 Σ名前のセット、𝒜X × Σ ×(X∪V)のサブセット-ソース-名前-ターゲットの関係、およびr ∈Xルートノードです以下が必要です。
(1)𝒜X × Σの部分関数です。
(2)X、≺、rアクセス可能な点付きグラフであり、は誘導されたターゲットとソースの関係です。[f]

このような構造は、コンテナを区別せずに、名前付きapqまたはネストされた辞書と呼ぶことができます右側のボックスは、コンテナノードの区別が行われる代替定義を提供します。用語の変化が見られます。「ノード」という用語は「コンテナ」の同義語として使用されますが、「非コンテナ」は(プリミティブ)値の異なる種類のVを形成ます。さらに、矢印はセットに対して「未修正」です

𝒜= {(sa)、σa)、ta))| a∈A \ { a r } }

ソース-名前-ターゲットトリプルの。これらは、上記のリレーショナルデータベーステーブルと見なすことができます。主キーに下線を付けsourcename示します(条件(1))。

構造は、決定論的なラベル付き遷移システムとして言い換えることができます。X「状態」のセット、Σは「ラベル」のセット、𝒜は「ラベル付き遷移」のセット、ルートノードrは「初期状態」です。 、およびアクセシビリティ条件(2)は、すべての状態が初期状態から到達可能であることを意味します。より具体的には、ネストされた辞書とMealyマシン間の接続を観察しますMealyマシンの定義から始めて、ネストされた辞書のクラスは、次の変更によって取得されます:(a)有限性要件を削除し、(b)すべての状態に到達可能であることを要求し、(c)遷移および出力関数を許可する部分的である、(d)遷移関数と出力関数が互いに素なドメインを持っていることを要求する。

ネストされた辞書

ネストされた辞書

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

最初に、部分構造ℰ0は、リテラル {...}を。に1回割り当てることによって作成されますr実線で示されているこの構造は、「矢印ツリー」です(したがって、スパニングツリーです)。リテラルは、 ℰ0のJSONシリアル化のように見えます

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

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

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

パス名

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

順序付けられたツリー

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

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

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

順序付きツリーは構造X≤V≤Sであり、 Xは空でないノードのセットであり、≤Vおよび≤Sは、垂直(または階層[3])順序および兄弟呼ばれるX上関係です。それぞれ注文します。構造は次の条件に従います。

  1. X、≤V 、前のサブセクションで定義された順序付けされていないツリーである半順序です。
  2. X、≤S 半順序です。
  3. 異なるノードは、兄弟である場合に限り 、 < Sで比較できます。
    (< S)∪(> S)=( ( ≺V)○(≻V idX
  4. すべてのノードには、有限個の先行する兄弟しかありません。つまり、X、≤S すべての主イデアルは有限です。(有限ツリーの場合、この条件は省略できます。)

条件(2)および(3)は、X、≤S コンポーネントごとの線形順序であり、各コンポーネントが兄弟セットであることを示しています。条件(4)は、兄弟集合Sが無限大である場合、 S≤S、≤)、自然数の通常の順序。

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

(< H = (≤V ○(< S)○(≥V (水平方向の順序
(< L = (> V)∪(< H 「不一致」lの順序)、
(< L + = (< V)∪(< H 「一致する」lの順序)。

これは、ノード同じセットX上で5の半順序≤V 、 ≤S≤H≤L +≤L-の「VSHL ±」システムに相当します。ここで、ペア{ ≤S≤Hを除く}、任意の2つの関係が他の3つを一意に決定します。決定性の表を参照してください。

表記規則に関する注記:

  • このサブセクションで使用されている関係合成記号○は、左から右に解釈されます()。
  • 記号<およびは、半順序の厳密バージョン非厳密バージョンを表します。
  • 記号>およびは逆関係を表します。
  • 記号は、半順序の直接バージョンである≤の被覆関係使用されます。

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


半順序≤Vおよび≤H相補です

(< V)⊎(> V)⊎(< H ) (> H)= X × X ∖idX

結果として、「一致する」線形順序< L +は、< Vの線形拡大です同様に、< L > Vの線形拡大です。

被覆関係≺L−≺L +は、それぞれプレオーダートラバーサルポストオーダートラバーサルに対応しますx≺L− y場合、 yに前兄弟があるかどうかに応じて、 xノードはyの前の兄弟の「右端」の非厳密な子孫である、後者の場合、xが最初の子になります。yペア後者の場合、関係(≺L ∖(< Hを形成します。これは、各非リーフノードに最初の子ノードを割り当てる部分マップです。同様に、(≻L + ) ∖(> Hは、有限個の子を持つ各非リーフノードに最後の子ノードを割り当てます。

水平方向を使用した定義

久保山の「根付き秩序木」の定義[3]は、水平次数≤Hを定義関係として利用しいる[h](Suppesも参照してください。[19]

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

順序付けられたツリーは、条件(1〜5)が満たされるような 構造X ≤V ≤H です。

  1. X、≤V 順序付けされていないツリーである半順序です。(垂直方向の順序
  2. X、≤H 半順序です。(水平方向の順序
  3. 半順序≤V≤Hは相補的です:(< V ) (> V ) (< H ) (> H)= X × X ∖idX
    (つまり(< V)で比較できないノードのペアは(< Hで比較でき、その逆も同様です。)
  4. 半順序≤Vおよび≤Hは「一貫性がある」:(< H =(≤V (< H)○(≥V
    (つまり、x < H yとなるすべてのノードxyについて、xのすべての子孫がyのすべての子孫に先行する必要があります。)
  5. すべてのノードには、有限個の先行する兄弟しかありません。(つまり、すべての無限の兄弟集合 Sに対して、S、≤H は自然数の順序型を持ちます。)(以前のように、有限ツリーの場合、この条件は省略できます。)

兄弟の順序≤S)は、(<S= < H)∩( ( ≺V)○(≻V によって取得されます。つまり、2つの異なるノードは、水平方向の順序であり、兄弟です。

決定性テーブル

次の表は、「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 x≺Vy↔y = inf L Y ここ で、 Yは ≥S)○(≻L− { x }画像です
S、L + x≺Vy↔y = sup L + Y ここ で、 Yは( ≤S)○(≺L +{ x }画像です

最後の2行で、inf L YX≤L− Yの下限を示しsup L +YX、≤L + Y上限示します両方の行で、≤S または (≥S 、兄弟の同等性(≤S ○(≥ S特に、 ≤L-または≤L +のいずれか一緒に兄弟セットに分割することも、順序付けられたツリーを決定するのに十分です。≺Vの最初の処方は、次のように読み取ることができます。非ルートノードxの親は、 xの兄弟のすべての直前の先行のセットの最小に等しい。ここで、「最小」および「先行」という単語は、 ≤L− _ _ 2番目の処方と同様に、「上限」、「後継者」、および≤L +を使用します。

≤S≤Hの関係は、明らかに定義ペアを形成することはできません。最も単純な例として、正確に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は反対に定義され、自然の木による集合論のように、下から上への方向が根の外側になり[私]

トラバーサルマップ

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

  • ≺V ...親ノード部分マップ、
  • ≻S ...前の兄弟の部分マップ、
  • ≺S ...次の兄弟の部分写像、
  • (≺L ∖(< H ...最初の子の部分写像、
  • (≻L + ) ∖(> H ...最後の子の部分写像、
  • ≻L− ...ノード部分マップ、
  • ≺L−...ノードの部分マップ。

構造の生成

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

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

二分木を使った定義

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

順序付けられたツリーは構造ですここで、Xは空でないノードのセットであり、lcrsは、それぞれアイブリング呼ばれるX上の部分マップです構造は次の条件に従います。

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

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

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

レベルごとの順序付け

破線は< B-順序を示します)

「VSHL ± 」システムの可能な拡張として、ツリーのレベル構造に基づいて、ノード間の別の区別された関係を定義できますまず、xyの祖先の数が同じである場合に限り、x〜Eyで定義される同値関係を〜Eで表しますこれにより、ノードのセットがレベルL 0L 1、...(、L nに分割され、分割が兄弟セット粗くなります。次に、関係を定義します< E < B および< B + by

< Eは厳密な半順序であり、< B-および< B +は厳密な全順序であることがわかりますさらに、「VSL ± 」システムと「VEB ±」システムの間には類似性があります。 < Eはコンポーネントごとに線形であり、< Vに直交し、< B < Eおよび> Vの線形拡大であり、< B + < Eおよび< Vの線形拡大です

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

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

  1. u⁎v∈W 場合   、   u∈W _ _ _ _ _ Wプレフィックスで閉じられています。)
  2. u⁎ [ i ] ∈Wかつj < iの   場合   u⁎ [ j ] ∈W Wは左兄弟-閉じています。)

Wに誘導された構造は、順序付けられたツリーを生成します。≥Vの場合は接頭辞の順序を取り、≤L−場合辞書順序を取ります。[k]

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

ネストされたリスト

ネストされたリスト

ネストされたリスト
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では、初期構造に存在しない兄弟インデックスを使用しているため、割り当ての変更は許可されていません。[l]

ネストされたデータ

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

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

次の条件が満たされる場合、 ℳをネストされたデータツリーと呼びます。

  1. ソースsa r が定義されていない ルート」矢印が1つだけあります。
  2. すべてのノードは、ルート矢印ar で始まる矢印のパスを介して到達可能です
  3. XO∪XAすべて のノードは、正確に1つの矢印のターゲット です 。 
  4. 矢印のソースであるすべてのノードは、XO∪XAから もの です
  5. セットXOXA互いに素です。
  6. 矢印命名関数σは、すべての矢印abについて、次の条件を満たす。
    1. σa)は、 sa)∈XO 場合にのみ定義され   ます
    2. σaσbの両方が定義され、等しい場合、 a =  b またはs a ≠  sbのいずれかです。
  7. 矢印インデックス関数ιは、すべての矢印abについて、次の条件を満たす。
    1. ιa)は、 sa)∈XAある場合にのみ定義され   ます。
    2. ιaιbの両方が定義され、等しい場合、 a =  b またはs a ≠  sbのいずれかです。
    3. ιaが定義され、ゼロ以外の場合、 s a = sa 'となる ような矢印a'に対してιa)= ιa ')+ 1

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

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

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

全順序

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

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

命名法

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

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

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

も参照してください

その他の木

メモ

  1. ^ これは、ツリーを形成するサブグラフであるグラフ理論で使用されるサブツリーの正式な定義とは異なります。すべての子孫を含める必要はありません。たとえば、ルートノード自体はグラフ理論の意味ではサブツリーですが、データ構造の意味ではサブツリーではありません(子孫がない場合を除く)。
  2. ^ 正しく、根付いた、順序付けられた有向グラフ。
  3. ^ あるいは、「部分的」バージョンは、除外することによって採用することができます
  4. ^ ta)= sbの場合、矢印abはそれぞれ連続していると言われます
  5. ^ つまり、同じソースノードを持つ矢印。
  6. ^ ≺= {(yx)| xαy)∈𝒜いくつかのα }。
  7. ^ ここでは、ルート矢印arpにないます。
  8. ^ 残念ながら、著者は水平順序関係に兄弟順序という用語を使用しています。これは、誤称ではないにしても、非標準です。
  9. ^ これにより、XPath軸を順軸逆軸 に分類することで、不等式シンボルの2つの可能な方向の一致も確立されます。
  10. ^ 一般に、自然数と同型の順序を備えた任意のアルファベットを使用できます。
  11. ^ このステートメントは、条件(ii)に関係なく有効です。
  12. ^ これは例えばによって解決することができますr = [[5,5],[[5,0],[],0],[[1.3],0,0],0]
  13. ^ 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、Volume 1: Fundamental Algorithms、ThirdEdition。Addison-Wesley、1997年。セクション2.3.4.2:方向付けられた木
  6. ^ Unger、Spencer(2012)。「集合論の木」(PDF) {{cite journal}}: Cite journal requires |journal= (help)
  7. ^ ブルースフィールズ。「Linuxカーネルに関する注意」
  8. ^ ピエールコインテ(1987)。「メタクラスはファーストクラス:ObjVlispモデル」。オブジェクト指向プログラミングシステム、言語、およびアプリケーションに関するOOPSLA'87会議議事録の議事録北ホラント。
  9. ^ Wolfgang Klas、Michael Schrefl(1995)。メタクラスとそのアプリケーション:データモデルの調整とデータベースの統合スプリンガー。ISBN  9783540600633
  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レクチャーノート、vol。14、カリフォルニア州スタンフォード:スタンフォード大学、言語と情報の研究センター、ISBN 0-937073-22-9MR  0940014
  17. ^ Jan Hidders; フィリップミシェルズ; Roel Vercammen(2005)。「XQueryパス式での並べ替えと重複排除の最適化」(PDF) {{cite journal}}: Cite journal requires |journal= (help)
  18. ^ フリットヨフダウ; マーク・シファー(2007)。「XMLドキュメント構造をナビゲートおよび編集するための形式」(PDF)ネットワーク情報システムにおけるデータベースに関する国際ワークショップシュプリンガー、ベルリン、ハイデルベルク。
  19. ^ サップス、パトリック(1973)。「自然言語の文脈自由断片の意味論」。自然言語へのアプローチスプリンガー、ドルドレヒト:370–394。CiteSeerX10.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回ブラジルシンポジウム。シュプリンガー、ベルリン、ハイデルベルク。CiteSeerX10.1.1.156.7781_  {{cite journal}}: 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-135S2CID1979330_  
  25. ^ ミカエリス、イェンス(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。; コグレル、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

さらに読む

外部リンク