Древовидная структура
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Июль 2014 г. ) |
Древовидная структура , древовидная диаграмма или древовидная модель — это способ представления иерархической природы структуры в графической форме. Она называется «деревовидной структурой», потому что классическое представление напоминает дерево , хотя диаграмма обычно перевернута по сравнению с биологическим деревом, со «стеблем» вверху и «листьями» внизу.
Древовидная структура является концептуальной и существует в нескольких формах. Обсуждение древовидных структур в конкретных областях см. в разделе « Дерево (структура данных) для информатики»; поскольку это относится к теории графов, см. дерево (теория графов) или дерево (теория множеств) . Другие статьи по теме перечислены ниже.
Терминология и свойства [ править ]
Элементы дерева называются « узлами ». Линии, соединяющие элементы, называются «ветвями». Узлы без дочерних узлов называются листовыми узлами , «конечными узлами» или «листьями».
В каждой конечной древовидной структуре есть член, у которого нет старшего элемента . Этот член называется «корнем» или корневым узлом . Корень — это начальный узел. Но обратное неверно: бесконечные древовидные структуры могут иметь или не иметь корневой узел.
Имена отношений между узлами моделируют терминологию родства семейных отношений. Гендерно-нейтральные имена «родитель» и «ребенок» в значительной степени вытеснили старую терминологию «отец» и «сын». Термин «дядя» до сих пор широко используется для других узлов на том же уровне, что и родительский, хотя иногда его заменяют гендерно-нейтральными терминами, такими как «оммер». [1]
- «Родителем» узла является узел, расположенный на одну ступень выше в иерархии (т.е. ближе к корневому узлу) и лежащий на той же ветке.
- «Родственные» узлы («брат» или «сестра») используют один и тот же родительский узел.
- «Дяди» узла (иногда «оммеры») являются братьями и сестрами родителя этого узла.
- Узел, который связан со всеми узлами более низкого уровня, называется «предком». Подключенные узлы нижнего уровня являются «потомками» узла-предка.
В примере «энциклопедия» является родителем «науки» и «культуры», их дочерними элементами. «Искусство» и «ремесло» — братья и сестры и дети «культуры», которая является их родителем и, следовательно, одним из их предков. Также «энциклопедия», как корень дерева, является прародительницей «науки», «культуры», «искусства» и «ремесла». Наконец, «наука», «искусство» и «ремесло», как и листья, не являются предками никакого другого узла.
Древовидные структуры могут отображать все виды таксономических знаний, такие как генеалогические деревья , биологическое эволюционное дерево , эволюционное дерево языковой семьи , грамматическую структуру языка (ключевым примером является S → NP VP, что означает, что предложение является существительным). фраза и глагольная фраза, каждая из которых, в свою очередь, имеет другие компоненты, которые имеют другие компоненты), способ логического упорядочения веб-страниц на веб-сайте, математические деревья наборов целых чисел и так далее.
В Оксфордском словаре английского языка зафиксировано использование терминов «деревовидная структура» и «деревовидная диаграмма» с 1965 года в книге Ноама Хомского « Аспекты теории синтаксиса» . [2]
В древовидной структуре существует один и только один путь из любой точки в любую другую точку.
Информатика широко использует древовидные структуры ( см. Дерево (структура данных) и телекоммуникации ).
Формальное определение см. в теории множеств , а обобщение, в котором дети не обязательно являются наследниками, см. в порядке префиксов .
Примеры древовидных структур [ править ]
- Интернет:
- Вакуумные трубки
- объектной модели документа , Логическая структура [3] Yahoo! предметный указатель, Керли
- Операционная система : структура каталогов
- Управление информацией: Десятичная система Дьюи , PSH , это иерархический маркированный список.
- Управление: иерархические организационные структуры.
- Информатика:
- Биология: эволюционное древо
- Бизнес: пирамидальная схема продаж
- Управление проектом: структура декомпозиции работ
- Лингвистика:
- (Синтаксис) Деревья структуры фраз
- (Историческая лингвистика) Древовидная модель изменения языка
- Спорт: деловые шахматы , сетка плей-офф.
- Математика: Вселенная фон Неймана
- Теория групп: деревья-потомки
Представление деревьев [ править ]
Существует множество способов визуального представления древовидных структур. Почти всегда они сводятся к вариациям или комбинациям. из нескольких основных стилей:
Классические диаграммы связей между узлами [ править ]
Классические диаграммы узлов-связей, соединяющие узлы вместе отрезками линий:
| энциклопедия | ||
|---|---|---|
| / культура |
\ наука | |
| / искусство |
\ ремесло | |
Вложенные наборы [ править ]
Вложенные наборы , в которых используется вложение или сдерживание для отображения родительского статуса; примеры включают TreeMaps , фрактальные карты и диаграммы Эйлера :
|
энциклопедия | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
| ||||||||||
| |||||||||||
Многослойные диаграммы «сосульки» [ править ]
Многослойные диаграммы «сосульки», в которых используется выравнивание/смежность.
| энциклопедия | ||
|---|---|---|
| культура | наука | |
| искусство | ремесло | |
Контуры и древовидное представление [ править ]
Списки или диаграммы, в которых используются отступы, иногда называемые « контурами » или « деревовидными представлениями ».
Схема:
- энциклопедия
- культура
- искусство
- ремесло
- наука
- культура
Вид дерева:
- энциклопедия
- культура
- искусство
- ремесло
- наука
- культура
Вложенные скобки [ править ]
Соответствие вложенным скобкам впервые заметил сэр Артур Кэли :
((искусство, ремесло)культура,наука)энциклопедия
или
энциклопедия(культура(искусство,ремесло),наука)
Радиальные деревья [ править ]
Деревья также могут быть представлены радиально :
| искусство \ |
ремесло / |
|---|---|
| культура | | |
| энциклопедия | |
| | наука | |
См. также [ править ]
- Виды деревьев
- B-дерево
- Танцующее дерево
- Древо решений
- Бинарное дерево левого дочернего элемента и правого родственного элемента
- Порфировое дерево
- Дерево (структура данных)
- Дерево (теория графов)
- Дерево (теория множеств)
- Статьи по Теме
Ссылки [ править ]
- ^ «Глоссарий Эфириума» . Гитхаб . Архивировано из оригинала 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 .
Внешние ссылки [ править ]
