導入
グラフの理論では、ルート付きツリーまたはツリー構造は、ルートが 1 つで、ルートを除くすべてのノードが 1 つの親を持つ、指向性非循環グラフです。
コンピューター サイエンスでは、このタイプのグラフを表すために使用される再帰的データ構造でもあります。
語彙
ツリーには、次の 2 つのカテゴリの要素があります。
- リーフ(または外部ノード)、ツリー内にスレッドを持たない要素。
- 内部ノード、ワイヤー付きの要素 (サブブランチ)。
ツリーのルートは親を持たない唯一のノードです。ノード (父親とその息子) はエッジによって相互にリンクされます。コンテキストに応じて、ノードはツリーの内部ノード、または内部ノードまたは外部ノード (リーフ) を指定できます。
ノードの深さは、ルートからノットまでの距離、つまりエッジの数です。木の高さは、木の葉の最大の深さです。ツリーのサイズはノードの数 (葉を数えるかどうか)、パスは各葉の深さの合計です。
木にはラベルを付けることができます。この場合、各ノードにはラベルがあり、これはある意味、ノットの「コンテンツ」です。ラベルは非常に単純なものにすることができます (たとえば、整数)。オブジェクト、データ構造のインスタンス、ポインターなど、必要に応じて複雑にすることもできます。ツリーにアルゴリズムを埋め込むためには、全体的な関係に従ってラベルを比較できることがほとんどの場合必須です。
ファイル システム内のファイルとフォルダーは通常、ツリー形式で編成されます。たとえば、FHS を参照してください。
実際、ツリーがそのように使用されることはほとんどありませんが、より制限的な構造を持つ多くの種類のツリーが存在し、特にデータベースの管理やファイルのインデックス作成など、アルゴリズムでよく使用されます。これにより、迅速かつ効果的な調査が可能になります。ここでは主な例を示します。
- 各ノードに最大 2 本のワイヤを持つバイナリ ツリー。実際には、リサーチ、ヒープ、avl、さらには赤黒ツリーのバイナリ ツリーの形で使用されます。最後の 2 つの例は、バランスの取れたツリー、つまりサブブランチの高さがほぼ同じであるツリーの特殊なケースです。
- バイナリ ツリーを一般化したN-AIA ツリー: 各ノードには最大でn 個の息子があります。木 2-3-4 と木 B は使用例であり、これもバランスの取れた木です。
コース
幅ルート
幅ルートは、ツリーのノードのレベルごとのコースに対応します。レベルとは、同じ深さに位置する内部ノードまたは葉のセットです。考慮したツリー内の同じ高さの節または葉とも言えます。特定のレベルのコースの順序は、通常、親のノード (すぐ上のレベルのノット) のコースの順序によって再帰的に与えられます。
したがって、前のツリーが使用される場合、ルートはa 、 b 、 c 、 d 、 e 、 f 、そしてgになります。
徹底的に
深層ルートは木の上を往復するコースです。一般に、次の 2 つの順序が可能です。
- 詳細コース接頭辞: このモードのルートでは、現在のノードがその子孫よりも前に処理されます。したがって、前のツリーが使用される場合、ルートはa 、 b 、 d 、 e 、 c 、 f 、そしてgになります。
- In – Depth course suffix: もちろん、このモードでは、現在のノードはその子孫の後に処理されます。したがって、前のツリーが使用される場合、ルートはD 、 E 、 B 、 F 、 G 、 C 、そしてaになります。このルート モードは逆ポーランド表記に対応します。
二分木の場合、現在のノードを左ノードと右ノードの間に扱うことで、 if you are a if you are a if you are a if you are a Very を作成することもできます。したがって、前のツリーが使用される場合、ルートはD 、 B 、 E 、 A 、 F 、 C 、そしてgになります。