Деревья как особый вид графов

Видео на Vimeo

---

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

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

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

1. Узлы:

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

2. Корень:

• Узел, который не имеет родительских узлов. Он является начальной точкой дерева.
• Например, верхний узел в диаграмме.

3. Листья:

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

4. Рёбра:

• Связи между узлами. Определяют родительско-дочерние отношения между узлами.
• Например, линии, соединяющие узлы в диаграмме.

5. Поддеревья:

• Любое подмножество дерева, состоящее из узла и всех его потомков.
• Например, ветвь дерева, исходящая из одного узла.

Важные характеристики дерева:

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

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

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

• Длина пути от корня до данного узла.
• Например, количество уровней от корня до конкретного узла.

2.2 Бинарные деревья

Можно выделить различные виды деревьев. Начнём с самых простых.

Бинарное дерево — это дерево, в котором каждый узел имеет не более двух дочерних узлов, называемых левым и правым потомками.

Пример бинарного дерева:

Особые виды бинарных деревьев:

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

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

Совершенное бинарное дерево:

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

Сбалансированное бинарное дерево:

Разница высот поддеревьев любого узла не превышает 1.

Бинарное дерево поиска:

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

2.3 n-арные деревья

n-арное дерево – это дерево, в котором каждый узел может иметь не более n дочерних узлов.

Особые виды n-арных деревьев:

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

Каждый узел имеет не более трёх дочерних узлов.

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

Каждый узел имеет не более k дочерних узлов.

Пример 3-арного дерева (каждый узел имеет не более трёх дочерних узлов):

2.4 Примеры использования деревьев

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

Применение деревьев: Представление иерархической структуры файлов и папок в операционной системе.

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

2. Дерево решений

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

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

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

Применение деревьев: Структурированное представление данных в формате XML или HTML.

Корневой узел представляет весь документ, внутренние узлы — теги и элементы, а листья — текстовые узлы и атрибуты. Это помогает в парсинге и манипулировании содержимым документов.

4. Организационная структура

Применение деревьев: Представление иерархии в организациях и компаниях.

Корневой узел представляет генерального директора, внутренние узлы — менеджеров и отделы, а листья — сотрудников. Это помогает визуализировать и управлять организационной структурой.

5. Игра в шахматы

Применение деревьев: Представление возможных ходов в игре.

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