最优成本二叉搜索树

二叉搜索树（BST）是一棵树，其中键值存储在内部节点中。外部节点是空节点。键按字典顺序排序，即对于每个内部节点，左子树中的所有键都小于该节点中的键，而右子树中的所有键都大于该节点。

当我们知道搜索每个键的频率时，就很容易计算访问树中每个节点的预期成本。最佳二叉搜索树是 BST，它定位每个节点的预期成本最小

BST 中元素的搜索时间为O(n)，而平衡 BST 中的搜索时间为O(log n)。同样，在最优成本二叉搜索树中，可以改进搜索时间，将最常用的数据放置在根中并更靠近根元素，同时将最不常用的数据放置在叶子附近和叶子中。

这里提出了最优二叉搜索树算法。首先，我们从一组提供的n个不同键< k 1 , k 2 , k 3 , ... k n >构建 BST 。这里我们假设访问密钥K i的概率为p i。添加一些虚拟密钥（d 0、d 1、d 2、...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] := qi - 1 
   w[i, i - 1] := qi - 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] + pj + qj 
      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 3 )时间，因为使用了三个嵌套的for循环。每个循环最多采用n 个值。

例子

考虑以下树，成本为 2.80，尽管这不是最佳结果。

树
节点 深度 可能性 贡献
k 1 1 0.15 0.30
k 2 0 0.10 0.10
k 3 2 0.05 0.15
k 4 1 0.10 0.20
k 5 2 0.20 0.60
d 0 2 0.05 0.15
d 1 2 0.10 0.30
d 2 3 0.05 0.20
d 3 3 0.05 0.20
d 4 3 0.05 0.20
d 5 3 0.10 0.40
全部的 2.80

为了获得最佳解决方案，使用本章讨论的算法生成下表。

在下表中，列索引为i，行索引为j。

e 1 2 3 4 5 6
5 2.75 2.00 1.30 0.90 0.50 0.10
4 1.75 1.20 0.60 0.30 0.05
3 1.25 0.70 0.25 0.05
2 0.90 0.40 0.05
1 0.45 0.10
0 0.05

w 1 2 3 4 5 6
5 1.00 0.80 0.60 0.50 0.35 0.10
4 0.70 0.50 0.30 0.20 0.05
3 0.55 0.35 0.15 0.05
2 0.45 0.25 0.05
1 0.30 0.10
0 0.05

根 1 2 3 4 5
5 2 4 5 5 5
4 2 2 4 4
3 2 2 3
2 1 2
1 1

从这些表中，可以形成最佳树。