Дерева як особливий вид графів

2.1 Основні компоненти дерева

Дерево — це спеціальний вид графа, який є ациклічним і зв'язним. У дереві існує єдиний шлях між будь-якою парою вузлів, що робить його структуру ієрархічною.

Основні компоненти дерева:

1. Вузли:

• Основні елементи дерева, які містять дані.
• Наприклад, кожне коло в діаграмі представляє вузол.

2. Корінь:

• Вузол, який не має батьківських вузлів. Він є початковою точкою дерева.
• Наприклад, верхній вузол у діаграмі.

3. Листя:

• Вузли, які не мають дочірніх вузлів. Вони знаходяться на "кінцях" дерева.
• Наприклад, вузли внизу діаграми.

4. Ребра:

• Зв'язки між вузлами. Визначають батьківсько-дочірні відносини між вузлами.
• Наприклад, лінії, що з'єднують вузли в діаграмі.

5. Піддерева:

• Будь-яка підмножина дерева, яка складається з вузла і всіх його нащадків.
• Наприклад, гілка дерева, що виходить з одного вузла.

Важливі характеристики дерева:

1. Висота дерева:

• Довжина шляху від кореня до найдальшого листа.
• Наприклад, кількість рівнів у діаграмі.

2. Глибина вузла:

• Довжина шляху від кореня до даного вузла.
• Наприклад, кількість рівнів від кореня до конкретного вузла.

2.2 Бінарні дерева

Можна виділити різні види дерев. Почнемо з найпростіших.

Бінарне дерево — це дерево, в якому кожний вузол має не більше двох дочірніх вузлів, які називаються лівим і правим нащадками.

Приклад бінарного дерева:

Особливі види бінарних дерев:

Повне бінарне дерево:

Всі рівні дерева, крім останнього, повністю заповнені, і всі вузли останнього рівня розташовані якомога лівіше.

Ідеальне бінарне дерево:

Всі внутрішні вузли мають рівно два дочірніх вузли, і всі листя знаходяться на одному рівні.

Збалансоване бінарне дерево:

Різниця висот піддерев будь-якого вузла не перевищує 1.

Бінарне дерево пошуку:

Для будь-якого вузла його ліве піддерево містить тільки вузли з меншими значеннями, а праве піддерево – тільки вузли з більшими значеннями.

2.3 n-арні дерева

n-арне дерево – це дерево, в якому кожен вузол може мати не більше n дочірніх вузлів.

Особливі види n-арних дерев:

1. Тернарне дерево (Ternary Tree):

Кожен вузол має не більше трьох дочірніх вузлів.

2. K-арне дерево (k-ary Tree):

Кожен вузол має не більше k дочірніх вузлів.

Приклад 3-арного дерева (кожен вузол має не більше трьох дочірніх вузлів):

2.4 Приклади використання дерев

1. Файлова система

Застосування дерев: Представлення ієрархічної структури файлів і папок в операційній системі.

Кореневий вузол представляє кореневу директорію, внутрішні вузли — папки, а листя — файли. Операції включають створення, видалення і переміщення файлів і папок.

2. Дерево рішень

Застосування дерев: Аналітика і машинне навчання для прийняття рішень.

Внутрішні вузли представляють питання або умови, гілки — можливі відповіді, а листя — кінцеві рішення або дії. Наприклад, діагностика захворювань в медицині на основі симптомів.

3. XML/HTML документ

Застосування дерев: Структуроване представлення даних у форматі XML або HTML.

Кореневий вузол представляє весь документ, внутрішні вузли — теги і елементи, а листя — текстові вузли і атрибути. Це допомагає у парсингу і маніпулюванні вмістом документів.

4. Організаційна структура

Застосування дерев: Представлення ієрархії в організаціях і компаніях.

Кореневий вузол представляє генерального директора, внутрішні вузли — менеджерів і відділи, а листя — співробітників. Це допомагає візуалізувати і керувати організаційною структурою.

5. Гра в шахи

Застосування дерев: Представлення можливих ходів у грі.

Кореневий вузол представляє початковий стан гри, внутрішні вузли — можливі ходи, а листя — кінцеві стани гри. Це допомагає у плануванні стратегій і прийнятті рішень у шахових програмах.