Алгоритм Гильберта – Мура построения оптимального дерева бинарного поиска Суть алгоритма

Алгоритм основывается на следующем свойстве таких деревьев.

Пусть Т – оптимальное дерево бинарного поиска для весов: .

Если элемент, соответствующий корню дерева Т, то левое поддерево корня дерева Т является ОДБП для весов p₂ ,…, p_{k - 1}, q_{k – 1} , а правое поддерево корня дерева Т является ОДБП для весов q_k , p_k+1,…, p_n , q_n .

Пусть ОДБП для множества

корень дерева ;

стоимость дерева ;

вес дерева :

; (2)

дерево, состоящее из листа

Если корень дерева , то левое поддерево с корнем , которое является ОДБП для множества , а правое поддерево с корнем , которое является ОДБП для множества .

Так как глубина вершины в дереве на единицу больше ее глубины в дереве или , то

. (3)

Можно найти корень дерева , определив величину , которая минимизирует сумму (3).

Эти рассуждения лежат в основе алгоритма, который был предложен Гильбертом и Муром (E.N. Gilbert, E.F. Moore, 1959).

Алгоритм

1. Дано: неотрицательные веса. Для i = 0, 1, 2, … , n полагают вес дерева совпадает с весом соответствующего листа, стоимость равна нулю, корень совпадает с листом:

2. Для выполнить шаг 3.

3. Для i = 0,1,2, …,n – l выполнить шаг 4.

4. Положить Пусть т – значение параметра , для которого сумма минимальна.

Положить

Вычислив с помощью приведенного выше алгоритма, мы можем построить дерево , используя следующую процедуру:

1. корень дерева . Если , то a_k имеет в качестве левого узла , а в качестве правого .

2. Рассмотрим внутреннюю вершину а_т . Если а_т = , то а_т имеет в качестве левого узла, а в качестве правого.

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

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

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

Пример. Пусть имеются четыре упорядоченных элемента с весами р₁ = 2, р₂ =1, р₃ =3, р₄ =1; q₀ =1, q₁ =2, q₂ =3, q₃ =2, q₄ =1. Построить оптимальное дерево бинарного поиска.

□ Воспользуемся алгоритмом Гильберта – Мура .

1. Для полагаем

2. и выполним шаг 3.

3. Так как i = 0, 1, 2, …, n – l , то i = 0, 1, 2, 3. Выполним шаг 4.

4. Вычисляем веса деревьев по формуле:

,

где .

Тогда, учитывая l , получим

Вычисления весов будем проводить с изменением значения i , т.е. деревья расположатся в следующем порядке: :

Вычисляем стоимость деревьев , минимизируя сумму

и каждый раз оптимально выбираем корень.

Используя указанную выше процедуру построения дерева, построим это дерево:

Корнем дерева является . Для корня левым узлом будет , а правым – . Для корня левым узлом будет , а правым – , т.е лист b₂ . Для корня левым листом будет , а правым – . Для корня а₄ левым листом будет , а правым – . ■