Предположим, что необходимо определить, принадлежит ли элемент

x множеству A. Интерпретация поиска по дереву на рис. 12б может быть

следующая. Сравним x с корневой вершиной a_2. Если x равен a₂, то поиск

успешно завершается.

Пусть x меньше a₂, тогда поиск продолжается в левом поддереве, а если

x больше a₂, то в правом. Успешный поиск завершается во внутренних вершинах дерева, при этом число выполненных сравнений на единицу больше уровня вершины a_i = x. Элемент x может не принадлежать множеству A, тогда

поиск будет безуспешным и завершится в одной из концевых вершин дерева.

В концевой вершине сравнение элементов не выполняется, поэтому число

сравнений равно уровню соответствующей концевой вершины.

Пусть вершинам дерева сопоставлены в соответствие неотрицательные

веса p_i = p(a_i), q_j = q(b_j). Стоимостью двоичного дерева поиска называется

величина

 

C(D) = p_i [l (a_i)+ 1] + q_j l (b_j)

 

Если веса рассматривать как вероятности обращений к элементам множества

A U B (åip_i + åjq_j = 1), то стоимость дерева пропорциональна времени поиска в дереве D.

Необходимо построить дерево бинарного поиска минимальной стоимости,

которое будем называть оптимальным для весов q₀, p₁, q₁,..., p_к-1, q_к-1.

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

таких деревьев. Пусть D_0,n - оптимальное дерево бинарного поиска для весов

q₀, p₁, q₁, p₂, q₂,..., p_n, q_n, а a_k – корневая вершина дерева D_0,n. Тогда левое

поддерево D_0,к-1 является оптимальным деревом бинарного поиска для весов

q₀, p₁, q₁,..., p_к-1, q_к-1, а правое поддерево D_к,n - оптимальным деревом бинарного поиска для весов q_k, p_k+1, q_k+1,..., p_n, q_n.

Обозначим через c(i,j) стоимость оптимального поддерева для весов

q_i, p_i+1,..., p_j, q_j, а через w(i,j) - сумму этих весов. Так как минимально возможная стоимость дерева с корневой вершиной a_k равна

w(i,j) + c(i,k-1) + c(k,j), то сформулированное выше свойство позволяет

написать рекуррентное соотношение

 

c(i,j) = w(i,j) + min {c(i,k-1) + c(k,j)}, 0

 

c(i,i) = 0.

 

Корень r(i,j) оптимального дерева D_i,j определяется значением k, при котором достигается минимум в (6).

Приведенный выше алгоритм строит оптимальное дерево снизу, в порядке

возростания величины (j-i). Вычислив r(i,j) для всех , можно построить оптимальное поддерево D_0,n. Сначала определяется корневая вершина r(0,n) дерева D_0,n. Пусть r(0,n) = a_k, тогда корневая вершина левого поддерева r(0,k-1), а правого - r(k,n). Аналогично, если r(i,j) = a_m, то левое

поддерево корневой вершины a_m определяется найденной величиной r(0,m-1), а правое - r(m,j).

Данный алгоритм носит название алгоритма Гилберта-Мура и основан на методе динамического программирования. Оценим вычислительную сложность

этого алгоритма. Вычисляя по мере надобности w(i,j), мы их всех можем определить за O(n²) сложений. При каждом из n – l + 1 значений параметра i для вычисления c(i,k-1) + c(k,i+l) достаточно l сложений; (l-1) попарных сравнений требуется для определения наименьшей суммы c(i,k-1) + c(k,i+1);

и еще одно сложение требуется для отыскания c(k,i+l). Таким образом, всего

требуется O(n²) + (n – l + 1)(l + (l-1)+ 1) = O(n³) арифметических операций. Следовательно, вычислительная сложность алгоритма Гильберта-Мура оценивается как O(n³) арифметических операций.

Пример 5. Пусть требуется построить оптимальное дерево бинарного поиска для последовательности весов, указанных в табл. 18.

 

Таблица 18.

 

q0	p1	q1	p2	q2	p3	q3	p4	q4	p5	q5

 

Вычисленные значения w(i,j), r(i,j) и с(i,j) приведены в табл. 19. Вычисления выполняеются последовательно, по строкам слева направо, начиная с первой строки. Построенное дерево бинарного поиска приведено на рис.13.

Таблица 19.

 

r(0,0) =b0 w(0,0) = 1 c(0,0) = 0	r(1,1) =b1 w(1,1) = 3 c(1,1) = 0	r(2,2) =b2 w(2,2) = 1 c(2,2) = 0	r(3,3) =b3 w(3,3) = 3 c(3,3) = 0	r(4,4) =b4 w(4,4) = 1 c(4,4) = 0	r(5,5) =b5 w(5,5) = 6 c(5,5) = 0
r(0,1) =a1 w(0,1) = 6 c(0,1) = 6	r(1,2) =a2 w(1,2) = 5 c(1,2) = 5	r(2,3) =a3 w(2,3) = 6 c(2,3) = 6	r(3,4) =a4 w(3,4) = 9 c(3,4) = 9	r(4,5) =a5 w(4,5) = 9 c(4,5) = 9
r(0,2) =a1 w(0,2) = 8 c(0,2) =13	r(1,3) =a3 w(1,3) =10 c(1,3) =15	r(2,4) =a4 w(2,4) =12 c(2,4) =18	r(4,5) =a5 w(4,5) =17 c(4,5) =26
r(0,3) =a2 w(0,3) =13 c(0,3) =25	r(1,4) =a3 w(1,4) =16 c(1,4) =30	r(2,5) =a4 w(2,5) =20 c(2,5) =35
r(0,4) =a3 w(0,4) =19 c(0,4) =43	r(1,5) =a4 w(1,5) =24 c(1,5) =48
r(0,4) =a4 w(0,4) =27 c(0,4) =61

 

a4

 

 

a2 a5

 

 

a1 a3 b4 b5

 

b0 b1 b2 b3

 

Рис. 13.

 

Кнут показал [3], что для построения оптимального дерева поиска не обязятельно вычислять все r(i,j) и c(i,j), . Достаточно при условии

неотрицательности весов вычислять r(i,j) для которых справедливо неравенство

r(i,j-1) r(i,j) r(i+1,j).

Пусть r(i,j) – индекс корневой вершины поддерева D_i,j. Тогда в (6) вместо

(j-i) значений k проверяется только (r(i+1,j) - r(i,j-1) + 1) значений. Оценим

сложность алгоритма Кнута. За O(n²) сложений вычисляются все w(i,j), . Заметим, что (r(i,i+1) = i+1; c(i,i+1) = w(i,i+1). После того, как

r(i,j) и c(i,j) вычислены для , можно в соответствие с предложением Кнута вычислить r(i,j) и c(i,j) для каждой пары (i,j), где и j-i = l,

l>1 с помощью 2*(r(i+1,j) - r(i,j-1) + 1) арифметических операций. Действительно, за (r(i+1,j) - r(i,j-1) + 1) сложений вычислим с(i,k-1) + c(k,j)

для r(i,j-1) k r(i+1,j). С помощью r(i+1,j) - r(i,j-1) попарных сравнений

определим r(i,j). Еще одно сложение потребуется для вычисления c(i,j).

Таким образом, для алгоритма Кнута общее число арифметических операций

есть:

 

O(n²) + 2 (r(i+1,j) - r(i,j-1) + 1) = O(n²) + 2( r(i,n) - (r(0,j)) =

 

= O(n²) + O(n²) = O(n²).

 

Алгоритм Кнута имеет наименьшую оценку трудоемкости среди всех

известных алгоритмов.

 

Алгоритм 4.

начало;

1) для i от 0 до n шаг 1 цикл;

2) начало;

3) c(i,j) = 0;

4) w(i,i) = a_m;

5) для j от i +1 до n шаг 1 цикл

6) начало;

7) w(i,j) = w(i,j-1) + q_j + p_j

8) конец цикла

9) конец цикла

10) для j от 1 до n шаг 1 цикл

11) начало;

12) с(j-1,j) = w(j-1,j);

13) r(j-1,j) = j;

14) конец цикла

15) для d от 2 до n шаг 1 цикл

16) начало;

17) для j от d до n шаг 1 цикл

18) начало;

19) i = j - d;

20) положить k равным тому индексу k, при котором выражение

c(i,k-1) + c(k,j) достигает максимума

21) с = c(i,k-1) + c(k,j);

22) с(i,j) = w(i,j) + с;

23) конец цикла

24) конец цикла

конец

 

Использование на практике алгоритма 4 ограничено, так как существуют

алгоритмы построения достаточно хороших деревьев бинарного поиска с

линейной от n оценкой сложности. Для оценки качества подоптимальных

алгоритмов используются двусторонние оценки, причем нижние оценки

незначительно отличаются от верхних оценок. Отличительной особенностью

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

поиска сверху, в то время как оптимальные алгоритмы строят дерево

бинарного поиска снизу.

Опишем на содержательном уровне алгоритмы построения почти оптимальных деревьев.

Назовем дерево поиска сбалансированным по сумме весов, если для

каждой его внутренней вершины a_k выполняется условие

 

a_k = min {|w(i,k-1) - w(k,j)|}, 0

где w(i,k-1), w(k,j) – сумма весов вершин соответственно левого и правого поддерева корневой вершины a_k.

Другими словами, необходимо выбрать корень в дереве поиска так, чтобы веса обоих поддеревьев различались как можно меньше. Аналогично поступать с каждым поддеревом.

Если сумма весов удовлетворяет условиям нормировки q_j + p_i = 1,

то близость по стоимости оптимальных и сбалансированных по сумме весов

деревьев определяется следующими оценками [4]:

 

H -log H -log e £ C(D_опт) £ C(D_сб) £ H + 2

где C(D_сб) – стоимость сбалансированного дерева; H – энтропия;

H = - q_j log q_j + p_i log p_i

Назовем дерево поиска минимаксным, если для каждой его внутренней вершины a_k выполняется условие

a_k = min max{|w(i,k-1) - w(k,j)|}, 0

В минимаксном дереве корень необходимо выбрать так, чтобы поддерево

большего веса имело наименьший возможный вес. Аналогично поступать с каждым поддеревом.

Для минимаксных деревьев D_mm справедлива следующая верхняя оценка

[4]:

C(D_mm) £ H + 1 + q_j

Контрольные вопросы и задания.

 

1. Постройте оптимальное дерево бинарного поиска для весов, заданных одной из строк табл. 20. Постройте сбалансированное и минимаксное дерево для заданного варианта и сравните их по стоимости с оптимальным деревом.

Таблица 20

 

 

q0	p1	q1	p2	Q2	p3	q3	p4	q4	p5	q5

2. Приведите пример сбалансированного дерева поиска, которое не является

оптимальным

3. Приведите пример минимаксного дерева поиска, которое не является оптимальным.