DAA — Деревья бинарного поиска с оптимальной стоимостью

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

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

Время поиска элемента в BST равно O (n) , тогда как в сбалансированном 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] := q i - 1 
   w[i, i - 1] := q i - 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] + p j + q j 
      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, хотя это не оптимальный результат.

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

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

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