Задача поиска. Деревья бинарного поиска (ДБП). Операции над ними.
Бинарное дерево поиска – это бинарное упорядоченное дерево, у которого каждой вершине приписан уникальный ключ поиска, причем выполнено соотношение: ключи (всех) вершин левого поддерева < ключ родителя < ключи (всех) вершин правого поддерева. Отметим, что ключи в вершинах такого дерева расположены по возрастанию в соответствии с инфиксным (внутренним) обходом. Отметим особенность (геометрического характера) таких деревьев – у вершин такого бинарного дерева допускается наличие правого сына при отсутствии левого, т.е. фиксируется не просто порядок на множестве дочерних вершин, но и их позиция (даже если позиция левого свободна). Хотя, с другой стороны, эту ситуацию можно трактовать как наличие двух детей, из которых левый – «пустой» (фиктивный). Для таких деревьев время поиска по ключу ≤ O(h), где h – высота дерева. Но при вставке новых вершин (с ключами) могут появляться длинные ветви, поэтому для времени поиска верхняя оценка в худшем O(n), где n – количество вершин в дереве. Статистический анализ показывает, что для бинарных поисковых деревьев с n вершинами оценка высоты в среднем O(log(n)) и она такая же для операций поиска, вставки, удаления и min с множествами мощности n. Поэтому бинарное дерево поиска хороший вариант для представления АТД «Множество», «Словарь» и «Очередь с приоритетом», но эффективна такая реализация только в среднем, т.е. только в среде, в которой случающиеся задержки выполнения операций некритичны, если общее время работы программы длительное и приемлемое для обрабатываемого объема входного потока.
Базовый интерфейс двоичного дерева поиска состоит из трех операций:
FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
INSERT(K,V) — добавление в дерево пары (key, value) = (K, V).
REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.
Операции:
-Поиск элемента (FIND)
Дано: дерево Т и ключ K.
Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.
Алгоритм:
Если дерево пусто, сообщить, что узел не найден, и остановиться.
Иначе сравнить K со значением ключа корневого узла X.
Если K=X, выдать ссылку на этот узел и остановиться.
Если K>X, рекурсивно искать ключ K в правом поддереве Т.
Если K<X, рекурсивно искать ключ K в левом поддереве Т.
-Добавление элемента (INSERT)
Дано: дерево Т и пара (K,V).
Задача: добавить пару (K, V) в дерево Т.
Алгоритм:
Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.
Иначе сравнить K с ключом корневого узла X.
Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.
-Удаление узла (REMOVE)
Дано: дерево Т с корнем n и ключом K.
Задача: удалить из дерева Т узел с ключом K (если такой есть).
Алгоритм:
Если дерево T пусто, остановиться;
Иначе сравнить K с ключом X корневого узла n.
Если K>X, рекурсивно удалить K из правого поддерева Т;
Если K<X, рекурсивно удалить K из левого поддерева Т;
Если K=X, то необходимо рассмотреть три случая.
Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
Если оба ребёнка присутствуют, то найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n); скопируем данные (кроме ссылок на дочерние элементы) из m в n; рекурсивно удалим узел m.
-Обход дерева (TRAVERSE)
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов. Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f. Эта функция обычно работает только с парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.
INFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
PREFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
POSTFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).
INFIX_TRAVERSE:
Дано: дерево Т и функция f
Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей
Алгоритм:
Если дерево пусто, остановиться.
Иначе
Рекурсивно обойти левое поддерево Т.
Применить функцию f к корневому узлу.
Рекурсивно обойти правое поддерево Т.
В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.-Разбиение дерева по ключу
Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами <K0 и ≥K0.-Объединение двух деревьев в одно
Обратная операция: есть два дерева поиска, у одного ключи <K0, у другого ≥K0. Объединить их в одно дерево.У нас есть два дерева: T1 (меньшее) и T2 (большее). Сначала нужно решить, откуда взять корень: из T1 или T2. Стандартного метода нет, возможные варианты:
Взять наугадЕсли в каждом узле дерева поддерживается размер всей ветви (см. дерево с неявным ключом), легко можно оценить дисбаланс для того и другого варианта.
алг ОбъединениеДеревьев(T1, T2)
если T1 пустое, вернуть T2
если T2 пустое, вернуть T1
если решили сделать корнем T1, то
T = ОбъединениеДеревьев(T1.правое, T2)
T1.правое = T
вернуть T1
иначе
T = ОбъединениеДеревьев(T1, T2.левое)
T2.левое = T
вернуть T2