Алгоритмы поиска на основе деревьев

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

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

Двоичные (бинарные) деревья

Двоичные деревья представляют собой иерархическую структуру, в которой каждый узел имеет не более двух потомков. То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). При этом каждое поддерево в свою очередь тоже является деревом. Поиск на таких структурах не дает выигрыша по выполнению по сравнению с линейными структурами того же размера, так как необходимо в худшем случае выполнить обход всего дерева. Поэтому интерес представляют двоичные упорядоченные деревья.

Двоичные упорядоченные деревья

Двоичное дерево упорядоченно, если для любой его вершины x справедливы такие свойства:

• все элементы в левом поддереве меньше элемента, хранимого в x,
• все элементы в правом поддереве больше элемента, хранимого в x,
• все элементы дерева различны.

Если в дереве выполняются первые два свойства, но встречаются одинаковые элементы, то такое дерево является частично упорядоченным. В дальнейшем будет идти речь только о двоичных упорядоченных деревьях. Основными операциями, производимыми с упорядоченным деревом, являются:

• поиск вершины;
• добавление вершины;
• удаление вершины;
• вывод (печать) дерева;
• очистка дерева.

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

Временная сложность этих алгоритмов (она одинакова для этих алгоритмов, так как в их основе лежит поиск) оценим для наилучшего и наихудшего случая. В лучшем случае, то есть случае полного двоичного дерева, получаем сложность O_min(log n). В худшем случае дерево может выродиться в список. Такое может произойти, например, при добавлении элементов в порядке возрастания. При работе со списком в среднем придется просмотреть половину списка. Это даст сложность O_max(n).

Случайные деревья

Случайные деревья поиска представляют собой упорядоченные бинарные деревья поиска, при создании которых элементы (их ключи) вставляются в случайном порядке.

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

При поступлении элементов в случайном порядке получаем дерево с минимальной высотой h, при этом минимизируется время поиска элемента в дереве, которое пропорционально O(log n). При поступлении элементов в упорядоченном виде или в порядке с единичными сериями монотонности происходит построение вырожденных деревьев поиска (оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет O(n).

Оптимальные деревья

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

Пусть даны 2n+1 вероятностей p₁,p₂,...,p_n, q₀,q₁,...,q_n, где p_i – вероятность того, что аргументом поиска является K_i элемент; q_i – вероятность того, что аргумент поиска лежит между вершинами K_i и K_i+1 ; q₀ – вероятность того, что аргумент поиска меньше, чем значение элемента K₁ ; q_n – вероятность того, что аргумент поиска больше, чем K_n. Тогда цена дерева поиска C будет определяться следующим образом:

где – уровень узла j, а – уровень листа K.

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

Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска, которое будет далеко от оптимального. Еще один подход состоит в выборе корня k таким образом, чтобы максимальная сумма вероятностей для вершин левого поддерева или правого поддерева была настолько мала, насколько это возможно. Такой подход также может оказаться плохим в случае выбора в качестве корня элемента с малым значением p_k.

Существуют алгоритмы, которые позволяют построить оптимальное дерево поиска. К ним относится, например, алгоритм Гарсия-Воча. Однако такие алгоритмы имеют временную сложность порядка O(n²). Таким образом, создание оптимальных деревьев поиска требует больших накладных затрат, что не всегда оправдывает выигрыш при быстром поиске.