algorithm - 最优二叉搜索树仅针对特定顺序的键和频率对是最优的？

Question

提供成对的 key 及其频率，

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 

我们可以构建一个 optimal BST通过 Knuth's dynamic programming algorithm .

如果我们打乱这些对，我们可以构建另一个最优 BST。

所以最优 BST 仅针对特定顺序的对是最优的，对吗？如果是，我们可以将这个数据结构应用于什么场景？

Answer 1

你问:

So optimal BST is only optimal for a specific order of pairs, right?

这就是维基百科文章所说的:

... is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities).

换句话说，如果您更改单个单词的频率，则必然会更改树中键的顺序。

您还问:

If it is, what's the scene we can apply this data structure for?

您可以像使用任何二叉搜索树一样使用它。这里的想法是它安排树使得经常搜索的项目需要搜索更少的节点，以不经常访问的项目为代价，这需要更多的搜索。当各个项目的访问概率差异很大时，它优于一般的二叉搜索树(包括平衡树)。

虽然您可以拥有动态最优 BST，但如果您进行大量修改，重新塑造树的成本会很高。最好的应用是当树是静态的，或者如果树的查询比修改多几个数量级。