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

В двоичном дереве поиск одних элементов может происходить чаще, чем других, то есть существуют вероятности pk поиска k

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

Пусть дано 2n + 1 вероятностей p1, p2, …, pn, q0, q1, …, qn, где pi – вероятность того, что аргументом поиска является ki элемент; pi – вероятность того, что аргумент поиска лежит между вершинами ki и ki + 1; q0 – вероятность того, что аргумент поиска меньше, чем значение элемента k1; qn – вероятность того, что аргумент поиска больше, чем kn

. Тогда цена дерева поиска C будет определяться следующим образом:

C=∑j=1npj([уровень узла]j+1)+∑k=1nqk([уровень листа]k).

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

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

.

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