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

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

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

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

Здесь представлен алгоритм оптимального двоичного дерева поиска. Сначала мы создаем BST из набора предоставленныхn количество различных ключей < k1, k2, k3, ... kn >. Здесь мы предполагаем, что вероятность доступа к ключуKi является pi. Некоторые фиктивные ключи (d0, d1, d2, ... dn) добавляются, поскольку некоторые поиски могут выполняться для значений, которых нет в наборе ключей K. Предположим, для каждого фиктивного ключаdi вероятность доступа qi.

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 (n3) время, так как три вложенных 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

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