详细分析最佳二叉搜索树，c ++代码实现

首先查看最佳二叉搜索树的描述

给出n个不同的关键字K = {k1，k2，...，kn}的序列，并对关键字进行排序，对于每个关键字ki，搜索ki的概率为pi. 某些搜索的值可能不在K中，因此有n + 1个虚拟键d0，d1二叉排序树代码，...，dn表示不再在K中的值.d0表示所有小于k1，dn的值表示大于kn的所有值，并且对于i = 1,2，...，n-1，di表示ki和ki + 1之间的所有值. 对于每个虚拟关键字di，对应于di的一次搜索的概率为qi. 在T中定义搜索的预期成本为E = ∑（depth（ki）+1）* pi + ∑（depth（di）+1）* qi = 1 + ∑ depth（ki）* pi + ∑ depth（di）*气

找到的最小E是最佳二叉搜索树

首先，我们定义

w [i] [j] = q [i-1] + p [i] + q [i] + p [i + 1] + .... + q [j] + p [j]，显然w [i] [j] = w [i] [j-1] + q [j] + p [j]

E [i] [j]是由节点i到j组成的最佳二叉搜索树的预期成本. 如果我们假设其根为r，那么显然他的左子树（由节点Point i，i + 1，... r-1也是最优的二叉搜索树，而右子树也是最优的二叉搜索树）搜索树，否则，我们可以调整他的子树，得到一个比原始树更好的二叉搜索树，它与前提矛盾，因此最优二叉搜索树具有最优子结构

仅左侧子树的搜索成本为E [i] [r-1]

仅右子树的搜索成本为E [r + 1] [j]

左右子树作为子树连接到根r. 显然，整体搜索成本会增加p [r] +（q [i-1] + p [i] + .. q [r-1]）[注: 由于所有实节点和虚拟节点又有一层] +（q [r + 1] + p [r + 1] + .. q [j]）[注意: 增加正确的子树的代价]

增加的成本实际上转换为w [i] [j]

因此，E [i] [j] = E [i] [r-1] + E [r + 1] [j] + W [i] [j]（r = i，... j）

为使E [i] [j]最小，有必要选择适当的r并将其表示为公式

E [i] [j] = min {E [i] [r-1] + E [r + 1] [j] + W [i] [j]}（r = i，... j ）

注意，将E [i] [i-1]定义为q [i-1]，类似地二叉排序树代码，E [j + 1] [j]是q [j]. 原因是因为r = i或j尽管左或右子树为空，但它仍包含虚拟节点d [i-1]和d [j]. 如果无法解决，则可以通过E [i] [i]

推断E [i] [i-1]

反向如下

E [i] [i] = E [i] [i-1] + E [i + 1] [i] + W [i] [i] //相当于循环中的r = i

左= q [i] + 2 *（q [i-1] + q [i]）//定义

右侧w [i] [i] = q [i-1] + p [i] + q [i]

所以得到E [i] [i-1] + E [i + 1] [i] = q [i-1] + q [i]

有了以上想法，我们可以从一个节点开始逐步扩展. 扩展的每个步骤都基于之前较少节点的W和E. 这种扩展方法有点类似于矩阵乘法问题. 最小乘法次数

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-245462-1.html