Loading article…
ツリー構造、ツリー図、またはツリー モデルは、構造の階層的性質をグラフィカルな形式で表現する方法です。この図は、生物学的な樹木と比較すると一般的に上下逆で、「幹」が上部に、「葉」が下部にあるものの、古典的な表現が樹木に似ていることから「ツリー構造」と呼ばれています。
ツリー構造は概念的なものであり、いくつかの形式で現れます。特定の分野におけるツリー構造の説明については、コンピューター サイエンスのツリー (データ構造)を参照してください。グラフ理論に関連する限り、 ツリー (グラフ理論)またはツリー (集合論)を参照してください。その他の関連記事は以下に記載されています。
用語とプロパティ
ツリー要素は「ノード」と呼ばれます。要素を接続する線は「ブランチ」と呼ばれます。子を持たないノードは、リーフ ノード、エンド ノード、または「リーフ」と呼ばれます。
すべての有限ツリー構造には、上位ノードを持たないメンバーが存在します。このメンバーは「ルート」またはルート ノードと呼ばれます。ルートは開始ノードです。ただし、逆は当てはまりません。無限ツリー構造にはルート ノードが存在する場合と存在しない場合があります。
ノード間の関係の名前は、家族関係の親族用語をモデルにしています。「親」と「子」という性別に中立な名前は、古い「父」と「息子」という用語に大きく取って代わりました。「叔父」という用語は、親と同じレベルの他のノードに対して今でも広く使用されていますが、「ommer」などの性別に中立な用語に置き換えられることもあります。[1]
- ノードの「親」とは、階層内で 1 段階上位のノード (つまり、ルート ノードに近いノード) であり、同じブランチ上にあります。
- 「兄弟」（「兄弟」または「姉妹」）ノードは同じ親ノードを共有します。
- ノードの「叔父」（場合によっては「ommers」）は、そのノードの親の兄弟です。
- すべての下位ノードに接続されているノードは「祖先」と呼ばれます。接続されている下位ノードは祖先ノードの「子孫」です。
この例では、「encyclopedia」は「science」と「culture」の親であり、子です。「art」と「craft」は兄弟であり、「culture」の子です。「culture」は親であり、したがって祖先の 1 つです。また、ツリーのルートである「encyclopedia」は、「science」、「culture」、「art」、「craft」の祖先です。最後に、葉である「science」、「art」、「craft」は、他のノードの祖先ではありません。
ツリー構造は、家系図、生物学的進化ツリー、言語ファミリーの進化ツリー、言語の文法構造（重要な例は S → NP VP で、文は名詞句と動詞句で構成され、それぞれがさらに他の要素を持ち、さらにその要素も他の要素を持つことを意味します）、Web サイト内で Web ページが論理的に順序付けられる方法、整数集合の数学的ツリーなど、あらゆる種類の分類学的知識を表すことができます。
オックスフォード英語辞典には、 1965年のノーム・チョムスキーの『統語論の側面』で「ツリー構造」と「ツリーダイアグラム」の両方の用語が使用されていることが記録されている。[2]
ツリー構造では、任意のポイントから他の任意のポイントへの パスは1 つだけです。
コンピュータ サイエンスではツリー構造が広く使用されています ( 「ツリー (データ構造)と通信」を参照 )。
正式な定義については集合論を参照してください。また、子が必ずしも後継者ではない一般化については、接頭辞順序を参照してください。
ツリー構造の例
- インターネット：
- ユーズネット階層
- ドキュメントオブジェクトモデルの論理構造、[3] Yahoo!主題索引、Curlie
- オペレーティングシステム:ディレクトリ構造
- 情報管理:デューイ十進分類法、PSH、この階層的な箇条書きリスト
- 管理：階層的な組織構造
- コンピュータサイエンス：
- 生物学:進化の樹
- ビジネス:ねずみ講
- プロジェクト管理:作業分解構造
- 言語学:
- スポーツ:ビジネスチェス、プレーオフブラケット
- 数学:フォン・ノイマン宇宙
- 群論:子孫ツリー
木を表現する
ツリー構造を視覚的に表現する方法は数多くあります。ほとんどの場合、これらはいくつかの基本的なスタイルのバリエーションまたは組み合わせに要約されます。
古典的なノードリンク図
線分でノードを接続する古典的なノードリンク図:
ネストされたセット
囲みや包含を使用して親子関係を示すネストされたセット。例としては、ツリーマップ、フラクタル マップ、オイラー図などがあります。
階層化された「つらら」図
配置/隣接性を使用する階層化された「つらら」図。
アウトラインとツリービュー
インデントを使用するリストまたは図。「アウトライン」または「ツリー ビュー」と呼ばれることもあります。
概要:
- 百科事典
- 文化
- 美術
- クラフト
- 科学
- 文化
ツリービュー:
- 百科事典
- 文化
- 美術
- クラフト
- 科学
- 文化
ネストされた括弧
入れ子になった括弧への対応は、アーサー・ケイリー卿によって最初に指摘されました。
((芸術、工芸)文化、科学)百科事典
または
百科事典(文化(芸術、工芸)、科学)
放射状木
木は放射状に表現することもできます。
参照
- 木の種類
- 関連記事
参考文献
- ^ “Ethereum Glossary”. GitHub . 2019年4月25日時点のオリジナルよりアーカイブ。2019年4月17日閲覧。
- ^ 「tree」。オックスフォード英語辞典（オンライン版）。オックスフォード大学出版局。 （サブスクリプションまたは参加機関のメンバーシップが必要です。）
- ^ 「ドキュメントオブジェクトモデルとは何か?」W3C アーキテクチャ ドメイン。 2012 年 2 月 12 日時点のオリジナルよりアーカイブ。2006 年 12 月 5 日閲覧。
さらに読む
ツリー構造の基本的なスタイルの識別については、以下を参照してください。
- ジャック・ベルタン『グラフィックスの記号学』1983年、ウィスコンシン大学出版局（第2版1973年、ISBN 978-0299090609 ;
- ドナルド・E・クヌース(1968)。『コンピュータプログラミングの芸術』第1巻: 基本アルゴリズム。Addison-Wesley。pp. 309–310。
- Brian Johnson とBen Shneiderman、「ツリーマップ: 階層情報構造の視覚化に対する空間充填アプローチ」、Proceedings of IEEE Visualization (VIS)、1991 年、pp. 284–291、ISBN 0-8186-2245-8。
- Peter Eades、Tao Lin、Xuemin Lin、「Two Tree Drawing Conventions」、International Journal of Computational Geometry and Applications、1993 年、第 3 巻、第 2 号、pp. 133–153。
- マヌエル・リマ（2014年）『The Book of Trees: Visualizing Branches of Knowledge（第1版）』ニューヨーク：プリンストン・アーキテクチュラル・プレス。ISBN 978-1-616-89218-0。
外部リンク
ウィキメディア・コモンズには、ツリー図に関連するメディアがあります。
- T-REX サーバー上の系統樹の可視化
- ツリー構造を使用してビジネスプロセスを設計する - Society for Technical Communicationより