Древовидная структура

Древовидная структура
Древовидная структура, демонстрирующая возможную иерархическую организацию энциклопедии. Подобный пример представляет собой полное двоичное дерево, подразумевающее наличие у всех узлов либо либо только двух дочерних узлов, либо ни одного.
В «Энциклопедии» использовалась древовидная диаграмма для отображения способа упорядочивания ее элементов.

Древовидная структура является одним из способов представления иерархической структуры в графическом виде. Древовидной структурой называется благодаря тому, что граф выглядит как перевернутое дерево. По этой же причине говорят, что корневой узел (корень) находится на самом верху, а листья — внизу.

В теории графов дерево — связанный ациклический граф (иногда его называют направленным ациклическим графом, у которого каждая вершина имеет степень 0 или 1). Ациклический граф без жесткого условия связывания иногда называется лесом (так как он состоит из деревьев).

Из совокупности древовидных структур состоят неоднородные семантические сети.


Содержание

Терминология и свойства

Каждая конечная древовидная структура содержит элемент, не имеющий вышестоящего. Этот элемент называется «корнем» или «корневым узлом». Он может считаться первым (или стартовым) узлом. Обратное утверждение, в общем случае, неверно: бесконечные древовидные структуры могут иметь, а могут и не иметь корневые узлы.

Линии, связывающие элементы называются «ветвями», а сами элементы называются узлами. Узлы без потомков называются «конечными узлами» или «листьями».

Названия связей между узлами именуются по принципу семейных взаимосвязей. На Западе в области информатики, в основном используются только названия членов семьи мужского рода, в русском языке для обозначения узла, напрямую связанного с узлом-родителем и находящимся в иерархии ниже, часто называют «дочерним». В лингвистике (англоязычной, к примеру), напротив, используются названия членов семей женского рода. Это свидетельствует о возврате к соглашению об общепринятых правилах наименования, авторами которого студентки известного американского лингвиста Ноама Хомского. Несмотря на это, в информатике нейтральные названия «родитель» и «дитя» часто заменяются словами «отец» и «сын», кроме того термин «дядя» не менее активно используется для обозначения других узлов, находящихся на том же уровне, что и родитель.

  • Узел является «родителем» другого узла, если он расположен на один шаг выше в иерархии дерева, то есть находится ближе к корневому узлу.
  • «Дети» («брат» или «сестра») имеют общий родительский узел.
  • Узел, связанный со всеми нижележащими узлами называется «предком» или «предшественником».

В приведенном выше примере, «энциклопедия» является родителем по отношению к «науке» и «культуре», которые соответственно, являются ее «детьми». «Искусство» и «ремесло» являются братьями по отношению друг к другу и детьми по отношению к «культуре».

Древовидные структуры используются для отображения все видов информации из области таксономии, как например, генеалогическое древо, филогенетическое дерево, грамматическая структура языка (например, в английском языке, хорошим примером является схема S → NP VP, означающая, что предложение (sentence) является именной группой (noun phrase) и глагольной группой (verb phrase), способ логического упорядочивания веб-страниц на сайте и так далее.

В древовидной структуре может быть один и только один путь от одной точки до другой точки.

Древовидные структуры широко используются в информатике (смотри Дерево (структура данных) и Связь (техника)).

Древовидные структуры по видам связей

Межды узлами древовидной структуры могут иметь место различные семантические отношения.

  • В приведённом выше примере-это принадлежность к какой-либо сфере деятельности (отношения Целое-Часть). К такому же типу относятся спецификации использующиеся в технике для описания состава устройства.
  • Хорошо известны древовидные структуры, классифицирующие множества объектов (отношения Общее-Частное) классификации живых существ, звёзд, химических элементов и т. п.
  • Если связи соответствуют временным отношениям образуются такие древовидные структуры как Геохронологическая шкала или родословные деревья (генеалогическое древо).

В реальных энциклопедиях (Википедия) все такие ДС существуют в антагонизме, если не продумана система их представления в отдельности и в целом.

Древовидные структуры с различными видами связей

В структуре тематически однородных групп статей Википедии использованы различные виды связей.Первоночально выделены разделы различающиеся по времени появления объектов статей (Неживая природа,Живая природа,Человечество,Техносфера),затем используются связи между структурными уровнями внутри разделов,связи между однородными статьями (родо-видовые),последними в иерархии используется количество статей в группе.

Древовидные структуры образованные различными семантическими отношениями могут быть связаны в пирамидальные структуры.Пирамидальные информационные структуры (ПИС) в Интернете.

Примеры древовидных структур

представление деревьев

Существует множество способов графического представления древовидных структур. В подавляющем большинстве случаев они сводятся к различным вариациям или комбинациям нескольких основных стилей:

  • Классическая диаграмма со связями между узлами, связывающие попарно узлы при помощи линейных отрезков:
        энциклопедия
          /      \
      наука    культура
                /   \
         искусство  ремесло
  • Вложенные множества, использующие вложенность друг в друга для обозначения связи «родитель-ребенок» (интересную разновидность подобного способа смотри здесь: Treemaps):
      +-------энциклопедия--------+
      |       +------культура---+ |
      | наука |искусство ремесло| |
      |       +-----------------+ |
      +---------------------------+
  • Многоуровневая диаграмма-«сосулька», использующая отношения расположения и соседства:
      +---------------------------+
      |      энциклопедия         |
      +---------+-----------------+
      |  наука  |     культура    |
      +---------+---------+-------+
                |искусство|ремесло|
                +---------+-------+
  • Диаграммы, использующие отступы, иногда называемые «схемами» или «представлениями деревьев»:
      энциклопедия
         наука
         культура
            искусство
            ремесло
  • Вложенные скобки, впервые предложенные для этого применения сэром Артуром Кэли
(наука,(искусство,ремесло)культура)энциклопедия

Описания некоторых базовых способов можно найти в:

  • Бертен, Жак, Sémiologie graphique, 1967, Éditions Gauthier-Villars, Paris (2nd edition 1973, English translation 1983);
  • Кнут, Дональд Эрвин, Искусство программирования, Volume I: Fundamental Algorithms, 1968, Addison-Wesley, pp. 309—310;
  • Брайан Джонсон и Бен Шнейдерман, Tree-maps: A space-filling approach to the visualization of hierarchical information structures, in Proceedings of IEEE Visualization (VIS), 1991, pp. 284—291;
  • Peter Eades, Tao Lin, and Xuemin Lin, Two Tree Drawing Conventions, International Journal of Computational Geometry and Applications, 1993, volume 3, number 2, pp. 133—153.


См. также

Виды деревьев
Связанные статьи

Дополнительные источники

Ссылки

  1. Что такое Document Object Model? (html). W3C Architecture domain. Архивировано из первоисточника 20 февраля 2012. Проверено 5 декабря 2006.



Wikimedia Foundation. 2010.

Смотреть что такое "Древовидная структура" в других словарях:

  • древовидная структура — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN tree like structurewindow tree …   Справочник технического переводчика

  • древовидная структура — medžio struktūra statusas T sritis automatika atitikmenys: angl. tree structure vok. baumförmige Struktur, f; Baumstruktur, f rus. древовидная структура, f pranc. arborescence, f; structure arborescente, f …   Automatikos terminų žodynas

  • древовидная структура сети — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN tree structured architecture …   Справочник технического переводчика

  • звеньевая древовидная структура коммутационного поля коммутационного блока (станции) — Структура, при которой в коммутационном поле коммутационного блока (станции) от одного входа к любому выходу имеется не более одного соединительного пути. [ГОСТ 19472 88] Тематики телефонные сети …   Справочник технического переводчика

  • Звеньевая древовидная структура коммутационного поля коммутационного блока (станции) — 115 . Звеньевая древовидная структура коммутационного поля коммутационного блока (станции) Структура, при которой в коммутационном поле коммутационного блока (станции) от одного входа к любому выходу имеется не более одного соединительного пути… …   Словарь-справочник терминов нормативно-технической документации

  • структура — (framework): Логическая структура для классификации и организации сложной информации [3]. Источник: ГОСТ Р ИСО/ТС 18308 2008: Информатизация здоровья. Требования к архитектуре электронного учета здоровья 3.38 стру …   Словарь-справочник терминов нормативно-технической документации

  • Структура коммутационного поля коммутационного блока звеньевая — 113 Источник: ГОСТ 19472 88: Система автоматизированной телефонной связи общегосударственная. Термины и определения …   Словарь-справочник терминов нормативно-технической документации

  • Структура коммутационного поля коммутационной станции звеньевая — 113 Источник: ГОСТ 19472 88: Система автоматизированной телефонной связи общегосударственная. Термины и определения …   Словарь-справочник терминов нормативно-технической документации

  • СТРУКТУРА РУД ДРЕВОВИДНАЯ — син. термина структура руд дендритовая. Геологический словарь: в 2 х томах. М.: Недра. Под редакцией К. Н. Паффенгольца и др.. 1978 …   Геологическая энциклопедия

  • Структура коммутационного поля коммутационного блока звеньевая древовидная — 115 Источник: ГОСТ 19472 88: Система автоматизированной телефонной связи общегосударственная. Термины и определения …   Словарь-справочник терминов нормативно-технической документации


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»