Бинарные деревья поиска

3.1 Определение бинарного дерева поиска (BST)

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

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

Пример BST:

BST – это сокращение от Binary Search Tree – буквально «Бинарное дерево поиска». Фактически это организация данных в виде «дерева», по которому можно очень быстро искать. Структура дерева – это фактически скрытая/хитрая сортировка элементов.

Обход центрированный (in-order traversal)

Задача обхода — определённым образом сформировать список узлов (или данных из узлов, вопрос терминологии и имеет значение на практике). Центрированный (симметричный) обход — обход, при котором корень дерева занимает место между результатами соответствующих обходов левого и правого поддеревьев.

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

3.2 Принципы работы и свойства BST

Принципы работы:

• Организация данных: BST организует данные так, чтобы обеспечивать эффективный поиск, вставку и удаление элементов.
• Рекурсивная структура: Каждый узел в BST подчиняется тем же правилам, что и корень дерева, что делает структуру рекурсивной.
• Сбалансированность: Для обеспечения оптимальной производительности BST должно быть сбалансированным, то есть высота левого и правого поддеревьев должна быть примерно одинаковой.

Свойства BST:

• Упорядоченность: В любой момент можно обойти дерево в порядке "in-order" (левое поддерево → текущий узел → правое поддерево), чтобы получить все элементы в отсортированном порядке.
• Время операций:
  • В среднем время выполнения операций поиска, вставки и удаления составляет O(log n), где n — количество узлов.
  • В худшем случае (если дерево не сбалансировано) время выполнения операций может достигать O(n).
• Уникальные ключи: Все ключи в BST должны быть уникальными, чтобы сохранить упорядоченность.

3.3 Основные операции

1. Вставка (Insertion):

Принцип работы:

• Начинаем с корневого узла.
• Сравниваем ключ нового узла с ключом текущего узла.
• Если новый ключ меньше, переходим к левому поддереву, если больше — к правому.
• Повторяем процесс до тех пор, пока не найдём подходящее место для вставки нового узла (либо левый, либо правый потомок отсутствует).

Алгоритм:

1. Если дерево пустое, новый узел становится корневым узлом.
2. Иначе рекурсивно находим правильное место и добавляем новый узел.

2. Удаление (Deletion):

Принцип работы:

• Найти узел для удаления.
• Рассмотреть три случая:
• Узел является листом (не имеет детей): просто удаляем узел.
• Узел имеет одного ребёнка: заменяем узел его ребёнком.
• Узел имеет двух детей: находим наименьший узел в правом поддереве (или наибольший в левом), копируем его значение в удаляемый узел и рекурсивно удаляем наименьший узел в правом поддереве.

Алгоритм:

1. Найти узел с заданным ключом.
2. В зависимости от случая выполнить соответствующее удаление и перераспределение узлов.

3. Поиск (Search):

Принцип работы:

• Начинаем с корневого узла.
• Сравниваем ключ искомого узла с ключом текущего узла.
• Если ключ совпадает, возвращаем узел.
• Если ключ меньше, переходим к левому поддереву, если больше — к правому.
• Повторяем процесс до тех пор, пока не найдём узел с искомым ключом или не достигнем конца дерева (в этом случае узел не найден).

Алгоритм:

1. Если дерево пустое или ключ узла совпадает с искомым, возвращаем узел.
2. Если ключ искомого узла меньше, рекурсивно ищем в левом поддереве.
3. Если ключ искомого узла больше, рекурсивно ищем в правом поддереве.

3.4 Примеры задач, решаемых с использованием BST

1. Поиск элемента в динамическом множестве

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

Решение с использованием BST:

• Вставка новых элементов в дерево.
• Удаление существующих элементов.
• Поиск элементов в дереве.

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

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

2. Нахождение минимального и максимального элемента

Необходимо быстро находить минимальное и максимальное значения в наборе данных.

Решение с использованием BST:

• Минимальный элемент находится в самом левом узле дерева.
• Максимальный элемент находится в самом правом узле дерева.

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

Поддержка системы, отслеживающей цены акций, где необходимо быстро находить минимальную и максимальную цену в текущий момент времени.

3. Проверка баланса выражения

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

Решение с использованием BST:

Используем BST для хранения промежуточных состояний проверки баланса скобок.

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

Парсинг и компиляция кода, где необходимо проверять правильность расстановки скобок в выражениях.

4. Построение словаря

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

Решение с использованием BST:

• Слова добавляются в дерево в алфавитном порядке.
• Поиск слов осуществляется по ключам.

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

Система автокоррекции текста, где необходимо быстро находить и исправлять слова.