деревоподібна структура
Термінологія і властивості
Кожна кінцева деревоподібна структура містить елемент, який не має вищого. Цей елемент називається «коренем» або «кореневим вузлом». Він може вважатися першим (або стартовим) вузлом.
Протилежне твердження, в загальному випадку, не так: нескінченні деревовидні структури можуть мати, а можуть і не мати кореневі вузли.
Лінії, що зв'язують елементи називаються «гілками», а самі елементи називаються вузлами. Вузли без нащадків називаються «кінцевими вузлами» або «листям».
Назви зв'язків між вузлами іменуються за принципом сімейних взаємозв'язків.
На Заході в галузі інформатики, в основному використовуються тільки назви членів сім'ї чоловічого роду, в українській мові для позначення вузла, безпосередньо пов'язаного з вузлом-батьком і знаходиться в ієрархії нижче, часто називають «дочірнім».
- Вузол є «батьком» іншого вузла, якщо він розташований на один крок вище в ієрархії дерева, тобто знаходиться ближче до кореневого вузла.
- «Діти» ( «брат» або «сестра») мають загальний батьківський вузол.
- Вузол, пов'язаний з усіма нижележащими вузлами називається «предком» або «попередником».
У наведеному вище прикладі, «енциклопедія» є батьком по відношенню до «науці» і «культурі», які відповідно, є її «дітьми». «Мистецтво» і «ремесло» є братами по відношенню один до одного і дітьми по відношенню до «культурі».
Деревовидні структури використовуються для відображення усіх видів інформації з області таксономії. як наприклад, генеалогічне древо. філіпченкове дерево. граматична структура мови (наприклад, в англійській мові, хорошим прикладом є схема S → NP VP, що означає, що пропозиція (sentence) є іменний групою (noun phrase) і дієслівної групою (verb phrase), спосіб логічного упорядкування веб-сторінок на сайті і так далі.
У структурі дерева може бути один і тільки один шлях від однієї точки до іншої точки.
Деревовидні структури за видами зв'язків
Між вузлами деревовидної структури можуть мати місце різні семантичні відносини.
- У наведеному вище прикладі-це приналежність до якої-небудь сфері діяльності (відносини Ціле-Частина). До такого ж типу відносяться специфікації використовуються в техніці для опису складу пристрою.
- Добре відомі деревовидні структури, що класифікують безлічі об'єктів (відносини Загальна-Приватне) класифікації живих істот. зірок, хімічних елементів і т. п.
- Якщо зв'язку відповідають часових відносин утворюються такі деревовидні структури як геохронологічна шкала або родовідні дерева (генеалогічне древо).
У реальних енциклопедіях (Вікіпедія) всі такі ДС існують в антагонізмі, якщо не продумана система їх подання окремо і в цілому.
Деревовидні структури з різними видами зв'язків
Деревовидні структури утворені різними семантичними відносинами можуть бути пов'язані в пірамідальні структури.Пірамідальние інформаційні структури (ПІС) в Інтернеті.
Приклади деревовидних структур
Існує безліч способів графічного представлення деревовидних структур. У переважній більшості випадків вони зводяться до різних варіацій або комбінаціям декількох основних стилів:
- Класична діаграма зі зв'язками між вузлами, що зв'язують попарно вузли за допомогою лінійних відрізків:
- Вкладені безлічі, що використовують вкладеність один в одного для позначення зв'язку «батько-дитина» (цікаву різновид подібного способу дивись тут: Treemaps):
- Багаторівнева діаграмма- «бурулька», яка використовує відносини розташування і сусідства:
- Діаграми, що використовують відступи, іноді звані «схемами» або «уявленнями дерев»:
- Вкладені дужки, вперше запропоновані для цього застосування сером Артуром Келі
Описи деяких базових способів можна знайти в: