Оптимальные бинарные деревья поиска

Министерство образования и науки Украины Министерство образования и науки АРК Крымский инженерно-педагогический университет ДОКЛАД По дисциплине Семинар по специальным дисциплинам По теме ОПТИМАЛЬНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА Симферополь 2011

План:

1. Оптимальные бинарные деревья поиска

2. Структура оптимального бинарного дерева поиска

3. Рекурсивное решение

4. Вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска.

Оптимальные бинарные деревья поиска

Предположим, что разрабатывается программа, предназначенная для перевода текстов с русского языка на украинский. Для каждого русского слова необходимо найти украинский эквивалент. Один из возможных путей поиска — построение бинарного дерева поиска с n русскими словами, выступающими в роли ключей, и украинскими эквивалентами, играющими роль сопутствующих данных. Поскольку поиск с помощью этого дерева будет производиться для каждого отдельного слова из текста, полное затраченное на него время должно быть как можно меньше. С помощью красно-черного дерева или любого другого сбалансированного бинарного дерева поиска можно добиться того, что время каждого отдельного поиска будет равным O (lgn). Однако слова встречаются с разной частотой, и может получиться так, что какое-нибудь часто употребляемое слово (например, предлог или союз) находится далеко от корня, а такое редкое слово, как «контрвстреча» , — возле корня. Такой способ организации привел бы к замедлению перевода, поскольку количество узлов, просмотренных в процессе поиска ключа в бинарном дереве, равно увеличенной на единицу глубине узла, содержащего данный ключ. Нужно сделать так, чтобы слова, которые встречаются в тексте часто, были размещены поближе к корню. Кроме того, в исходном тексте могут встречаться слова, для которых перевод отсутствует. Таких слов вообще не должно быть в бинарном дереве поиска. Как организовать бинарное дерево поиска, чтобы свести к минимуму количество посещенных в процессе поиска узлов, если известно, с какой частотой встречаются слова?

Необходимая нам конструкция известна как оптимальное бинарное дерево поиска (optimal binary search tree). Приведем формальное описание задачи. Имеется заданная последовательность К = (k₁, k₂,…, k_n), состоящая из n различных ключей, которые расположены в отсортированном порядке (так что k₁ < k₂ <… < k_n). Из этих ключей нужно составить бинарное дерево поиска. Для каждого ключа к{ задана вероятность pi поиска этого ключа. Кроме того, может выполняться поиск значений, отсутствующих в последовательности К, поэтому следует предусмотреть n + 1 фиктивных ключей (d₀, d₁,…, d_n), представляющих эти значения. В частности, do представляет все значения, меньшие k₁, a d_n — все значения, превышающие кп. Фиктивный ключ d_i (i = 1,2,…, n — 1) представляет все значения, которые находятся между k_i и k_i+1. Для каждого фиктивного ключа d_i задана соответствующая ей вероятность q_i. Например бинарное дерево поиска для множества, состоящего из n = 5 ключей.

Каждый ключ k_i представлен внутренним узлом, а каждый фиктивный ключ d_i является листом. Поиск может быть либо успешным (найден какой-то ключ k_i), либо неудачным (возвращается какой-то фиктивный ключ d_i), поэтому справедливо соотношение Вероятности, соответствующие внутренним узлам p_i и листьям q_i, приведены таблице.

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

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

Математическое ожидание поиска в этом дереве равно 2.80. Этот пример демонстрирует, что оптимальное бинарное дерево поиска — это не обязательно дерево минимальной высоты. Кроме того, в оптимальном дереве ключ, которому соответствует максимальная вероятность, не всегда находится в корне. В данном случае вероятность имеет самую большую величину для ключа k₅, хотя в корне оптимального бинарного дерева расположен ключ k₂. (Минимальная величина математического ожидания для всевозможных бинарных деревьев поиска, в корне которых находится ключ k₅, равна 2.85) Последовательный перебор всех возможных деревьев в данном случае оказывается неэффективным.

Чтобы сконструировать бинарное дерево поиска, можно обозначить ключами k₁, k₂, …, k_n узлы бинарного дерева с n узлами, а затем добавить листья для фиктивных ключей. В задаче 12−4 было показано, что количество бинарных деревьев с n узлами равно, так что количество бинарных деревьев, которые надо проверять при полном переборе, растет экспоненциально с ростом n. Эта задача будет решаться методом динамического программирования.

2. Структура оптимального бинарного дерева поиска

Чтобы охарактеризовать оптимальную подструктуру оптимального бинарного дерева поиска, исследуем его поддеревья. Рассмотрим произвольное поддерево бинарного дерева поиска. Оно должно содержать ключи, которые составляют непрерывный интервал k_i,…, k_j Для некоторых 1 < i < j < n. Кроме того, такое поддерево должно также содержать в качестве листьев фиктивные ключи d_i-1, …, d_j.

Теперь можно сформулировать оптимальную подструктуру: если в состав оптимального бинарного дерева поиска T входит поддерево T', содержащее ключи k_i,…, k_j, то это поддерево тоже должно быть оптимальным для вспомогательной подзадачи с ключами k_i,…, k_j и фиктивными ключами d_i-1, …, d_j. Для доказательства этого утверждения применяется обычный метод «вырезания и вставки». Если бы существовало поддерево Т", математическое ожидание поиска в котором ниже, чем математическое ожидание поиска в поддереве Т', то из дерева Т можно было бы вырезать поддерево Т' и подставить вместо него поддерево Т". В результате получилось бы дерево, математическое ожидание времени поиска, в котором оказалось бы меньше, что противоречит оптимальности дерева Т.

Покажем с помощью описанной выше оптимальной подструктуры, что оптимальное решение задачи можно воссоздать из оптимальных решений вспомогательных задач. Если имеется поддерево, содержащее ключи k_i,…, k_j, то один из этих ключей, скажем, k_r (i<=r<=j) будет корнем этого оптимального поддерева. Поддерево, которое находится слева от корня k_r, будет содержать ключи k_i,…, k_r-1 (и фиктивные ключи d_i-1,…, d_r-1), а правое поддерево — ключи k_r+1,…, k_j (и фиктивные ключи d_r,…, d_j). Как только будут проверены все ключи k_r (где I <= r <= j), которые являются кандидатами на роль корня, и найдем оптимальные бинарные деревья поиска, содержащие элементы k_i,…, k_r-1, и k_r+1,…, k_j, мы гарантированно построим оптимальное бинарное дерево поиска. Стоит сделать одно замечание по поводу «пустых» поддеревьев. Предположим, что в поддереве с ключами k_i,…, k_j в качестве корня выбран ключ k_i.

Согласно приведенным выше рассуждениям, поддерево, которое находится слева от корня k_i, содержит ключи k_i,…, k_i-1. Интерпретировать эту последовательность необходимо как такую, в которой не содержится ни одного ключа. Однако следует иметь в виду, что поддеревья содержат помимо реальных и фиктивные ключи. Примем соглашение, согласно которому поддерево, состоящее из ключей k_i,…k_i-1, не содержит обычных ключей, но содержит один фиктивный ключ d_i-1. Аналогично, если в качестве корня выбран ключ k_i, то правое поддерево не содержит обычных ключей, но содержит один фиктивный ключ d_j.

3. Рекурсивное решение

Теперь все готово для рекурсивного определения оптимального решения. В качестве вспомогательной задачи выберем задачу поиска оптимального бинарного дерева поиска, содержащего ключи k_i,…, k_j, где i >= 1, j <= n и j >= i — 1 (если j = n — 1, то фактических ключей не существует, имеется только фиктивный ключ d_i-1). Определим величину е[i, j] как математическое ожидание стоимости поиска в оптимальном бинарном дереве поиска с ключами к{,…, kj. В конечном итоге нужно вычислить величину е[1,n].

Если j = i — 1, то все просто. В этом случае имеется всего один фиктивный ключ d_i-1, и математическое ожидание стоимости поиска равно е[i, i — 1] = q_i-1.

Если j >= i, то среди ключей k_i,…, k_j нужно выбрать корень k_r, а потом из ключей k_i,…, k_r-1 составить левое оптимальное бинарное дерево поиска, а из ключей k_r+1,…, k_j — правое оптимальное бинарное дерево поиска. Глубина каждого узла в поддереве возрастает на единицу. Согласно уравнению математическое ожидание стоимости поиска в этом поддереве возрастает на величину суммы по всем вероятностям поддерева. Обозначим эту сумму вероятностей, вычисленную для поддерева с ключами k_i,…, k_j так:

Таким образом, если k_r — корень оптимального поддерева, содержащего ключи к_i,…, k_j, то выполняется соотношение Заметив, что выражение для величины е [i, j] можно переписать так:

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

С учетом этого получаем окончательную рекурсивную формулу:

Величины е[r, j] — это математическое ожидание стоимостей поиска в оптимальных бинарных деревьях поиска. Чтобы было легче следить за структурой оптимального бинарного дерева поиска, обозначим через root [i, j] (где 1 <= i <= j <= n) индекс r узла k_r, который является корнем оптимального бинарного дерева поиска, содержащего ключи k_i,…, k_j.

бинарный дерево рекурсивный ключ

4. Вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска

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

Вместо этого будем сохранять значения e[i, j] в таблице е [1.n+1,0.n]. Первый индекс должен пробегать не n, а n+1 значений. Это объясняется тем, что для получения поддерева, в который входит только фиктивный ключ d_n, понадобится вычислить и сохранить значение е[n+1,n]. Второй индекс должен начинаться с нуля, поскольку для получения поддерева, содержащего лишь фиктивный ключ d₀, нужно вычислить и сохранить значение е [1,0]. Необходимо использовать только те элементы e[i, j], для которых j >= i-1. Кроме того, необходимо использовать таблицу root[i, j], в которую будут заноситься корни поддеревьев, содержащих ключи k_i,…, k_j. В этой таблице задействованы только те записи, для которых 1 <= i <= j <= n.

Для повышения эффективности понадобится еще одна таблица. Вместо того чтобы каждый раз при вычислении e[i, j] вычислять значения w (i, j) «с нуля», для чего потребуется (j — i) операций сложения, будем сохранять эти значения в таблице w [l.n+1,0.n]. В базовом случае вычисляются величины

w [i, i-1] = q_i-1 для 1 <= i <= n + 1.

Для j >= i вычисляются величины Таким образом, каждое из (n²) значений матрицы w [i, j] можно вычислить за время (1).

Ниже приведен псевдокод, который принимает в качестве входных данных вероятности p_i,…, p_n и q₀,…, q_n и размер n и возвращает таблицы е и root.

Работа представленной выше процедуры такова. Цикл for в строках 1−3 инициализирует значения е[i, i-1] и w[i, i-1]. Затем в цикле for в строках 4−13 с помощью рекуррентных соотношений вычисляются элементы матриц е[i, j] и w[i, j] для всех индексов 1 <= i <= j <= n.

В первой итерации, когда l = 1, в этом цикле вычисляются элементы е [i, i] и w [i, i] для i = 1,2,…, n.

Во второй итерации, когда l = 2, вычисляются элементы е[i, i+1] и w[i, i+1] для i= 1,2,…, n-1 и т. д.

Во внутреннем цикле for (строки 9−13) каждый индекс r апробируется на роль индекса корневого элемента k_r оптимального бинарного дерева поиска с ключами к_i,…, k_j. В этом цикле элементу root [i, j] присваивается то значение индекса r, которое подходит лучше всего.

Ниже показаны таблицы е[i, j], w[i, j] и root[i, j], вычисленные с помощью процедуры Optimal_BST для распределения ключей. Таблицы повернуты так, чтобы диагонали располагались горизонтально. В процедуре Optimal_BST строки вычисляются снизу вверх, а в каждой строке заполнение элементов производится слева направо.

Время выполнения процедуры Optimal_BST равно (n³). Легко увидеть, что время работы составляет О (n²), поскольку циклы for этой процедуры трижды вложены друг в друга, и индекс каждого цикла принимает не более n значений. Далее, ндексы циклов в процедуре Optimal_BST изменяются во всех направлениях они принимают по крайней мере одно значение. Таким образом, процедура Optimal_BST выполняется в течение времени (n³).

1. Кормен Т. Х. Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон. Р. Л. Ривест, К. Штайн. — [2-е изд.]: пер. с англ. — М.: Изд. дом «Вильямс», 2005. — 1296 с.

2. Интернет-Университет Информационных Технологий «intuit.ru»