Алгоритм

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₂ . Для корня левым листом будет , а правым – . Для корня а₄ левым листом будет , а правым – . ■