деревоподібна структура

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

Кожна кінцева деревоподібна структура містить елемент, який не має вищого. Цей елемент називається «коренем» або «кореневим вузлом». Він може вважатися першим (або стартовим) вузлом.

Протилежне твердження, в загальному випадку, не так: нескінченні деревовидні структури можуть мати, а можуть і не мати кореневі вузли.

Лінії, що зв'язують елементи називаються «гілками», а самі елементи називаються вузлами. Вузли без нащадків називаються «кінцевими вузлами» або «листям».

Назви зв'язків між вузлами іменуються за принципом сімейних взаємозв'язків.

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

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

У наведеному вище прикладі, «енциклопедія» є батьком по відношенню до «науці» і «культурі», які відповідно, є її «дітьми». «Мистецтво» і «ремесло» є братами по відношенню один до одного і дітьми по відношенню до «культурі».

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

У структурі дерева може бути один і тільки один шлях від однієї точки до іншої точки.

Деревовидні структури за видами зв'язків

Між вузлами деревовидної структури можуть мати місце різні семантичні відносини.

  • У наведеному вище прикладі-це приналежність до якої-небудь сфері діяльності (відносини Ціле-Частина). До такого ж типу відносяться специфікації використовуються в техніці для опису складу пристрою.
  • Добре відомі деревовидні структури, що класифікують безлічі об'єктів (відносини Загальна-Приватне) класифікації живих істот. зірок, хімічних елементів і т. п.
  • Якщо зв'язку відповідають часових відносин утворюються такі деревовидні структури як геохронологічна шкала або родовідні дерева (генеалогічне древо).

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

Деревовидні структури з різними видами зв'язків

Деревовидні структури утворені різними семантичними відносинами можуть бути пов'язані в пірамідальні структури.Пірамідальние інформаційні структури (ПІС) в Інтернеті.

Приклади деревовидних структур

Існує безліч способів графічного представлення деревовидних структур. У переважній більшості випадків вони зводяться до різних варіацій або комбінаціям декількох основних стилів:

  • Класична діаграма зі зв'язками між вузлами, що зв'язують попарно вузли за допомогою лінійних відрізків:
  • Вкладені безлічі, що використовують вкладеність один в одного для позначення зв'язку «батько-дитина» (цікаву різновид подібного способу дивись тут: Treemaps):
  • Багаторівнева діаграмма- «бурулька», яка використовує відносини розташування і сусідства:
  • Діаграми, що використовують відступи, іноді звані «схемами» або «уявленнями дерев»:
  • Вкладені дужки, вперше запропоновані для цього застосування сером Артуром Келі

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

Схожі статті