DAA - деревья двоичного поиска оптимальной стоимости

Дерево двоичного поиска (BST) - это дерево, в котором значения ключей хранятся во внутренних узлах. Внешние узлы - это нулевые узлы. Ключи упорядочены лексикографически, т. Е. Для каждого внутреннего узла все ключи в левом поддереве меньше, чем ключи в узле, а все ключи в правом поддереве больше.

Когда мы знаем частоту поиска каждого ключа, довольно легко вычислить ожидаемую стоимость доступа к каждому узлу в дереве. Оптимальное двоичное дерево поиска - это BST, у которого есть минимальные ожидаемые затраты на поиск каждого узла.

Время поиска элемента в BST составляет O(n), тогда как в режиме поиска Balanced-BST время O(log n). Опять же, время поиска можно уменьшить в двоичном дереве поиска с оптимальной стоимостью, помещая наиболее часто используемые данные в корень и ближе к корневому элементу, а наименее часто используемые данные размещая рядом с листьями и в листьях.

Здесь представлен алгоритм оптимального двоичного дерева поиска. Сначала мы создаем BST из набора предоставленныхn количество различных ключей < k₁, k₂, k₃, ... k_n >. Здесь мы предполагаем, что вероятность доступа к ключуK_i является p_i. Некоторые фиктивные ключи (d₀, d₁, d₂, ... d_n) добавляются, поскольку некоторые поиски могут выполняться для значений, которых нет в наборе ключей K. Предположим, для каждого фиктивного ключаd_i вероятность доступа q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

Анализ

Алгоритм требует O (n³) время, так как три вложенных forпетли используются. Каждая из этих петель занимает не болееn значения.

пример

Учитывая следующее дерево, стоимость составляет 2,80, хотя это не оптимальный результат.

Узел	Глубина	Вероятность	Вклад
k 1	1	0,15	0,30
k 2	0	0,10	0,10
k 3	2	0,05	0,15
k 4	1	0,10	0,20
k 5	2	0,20	0,60
d 0	2	0,05	0,15
d 1	2	0,10	0,30
d 2	3	0,05	0,20
d 3	3	0,05	0,20
d 4	3	0,05	0,20
d 5	3	0,10	0,40
Total			2,80

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

В следующих таблицах индекс столбца i и индекс строки j.

е	1	2	3	4	5	6
5	2,75	2,00	1,30	0,90	0,50	0,10
4	1,75	1,20	0,60	0,30	0,05
3	1,25	0,70	0,25	0,05
2	0,90	0,40	0,05
1	0,45	0,10
0	0,05

ш	1	2	3	4	5	6
5	1,00	0,80	0,60	0,50	0,35	0,10
4	0,70	0,50	0,30	0,20	0,05
3	0,55	0,35	0,15	0,05
2	0,45	0,25	0,05
1	0,30	0,10
0	0,05

корень	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

Из этих таблиц можно составить оптимальное дерево.