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

, Древовидная структура древовидная диаграмма древовидная модель — это способ представления иерархической природы структуры или в графической форме. Она называется «деревовидной структурой», потому что классическое представление напоминает дерево , хотя диаграмма обычно перевернута по сравнению с биологическим деревом, со «стеблем» вверху и «листьями» внизу.

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

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

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

В каждой конечной древовидной структуре есть член, у которого нет старшего элемента . Этот член называется «корнем» или корневым узлом . Корень — это начальный узел. Но обратное неверно: бесконечные древовидные структуры могут иметь или не иметь корневой узел.

Имена отношений между узлами моделируют терминологию родства семейных отношений. Гендерно-нейтральные имена «родитель» и «ребенок» в значительной степени вытеснили старую терминологию «отец» и «сын». Термин «дядя» до сих пор широко используется для других узлов на том же уровне, что и родительский, хотя иногда его заменяют гендерно-нейтральными терминами, такими как «оммер». ^[1]

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

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

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

Оксфордский словарь английского языка записывает использование терминов «деревовидная структура» и «древовидная диаграмма» с 1965 года в книге Ноама Хомского « Аспекты теории синтаксиса» . ^[2]

В древовидной структуре существует один и только один путь из любой точки в любую другую точку.

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

Формальное определение см. в теории множеств , а обобщение, в котором дети не обязательно являются преемниками, см. в порядке префиксов .

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

информационная диаграмма в форме дерева, иллюстрирующая «эволюцию» термоэмиссионных трубок (разновидность электронных ламп) между 1883 и 1934 годами.

Интернет:
- иерархия сети Usenet
Вакуумные трубки
- объектной модели документа , Логическая структура ^[3] Yahoo! предметный указатель, Керли
Операционная система : структура каталогов
Управление информацией: Десятичная система Дьюи , PSH , это иерархический маркированный список.
Управление: иерархические организационные структуры .
Информатика:
Биология: эволюционное древо
Бизнес: пирамидальная схема продаж
Управление проектом: структура декомпозиции работ
Лингвистика:
- (Синтаксис) Деревья структуры фраз
- (Историческая лингвистика) Древовидная модель изменения языка
Спорт: деловые шахматы , сетка плей-офф.
Математика: Вселенная фон Неймана
Теория групп: деревья-потомки

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

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

Классические диаграммы узловых связей

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

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

Вложенные наборы

Вложенные наборы , в которых используется вложение или сдерживание для отображения родительского статуса; примеры включают TreeMaps , фрактальные карты и диаграммы Эйлера :

энциклопедия

	культура
	культура
художественное ремесло

наука

Многослойные диаграммы «сосульки»

Многослойные диаграммы «сосульки», в которых используется выравнивание/смежность.

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

Контуры и виды в виде дерева

Списки или диаграммы, в которых используются отступы, иногда называемые « контурами » или « деревовидными представлениями ».

Схема:

энциклопедия

культура

искусство

ремесло

наука

Вид дерева:

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

Вложенные круглые скобки

Соответствие вложенным скобкам впервые заметил сэр Артур Кэли :

((искусство, ремесло)культура,наука)энциклопедия
или
энциклопедия(культура(искусство,ремесло),наука)

Радиальные деревья

Деревья также могут быть представлены радиально :

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

См. также

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

Похожие статьи

Ссылки

^ «Глоссарий Эфириума» . Гитхаб . Архивировано из оригинала 25 апреля 2019 года . Проверено 17 апреля 2019 г.
^ "дерево" . Оксфордский словарь английского языка (онлайн-изд.). Издательство Оксфордского университета . (Требуется подписка или членство участвующей организации .)
^ «Что такое объектная модель документа?» . Домен архитектуры W3C . Архивировано из оригинала 12 февраля 2012 г. Проверено 5 декабря 2006 г.

Дальнейшее чтение

Определение некоторых основных стилей древовидных структур можно найти в:

Жак Бертен , Семиология графики , 1983, University of Wisconsin Press (2-е издание, 1973 г., ISBN 978-0299090609 ;
Дональд Э. Кнут (1968). Искусство компьютерного программирования . Том 1: Фундаментальные алгоритмы. Аддисон-Уэсли. стр. 309–310.
Брайан Джонсон и Бен Шнейдерман , « Древовидные карты: подход к визуализации иерархических информационных структур, заполняющий пространство », в Proceedings of IEEE Visualization (VIS) , 1991, стр. 284–291, ISBN 0-8186-2245-8 ;
Питер Идс , Тао Линь и Сюэмин Линь, «Два соглашения о рисовании деревьев», Международный журнал вычислительной геометрии и приложений , 1993, том 3, номер 2, стр. 133–153.
Мануэль Лима (2014). Книга деревьев: визуализация отраслей знаний (1-е изд.). Нью-Йорк: Princeton Architectural Press. ISBN 978-1-616-89218-0 .

Внешние ссылки

[1] «Глоссарий Эфириума» . Гитхаб . Архивировано из оригинала 25 апреля 2019 года . Проверено 17 апреля 2019 г.

[2] "дерево" . Оксфордский словарь английского языка (онлайн-изд.). Издательство Оксфордского университета . (Требуется подписка или членство участвующей организации .)

[3] «Что такое объектная модель документа?» . Домен архитектуры W3C . Архивировано из оригинала 12 февраля 2012 г. Проверено 5 декабря 2006 г.

[1]

[2]

[3]