最优二叉搜索树问题（带频率版本）
字数 2674 2025-11-10 21:45:09

最优二叉搜索树问题（带频率版本）

题目描述

给定一个有序的键值序列 keys[1..n]（例如，表示二叉搜索树中的键），以及每个键被搜索的频率 freq[1..n]。目标是构建一棵二叉搜索树（BST），使得所有键的搜索成本的总和最小。

搜索成本定义为：搜索一个键的代价等于该键在树中的深度（从根节点开始计算，根节点的深度为1）乘以该键的频率。总成本则是搜索每个键的代价之和。

形式化地说，我们需要最小化：
总成本 = Σ (freq[i] * (depth of key i in the BST + 1))

解题过程

  1. 问题分析
    这是一个经典的优化问题。对于一组有序的键，可以构建多种不同结构的二叉搜索树（例如，平衡BST、倾斜BST等）。不同的树结构会导致键的深度不同，从而影响总搜索成本。由于键是有序的，BST的中序遍历必须与键的顺序一致。因此，问题可以看作是为这个有序序列选择一个根节点，然后递归地为左右子树选择根节点。

  2. 定义状态
    我们使用动态规划来解决。定义 dp[i][j] 为构建由键 keys[i], keys[i+1], ..., keys[j] 组成的二叉搜索树的最小总搜索成本（包括这些键本身的频率成本）。
    我们的目标是计算 dp[1][n]。

  3. 状态转移方程
    考虑区间 [i, j]。为了构建这棵BST，我们需要从 i 到 j 中选择一个根节点 k（i <= k <= j）。

    • 如果选择 k 作为根，那么：
      • 所有在 k 左边的键 keys[i], ..., keys[k-1] 将形成左子树。
      • 所有在 k 右边的键 keys[k+1], ..., keys[j] 将形成右子树。
    • 当 k 成为根节点后，左子树和右子树中的所有键的深度都会增加1（因为它们在根节点 k 的下方一层）。这意味着，整个子树 [i, j] 中所有键的频率之和 都会因为根节点 k 的这一层而贡献一次成本。

    因此，如果我们已经知道了左子树 [i, k-1] 的最小成本 dp[i][k-1] 和右子树 [k+1, j] 的最小成本 dp[k+1][j]，那么以 k 为根的总成本为：
    cost = dp[i][k-1] + dp[k+1][j] + sum(freq[i] to freq[j])

    解释最后一项 sum(freq[i] to freq[j])：

    • dp[i][k-1] 是左子树在当前结构下的成本。当我们把左子树挂到根 k 下面时，左子树里每个键的深度都增加了1，因此总成本增加了 (左子树所有键的频率和)。
    • 同理，右子树的总成本也增加了 (右子树所有键的频率和)。
    • 根节点 k 本身的深度在这一层是1，因此它的成本就是 freq[k]。
    • 将这三部分相加：增加左子树的成本 + 增加右子树的成本 + 根节点的成本 = (左子树频率和) + (右子树频率和) + freq[k] = (从i到j的所有键的频率和)。

    所以，转移方程为：
    dp[i][j] = min( dp[i][k-1] + dp[k+1][j] + sum(freq[i..j]) )，其中 k 从 i 遍历到 j。

    边界情况：

    • 如果 i > j，说明这是一个空子树，成本为0。因此，当 k=i 时，左子树 [i, k-1] 即 [i, i-1] 是空的，dp[i][i-1] = 0。同理，当 k=j 时，dp[j+1][j] = 0。
    • 如果 i == j，即只有一个键，那么它自己就是根。dp[i][i] = freq[i]。这也可以通过状态转移方程得到：k 只能取 i，dp[i][i] = dp[i][i-1] + dp[i+1][i] + sum(freq[i..i]) = 0 + 0 + freq[i] = freq[i]。

  4. 计算顺序
    由于计算 dp[i][j] 时需要知道更小区间 [i, k-1] 和 [k+1, j] 的结果，我们应该按区间长度 L 从小到大的顺序进行计算。

    • L = 0：区间长度为1（即 i = j）。计算所有 dp[i][i]。
    • L = 1：区间长度为2（即 i, j 相差1）。计算所有 dp[i][i+1]。
    • ...
    • L = n-1：区间长度为 n（即 i=1, j=n）。计算 dp[1][n]。

    为了快速计算区间 [i, j] 的频率和 sum(freq[i..j])，我们可以预先计算一个前缀和数组 prefixSum，使得 prefixSum[j] - prefixSum[i-1] 就等于 sum(freq[i..j])。

  5. 示例
    键： [10, 12, 20]
    频率：[34, 8, 50]

    • 情况1：根为10
      左子树：空，成本0
      右子树：[12, 20]，需要计算其最小成本。对于子树[12,20]：
      * 根为12：成本 = 0 (左空) + 50 (右子树[20]) + (8+50) = 0+50+58=108
      * 根为20：成本 = 8 (左子树[12]) + 0 (右空) + (8+50) = 8+0+58=66
      所以子树[12,20]的最小成本是66。
      总成本 = 0 + 66 + (34+8+50) = 66 + 92 = 158
    • 情况2：根为12
      左子树：[10]，成本34
      右子树：[20]，成本50
      总成本 = 34 + 50 + (34+8+50) = 84 + 92 = 176
    • 情况3：根为20
      左子树：[10,12]，需要计算其最小成本。对于子树[10,12]：
      * 根为10：成本=0+8+(34+8)=0+8+42=50
      * 根为12：成本=34+0+(34+8)=34+0+42=76
      所以子树[10,12]的最小成本是50。
      右子树：空，成本0
      总成本 = 50 + 0 + (34+8+50) = 50 + 92 = 142
      比较三种情况，最小总成本是142，对应的树结构是20为根，10为左子，12为10的右子。

通过这个循序渐进的过程，我们可以系统地计算出给定键和频率下的最优二叉搜索树结构及其最小总搜索成本。

最优二叉搜索树问题（带频率版本） 题目描述 给定一个有序的键值序列 keys[ 1..n]（例如，表示二叉搜索树中的键），以及每个键被搜索的频率 freq[ 1..n ]。目标是构建一棵二叉搜索树（BST），使得所有键的搜索成本的总和最小。 搜索成本定义为：搜索一个键的代价等于该键在树中的深度（从根节点开始计算，根节点的深度为1）乘以该键的频率。总成本则是搜索每个键的代价之和。 形式化地说，我们需要最小化： 总成本 = Σ (freq[ i] * (depth of key i in the BST + 1)) 解题过程 问题分析 这是一个经典的优化问题。对于一组有序的键，可以构建多种不同结构的二叉搜索树（例如，平衡BST、倾斜BST等）。不同的树结构会导致键的深度不同，从而影响总搜索成本。由于键是有序的，BST的中序遍历必须与键的顺序一致。因此，问题可以看作是为这个有序序列选择一个根节点，然后递归地为左右子树选择根节点。 定义状态 我们使用动态规划来解决。定义 dp[i][j] 为构建由键 keys[i], keys[i+1], ..., keys[j] 组成的二叉搜索树的最小总搜索成本（包括这些键本身的频率成本）。 我们的目标是计算 dp[1][n] 。 状态转移方程 考虑区间 [i, j] 。为了构建这棵BST，我们需要从 i 到 j 中选择一个根节点 k （ i <= k <= j ）。 如果选择 k 作为根，那么： 所有在 k 左边的键 keys[i], ..., keys[k-1] 将形成左子树。 所有在 k 右边的键 keys[k+1], ..., keys[j] 将形成右子树。 当 k 成为根节点后， 左子树和右子树中的所有键的深度都会增加1 （因为它们在根节点 k 的下方一层）。这意味着， 整个子树 [i, j] 中所有键的频率之和 都会因为根节点 k 的这一层而贡献一次成本。 因此，如果我们已经知道了左子树 [i, k-1] 的最小成本 dp[i][k-1] 和右子树 [k+1, j] 的最小成本 dp[k+1][j] ，那么以 k 为根的总成本为： cost = dp[i][k-1] + dp[k+1][j] + sum(freq[i] to freq[j]) 解释最后一项 sum(freq[i] to freq[j]) ： dp[i][k-1] 是左子树在当前结构下的成本。当我们把左子树挂到根 k 下面时，左子树里每个键的深度都增加了1，因此总成本增加了 (左子树所有键的频率和) 。 同理，右子树的总成本也增加了 (右子树所有键的频率和) 。 根节点 k 本身的深度在这一层是1，因此它的成本就是 freq[k] 。 将这三部分相加： 增加左子树的成本 + 增加右子树的成本 + 根节点的成本 = (左子树频率和) + (右子树频率和) + freq[k] = (从i到j的所有键的频率和) 。 所以，转移方程为： dp[i][j] = min( dp[i][k-1] + dp[k+1][j] + sum(freq[i..j]) ) ，其中 k 从 i 遍历到 j 。 边界情况 ： 如果 i > j ，说明这是一个空子树，成本为0。因此，当 k=i 时，左子树 [i, k-1] 即 [i, i-1] 是空的， dp[i][i-1] = 0 。同理，当 k=j 时， dp[j+1][j] = 0 。 如果 i == j ，即只有一个键，那么它自己就是根。 dp[i][i] = freq[i] 。这也可以通过状态转移方程得到： k 只能取 i ， dp[i][i] = dp[i][i-1] + dp[i+1][i] + sum(freq[i..i]) = 0 + 0 + freq[i] = freq[i] 。 计算顺序 由于计算 dp[i][j] 时需要知道更小区间 [i, k-1] 和 [k+1, j] 的结果，我们应该按区间长度 L 从小到大的顺序进行计算。 L = 0 ：区间长度为1（即 i = j ）。计算所有 dp[i][i] 。 L = 1 ：区间长度为2（即 i, j 相差1）。计算所有 dp[i][i+1] 。 ... L = n-1 ：区间长度为 n （即 i=1, j=n ）。计算 dp[1][n] 。 为了快速计算区间 [i, j] 的频率和 sum(freq[i..j]) ，我们可以预先计算一个前缀和数组 prefixSum ，使得 prefixSum[j] - prefixSum[i-1] 就等于 sum(freq[i..j]) 。 示例 键： [ 10, 12, 20 ] 频率：[ 34, 8, 50 ] 情况1：根为10 左子树：空，成本0 右子树：[ 12, 20]，需要计算其最小成本。对于子树[ 12,20 ]： * 根为12：成本 = 0 (左空) + 50 (右子树[ 20 ]) + (8+50) = 0+50+58=108 * 根为20：成本 = 8 (左子树[ 12 ]) + 0 (右空) + (8+50) = 8+0+58=66 所以子树[ 12,20 ]的最小成本是66。 总成本 = 0 + 66 + (34+8+50) = 66 + 92 = 158 情况2：根为12 左子树：[ 10 ]，成本34 右子树：[ 20 ]，成本50 总成本 = 34 + 50 + (34+8+50) = 84 + 92 = 176 情况3：根为20 左子树：[ 10,12]，需要计算其最小成本。对于子树[ 10,12 ]： * 根为10：成本=0+8+(34+8)=0+8+42=50 * 根为12：成本=34+0+(34+8)=34+0+42=76 所以子树[ 10,12 ]的最小成本是50。 右子树：空，成本0 总成本 = 50 + 0 + (34+8+50) = 50 + 92 = 142 比较三种情况，最小总成本是142，对应的树结构是20为根，10为左子，12为10的右子。 通过这个循序渐进的过程，我们可以系统地计算出给定键和频率下的最优二叉搜索树结构及其最小总搜索成本。