WikiSort.ru - Программирование

Древовидная структура является одним из способов представления иерархической структуры в графическом виде.

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

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

Ациклический ориентированный граф без жесткого условия связывания называется сетью, Несвязанный граф из нескольких деревьев - лесом..

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

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

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

Обратное утверждение, в общем случае, неверно: бесконечные древовидные структуры могут иметь, а могут и не иметь корневые узлы.

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

Названия связей между узлами именуются по принципу семейных взаимосвязей.

На Западе в области информатики, в основном используются только названия членов семьи мужского рода, в русском языке для обозначения узла, напрямую связанного с узлом-родителем и находящимся в иерархии ниже, часто называют «дочерним».

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

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

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

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

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

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

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

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

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

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

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

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

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

• Интернет: Группа новостей, логическая структура DOM^[1], индексация Yahoo!, Open Directory Project
• Управление информацией: десятичная классификация Дьюи
• Управление: иерархически организованные структуры
• Информатика: двоичное дерево поиска, Красно-чёрное дерево, АВЛ-дерево
• Биология: филогенетическое дерево
• Бизнес: финансовая пирамида
• Управление проектами: структура декомпозиции работ
• Гомология, характеризующаяся древовидным формированием рядов в различных научных областях
• Лингвистика (синтаксис): дерево структуры фразы
• Спорт: Деловые шахматы

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

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

• Классическая диаграмма со связями между узлами, связывающие попарно узлы при помощи линейных отрезков:

        энциклопедия
          /      \
      наука    культура
                /   \
         искусство  ремесло

• Вложенные множества, использующие вложенность друг в друга для обозначения связи «родитель-ребёнок» (интересную разновидность подобного способа смотри здесь: 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.

См. также

Виды деревьев

• B-дерево
• Пляшущее дерево
• Дерево (структура данных)
• Дерево (теория графов)
• Дерево (теория множеств)
• Дерево (описательная теория множеств)

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

• Обработка данных
• Иерархия

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

• Визуализация филогенетических деревьев на сервере T-REX
• Использование древовидных структур для разработки бизнес-процессов — от Society for Technical Communication
• Древовидная иерархия категорий и страниц в разделе Вычислений в Википедии (недоступная ссылка)
• Карта рынка — древовидный вариант визуализации поведения фондового рынка

Ссылки

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Исправить статью согласно стилистическим правилам Википедии.