Всем привет!

Подскажите, пожалуйста,один момент.

Читаю Кормена "построение и анализ" тему про оптимальные двоичные дерева поиска.

И там рассматривается задача быстрого перевода текста.

Вот что автор пишет:

Программа, предназначенная для переводов текстов с русского на английский.
Один из возможных путей поиска - построение бинарного дерева поиска с n русскими словами, выступающими в роли ключей, и английскими эквивалентами, играющими роль сопутствующих данных.

Потом идет формальне описание задачи:

Имеется заданная последовательность K= 〈k_1,k_2,…,k_n 〉, состоящая из n различных ключей, которые расположены в отсортированном порядке (так что k_1<k_2<⋯<k_n).
Из этих ключей нужно составить бинарное дерево поиска, так чтобы свести к минимуму количество посещенных в процессе поиска узлов, если известно, с какой частотой встречаются слова.

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

А матожидание для узла находится как вероятность узла * глубину узла.

Вопрос:

Дерево формируется с учетом посчитанных матожиданий. Поэтому ключи в нем, если я правильно понял, не могут быть просто русскими словами, так как дерево строится по - другому принципу.

Что тогда можно взять в качестве ключей?

Спасибо.

mr_virtus,

Разобрался. Вопрос закрыт. Всем спасибо.

mayton,

Нужно брать русские слова.


Можно построить различные деревья(и все они будут двочиными деревьями поиска), у которых будут одни и теже ключи - русские слова. Просто стоимость нахождения этих слов будет в разных деревьях разная.