Задача поиска. Деревья бинарного поиска (ДБП). Операции над ними.

Бинарное дерево поиска – это бинарное упорядоченное дерево, у которого каждой вершине приписан уникальный ключ поиска, причем выполнено соотношение: ключи (всех) вершин левого поддерева < ключ родителя < ключи (всех) вершин правого поддерева. Отметим, что ключи в вершинах такого дерева расположены по возрастанию в соответствии с инфиксным (внутренним) обходом. Отметим особенность (геометрического характера) таких деревьев – у вершин такого бинарного дерева допускается наличие правого сына при отсутствии левого, т.е. фиксируется не просто порядок на множестве дочерних вершин, но и их позиция (даже если позиция левого свободна). Хотя, с другой стороны, эту ситуацию можно трактовать как наличие двух детей, из которых левый – «пустой» (фиктивный). Для таких деревьев время поиска по ключу ≤ 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, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи. -Разбиение дерева по ключу

Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами < K ₀ и ≥ K ₀. -Объединение двух деревьев в одно

Обратная операция: есть два дерева поиска, у одного ключи < K ₀, у другого ≥ K ₀. Объединить их в одно дерево.У нас есть два дерева: T ₁ (меньшее) и T ₂ (большее). Сначала нужно решить, откуда взять корень: из T ₁ или T ₂. Стандартного метода нет, возможные варианты:

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

алг ОбъединениеДеревьев(T1, T2)

если T1 пустое, вернуть T2

если T2 пустое, вернуть T1

если решили сделать корнем T1, то

T = ОбъединениеДеревьев(T1.правое, T2)

T1.правое = T

вернуть T1

иначе

T = ОбъединениеДеревьев(T1, T2.левое)

T2.левое = T

вернуть T2