2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира — Подготовка к ЕГЭ/ОГЭ и сессии СПО и ВУЗы

Основные понятия деревьев

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

Основные термины:

Корень — начальный узел дерева (не имеет предков)
Лист — узел, не имеющий потомков
Внутренний узел — узел, имеющий хотя бы одного потомка
Ребро — связь между узлами
Высота дерева — длина самого длинного пути от корня до листа
Глубина узла — длина пути от корня до этого узла

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

Файловая система компьютера
Структура HTML-документа (DOM)
Организационная структура компании
Генеалогическое древо

Бинарное дерево

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

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

Каждый узел имеет 0, 1 или 2 потомка
Левый потомок обычно содержит значения меньше родителя
Правый потомок обычно содержит значения больше родителя
Идеально сбалансированное бинарное дерево имеет минимальную высоту

Важно: Высота сбалансированного бинарного дерева с n узлами составляет O(log n), что обеспечивает эффективный поиск.

Деревья поиска

Бинарное дерево поиска (BST) — это бинарное дерево, для которого выполняются следующие условия:

Значение в левом поддереве меньше значения в корне
Значение в правом поддереве больше значения в корне
Оба поддерева являются бинарными деревьями поиска

Операции с деревом поиска:

Поиск — O(log n) в сбалансированном дереве
Вставка — добавление нового элемента в правильную позицию
Удаление — удаление элемента с сохранением свойств дерева
Обход — посещение всех узлов в определенном порядке

Важно: В несбалансированном дереве производительность операций может деградировать до O(n).

Способы обхода дерева

Существует три основных способа обхода бинарного дерева:

Прямой обход (Pre-order)

Корень → Левое поддерево → Правое поддерево

                            PreOrder(node):

                              if node != null:

                                print(node.value)

                                PreOrder(node.left)

                                PreOrder(node.right)

Результат: 8, 5, 3, 7, 10, 9, 12

Центральный обход (In-order)

Левое поддерево → Корень → Правое поддерево

                            InOrder(node):

                              if node != null:

                                InOrder(node.left)

                                print(node.value)

                                InOrder(node.right)

Результат: 3, 5, 7, 8, 9, 10, 12

Обратный обход (Post-order)

Левое поддерево → Правое поддерево → Корень

                            PostOrder(node):

                              if node != null:

                                PostOrder(node.left)

                                PostOrder(node.right)

                                print(node.value)

Результат: 3, 7, 5, 9, 12, 10, 8

Представление арифметических выражений в виде дерева

Арифметические выражения могут быть представлены в виде бинарных деревьев, где:

Листья содержат операнды (числа или переменные)
Внутренние узлы содержат операторы (+, -, *, /)
Вычисление выражения происходит снизу вверх

Пример: Выражение (5 + 3) * (10 — 2)

Вычисление выражения происходит следующим образом:

Вычисляем левое поддерево: 5 + 3 = 8
Вычисляем правое поддерево: 10 — 2 = 8
Вычисляем корень: 8 * 8 = 64

                    // Представление выражения в коде

                    class Node {

                      constructor(value, left = null, right = null) {

                        this.value = value;

                        this.left = left;

                        this.right = right;

                      }

                    }

                    // Построение дерева для (5 + 3) * (10 — 2)

                    const tree = new Node(‘*’,

                      new Node(‘+’, new Node(‘5’), new Node(‘3’)),

                      new Node(‘-‘, new Node(’10’), new Node(‘2’))

                    );

Использование деревьев и графов в окружающем мире

Деревья и графы широко применяются для моделирования различных объектов и процессов:

Область применения	Пример	Тип структуры
Компьютерные сети	Топология сети, маршрутизация	Граф
Базы данных	Индексы, иерархические данные	B-деревья, деревья поиска
Искусственный интеллект	Деревья решений, нейронные сети	Деревья, графы
Лингвистика	Синтаксический анализ предложений	Деревья разбора
Биология	Филогенетические деревья	Деревья
Социальные сети	Граф друзей, рекомендации	Граф
Файловые системы	Иерархия папок и файлов	Дерево

Пример: Файловая система

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

Важно: Понимание деревьев и графов необходимо для решения многих практических задач в программировании и компьютерных науках.

Деревья: структуры данных и их применение