Алгоритм Гильберта – Мура построения оптимального дерева бинарного поиска Суть алгоритма

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

Пусть Т – оптимальное дерево бинарного поиска для весов: .

Если элемент, соответствующий корню дерева Т, то левое поддерево корня дерева Т является ОДБП для весов p₂ ,…, p_{k - 1}, q_{k – 1} , а правое поддерево корня дерева Т является ОДБП для весов q_k , p_k+1,…, p_n , q_n .

Пусть ОДБП для множества

корень дерева ;

стоимость дерева ;

вес дерева :

; (2)

дерево, состоящее из листа

Если корень дерева , то левое поддерево с корнем , которое является ОДБП для множества , а правое поддерево с корнем , которое является ОДБП для множества .

Так как глубина вершины в дереве на единицу больше ее глубины в дереве или , то

. (3)

Можно найти корень дерева , определив величину , которая минимизирует сумму (3).

Эти рассуждения лежат в основе алгоритма, который был предложен Гильбертом и Муром (E.N. Gilbert, E.F. Moore, 1959).