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

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

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

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

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


Терминология и свойства[править | править вики-текст]

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

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

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

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

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

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

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

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

Древовидные структуры по видам связей[править | править вики-текст]

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

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

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

Древовидные структуры с различными видами связей[править | править вики-текст]

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

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

Примеры древовидных структур[править | править вики-текст]

Представление деревьев[править | править вики-текст]

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

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

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

См. также[править | править вики-текст]

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

Дополнительные источники[править | править вики-текст]

Ссылки[править | править вики-текст]