Оптимальное бинарное дерево поиска является оптимальным только для определенного порядка пар ключа и частоты?

Question

Предоставление пар ключа и его частоты,

a 32
an 7
and 69
by 13
effects 6
for 15
from t 0
high 8
in 64
of t 42
on 22
the 79
to 18
with 9 

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

Мы можем построить еще один оптимальный BST, если перетасуем пары.

Так что оптимальный BST оптимален только для определенного порядка пар, верно? Если да, то для какой сцены мы можем применить эту структуру данных?

Answer 1

Вы спросили:

Так что оптимальный BST оптимален только для определенного порядка пар, верно?

Вот что говорится в статье в Википедии:

... - это двоичное дерево поиска, которое предоставляет наименьшее возможное время поиска (или ожидаемое время поиска) для данной последовательности обращений (или вероятностей доступа).

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

Вы также спросили:

Если это так, для какой сцены мы можем применить эту структуру данных?

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

Несмотря на то, что вы можете иметь динамический оптимальный BST, изменение формы дерева может обойтись дорого, если у вас есть много модификаций. Лучшее применение этого - когда дерево статично или если у дерева на несколько порядков больше запросов, чем модификаций.

Answer 2

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

Его можно использовать как словарь, как BST.