最优二叉搜索树的最优结构问题（扩展：带深度限制）
字数 3376 2025-12-07 07:53:59

最优二叉搜索树的最优结构问题（扩展：带深度限制）

题目描述

给定一个有序关键字集合 \(keys[1..n]\) 和对应的查找概率 \(p[1..n]\)（查找成功概率），以及 \(n+1\) 个“伪关键字”（表示不在树中的值）的概率 \(q[0..n]\)（查找失败概率）。其中，\(p_i\) 是查找关键字 \(keys[i]\) 的概率，\(q_j\) 是查找值落在区间 \((keys[j], keys[j+1])\) 的概率（约定 \(keys[0] = -\infty, keys[n+1] = +\infty\)）。

构造一棵二叉搜索树（BST），使得所有关键字和伪关键字的期望查找代价最小。
新增限制：树中任意叶节点到根节点的路径长度（深度）不能超过一个给定的整数 \(D\)（即树高受限制）。求此条件下的最小期望查找代价。

核心概念回顾（无深度限制的版本）

对于关键字 \(keys[i..j]\)，定义：

  1. 期望代价 \(e[i][j]\)：以 \(keys[i..j]\) 为关键字构造的 BST 的最小期望查找代价。
  2. 概率和 \(w[i][j] = \sum_{k=i}^{j} p_k + \sum_{k=i-1}^{j} q_k\)（即该子树中所有成功与失败概率之和）。

状态转移方程（经典最优 BST）：

\[e[i][j] = \min_{r=i}^{j} \left( e[i][r-1] + e[r+1][j] + w[i][j] \right) \]

其中 \(r\) 为根的关键字下标。
初始化：\(e[i][i-1] = q_{i-1}\)（空子树只有失败概率）。
目标：\(e[1][n]\)。

加入深度限制后的挑战

深度限制 \(D\) 意味着：从根到任意叶子的路径上最多有 \(D\) 条边（即最大深度为 \(D\)）。
因此，我们需要在状态中增加当前子树的允许最大深度。

状态设计

设 \(dp[i][j][d]\) 表示：

  • 关键字范围 \(keys[i..j]\)
  • 该子树在整棵树中的深度不能超过 \(d\)（即从该子树的根到其任意叶子的路径长度 ≤ \(d\)）。
  • 值：该条件下的最小期望查找代价。

注意：\(d\) 是从该子树根部开始计算的深度限制，而不是从整棵树的根。
若 \(d < 0\)，表示不可能（深度超过限制），值为无穷大。

状态转移

我们枚举该子树的根 \(r\)（\(i \le r \le j\)）：

  • 左子树关键字范围：\([i, r-1]\)
  • 右子树关键字范围：\([r+1, j]\)
  • 根 \(r\) 的深度比其父节点深 1，但我们在 \(dp[i][j][d]\) 中，\(d\) 是本子树的允许深度，所以左右子树允许的深度是 \(d-1\)。

转移方程：

\[dp[i][j][d] = \min_{r=i}^{j} \Big( dp[i][r-1][d-1] + dp[r+1][j][d-1] + w[i][j] \Big) \]

其中 \(w[i][j]\) 含义同上（概率和）。

为什么是 \(d-1\)？
因为如果本子树的深度限制是 \(d\)，那么左右子树作为本子树的子树，其根到叶的最大路径长度要减少 1（本子树的根占了一条边），所以它们允许的最大深度是 \(d-1\)。

初始化

  • 当子树为空（即 \(i > j\) 时）：
    此时子树只有一个“伪关键字”节点（失败叶子），其深度限制为 \(d\)。
    但该叶子节点在本子树中就是唯一的节点，它的查找代价是 \(q_{j}\)（注意：空子树对应 \(keys[i..j]\) 为空，伪关键字是 \(q_{i-1}\) 吗？要小心下标）。
    更准确：空子树对应区间 \([i, i-1]\) 表示关键字为空，只有伪关键字 \(q_{i-1}\)。
    所以初始化：

\[ dp[i][i-1][d] = q_{i-1} \quad \text{对任意 } d \ge 0 \]

如果 \(d < 0\)，则设为无穷大（不可能）。

  • 另外，对所有 \(i, j, d\) 先初始化为无穷大。

计算顺序

  1. 先计算 \(w[i][j]\)（预处理，\(O(n^2)\)）。
  2. 按区间长度 \(len = 0\) 到 \(n\) 递增计算。
  3. 对每个区间 \([i, j]\)，对 \(d\) 从 0 到 \(D\) 遍历。
  4. 枚举根 \(r\) 更新。

注意：\(d\) 可以到 \(D\)，但实际深度可能小于 \(D\)。

最终答案

整棵树的深度限制是 \(D\)，所以答案是：

\[\min_{d=0}^{D} dp[1][n][d] \]

为什么取 min ？因为 \(dp[1][n][d]\) 表示深度限制为 \(d\) 的最小代价，如果 \(d\) 更小可能得不到有效解（无穷大），但更大的 \(d\) 代价更小，我们选满足限制的最小代价。
实际上直接取 \(dp[1][n][D]\) 即可，因为如果 \(d\) 更大允许更深，代价不会更大（单调不增），但我们的定义是“深度不超过 \(d\)”，所以 \(dp[1][n][D]\) 就是允许深度不超过 \(D\) 的最小代价。

时间复杂度

状态数：\(O(n^2 D)\)
每个状态枚举根 \(O(n)\)
总复杂度：\(O(n^3 D)\)
可以用四边形不等式优化枚举根的部分到 \(O(n^2 D)\)，但这里不展开。

举例说明（简单情况）

设 \(n=2\)，关键字概率 \(p=[0.1, 0.2]\)，伪关键字概率 \(q=[0.05, 0.1, 0.15]\)，\(D=2\)。

  1. 计算 \(w\)：
    \(w[1][1] = p1+q0+q1 = 0.1+0.05+0.1=0.25\)
    \(w[2][2] = p2+q1+q2 = 0.2+0.1+0.15=0.45\)
    \(w[1][2] = p1+p2+q0+q1+q2 = 0.1+0.2+0.05+0.1+0.15=0.6\)

  2. 初始化空子树：
    \(dp[1][0][d] = q0=0.05\)（对所有 d≥0）
    \(dp[2][1][d] = q1=0.1\)
    \(dp[3][2][d] = q2=0.15\)

  3. 计算 \(dp[1][1][d]\)：
    只有根 r=1，左子树 [1,0]，右子树 [2,1]。
    \(dp[1][1][d] = dp[1][0][d-1] + dp[2][1][d-1] + w[1][1]\)
    需要 d≥1，否则 d-1<0 时左右子树无穷大。

    比如 d=1：
    \(dp[1][0][0]=0.05, dp[2][1][0]=0.1\)
    所以 = 0.05+0.1+0.25=0.4

  4. 类似计算 \(dp[2][2][d]\)，然后 \(dp[1][2][d]\) 枚举根 r=1,2 比较。

最终 \(dp[1][2][2]\) 即为答案。

关键点总结

  1. 状态增加一维“允许的深度”来满足深度限制。
  2. 转移时左右子树的允许深度减 1。
  3. 初始化空子树时，代价为对应伪关键字概率，且只要深度限制 ≥0 就允许。
  4. 最终答案为 \(dp[1][n][D]\)。

这样，我们就在经典最优 BST 问题上加入了深度限制，并用区间 DP 的三维状态解决了问题。

最优二叉搜索树的最优结构问题（扩展：带深度限制） 题目描述 给定一个有序关键字集合 \( keys[ 1..n] \) 和对应的查找概率 \( p[ 1..n] \)（查找成功概率），以及 \( n+1 \) 个“伪关键字”（表示不在树中的值）的概率 \( q[ 0..n] \)（查找失败概率）。其中，\( p_ i \) 是查找关键字 \( keys[ i] \) 的概率，\( q_ j \) 是查找值落在区间 \( (keys[ j], keys[ j+1]) \) 的概率（约定 \( keys[ 0] = -\infty, keys[ n+1 ] = +\infty \)）。 构造一棵二叉搜索树（BST），使得 所有关键字和伪关键字的期望查找代价最小 。 新增限制 ：树中任意叶节点到根节点的路径长度（深度）不能超过一个给定的整数 \( D \)（即树高受限制）。求此条件下的最小期望查找代价。 核心概念回顾（无深度限制的版本） 对于关键字 \( keys[ i..j ] \)，定义： 期望代价 \( e[ i][ j] \)：以 \( keys[ i..j ] \) 为关键字构造的 BST 的最小期望查找代价。 概率和 \( w[ i][ j] = \sum_ {k=i}^{j} p_ k + \sum_ {k=i-1}^{j} q_ k \)（即该子树中所有成功与失败概率之和）。 状态转移方程（经典最优 BST）： \[ e[ i][ j] = \min_ {r=i}^{j} \left( e[ i][ r-1] + e[ r+1][ j] + w[ i][ j ] \right) \] 其中 \( r \) 为根的关键字下标。 初始化：\( e[ i][ i-1] = q_ {i-1} \)（空子树只有失败概率）。 目标：\( e[ 1][ n ] \)。 加入深度限制后的挑战 深度限制 \( D \) 意味着：从根到任意叶子的路径上最多有 \( D \) 条边（即最大深度为 \( D \)）。 因此，我们需要在状态中 增加当前子树的允许最大深度 。 状态设计 设 \( dp[ i][ j][ d ] \) 表示： 关键字范围 \( keys[ i..j ] \) 该子树 在整棵树中的深度 不能超过 \( d \)（即从该子树的根到其任意叶子的路径长度 ≤ \( d \)）。 值：该条件下的最小期望查找代价。 注意：\( d \) 是从该子树 根部 开始计算的深度限制，而不是从整棵树的根。 若 \( d < 0 \)，表示不可能（深度超过限制），值为无穷大。 状态转移 我们枚举该子树的根 \( r \)（\( i \le r \le j \)）： 左子树关键字范围：\( [ i, r-1 ] \) 右子树关键字范围：\( [ r+1, j ] \) 根 \( r \) 的深度比其父节点深 1，但我们在 \( dp[ i][ j][ d] \) 中，\( d \) 是 本子树的允许深度 ，所以左右子树允许的深度是 \( d-1 \)。 转移方程： \[ dp[ i][ j][ d] = \min_ {r=i}^{j} \Big( dp[ i][ r-1][ d-1] + dp[ r+1][ j][ d-1] + w[ i][ j ] \Big) \] 其中 \( w[ i][ j ] \) 含义同上（概率和）。 为什么是 \( d-1 \)？ 因为如果本子树的深度限制是 \( d \)，那么左右子树作为本子树的子树，其根到叶的最大路径长度要减少 1（本子树的根占了一条边），所以它们允许的最大深度是 \( d-1 \)。 初始化 当子树为空（即 \( i > j \) 时）： 此时子树只有一个“伪关键字”节点（失败叶子），其深度限制为 \( d \)。 但该叶子节点在本子树中就是唯一的节点，它的查找代价是 \( q_ {j} \)（注意：空子树对应 \( keys[ i..j] \) 为空，伪关键字是 \( q_ {i-1} \) 吗？要小心下标）。 更准确：空子树对应区间 \( [ i, i-1] \) 表示关键字为空，只有伪关键字 \( q_ {i-1} \)。 所以初始化： \[ dp[ i][ i-1][ d] = q_ {i-1} \quad \text{对任意 } d \ge 0 \] 如果 \( d < 0 \)，则设为无穷大（不可能）。 另外，对所有 \( i, j, d \) 先初始化为无穷大。 计算顺序 先计算 \( w[ i][ j ] \)（预处理，\( O(n^2) \)）。 按区间长度 \( len = 0 \) 到 \( n \) 递增计算。 对每个区间 \( [ i, j ] \)，对 \( d \) 从 0 到 \( D \) 遍历。 枚举根 \( r \) 更新。 注意：\( d \) 可以到 \( D \)，但实际深度可能小于 \( D \)。 最终答案 整棵树的深度限制是 \( D \)，所以答案是： \[ \min_ {d=0}^{D} dp[ 1][ n][ d ] \] 为什么取 min ？因为 \( dp[ 1][ n][ d ] \) 表示深度限制为 \( d \) 的最小代价，如果 \( d \) 更小可能得不到有效解（无穷大），但更大的 \( d \) 代价更小，我们选满足限制的最小代价。 实际上直接取 \( dp[ 1][ n][ D] \) 即可，因为如果 \( d \) 更大允许更深，代价不会更大（单调不增），但我们的定义是“深度不超过 \( d \)”，所以 \( dp[ 1][ n][ D ] \) 就是允许深度不超过 \( D \) 的最小代价。 时间复杂度 状态数：\( O(n^2 D) \) 每个状态枚举根 \( O(n) \) 总复杂度：\( O(n^3 D) \) 可以用四边形不等式优化枚举根的部分到 \( O(n^2 D) \)，但这里不展开。 举例说明（简单情况） 设 \( n=2 \)，关键字概率 \( p=[ 0.1, 0.2] \)，伪关键字概率 \( q=[ 0.05, 0.1, 0.15 ] \)，\( D=2 \)。 计算 \( w \)： \( w[ 1][ 1 ] = p1+q0+q1 = 0.1+0.05+0.1=0.25 \) \( w[ 2][ 2 ] = p2+q1+q2 = 0.2+0.1+0.15=0.45 \) \( w[ 1][ 2 ] = p1+p2+q0+q1+q2 = 0.1+0.2+0.05+0.1+0.15=0.6 \) 初始化空子树： \( dp[ 1][ 0][ d ] = q0=0.05 \)（对所有 d≥0） \( dp[ 2][ 1][ d ] = q1=0.1 \) \( dp[ 3][ 2][ d ] = q2=0.15 \) 计算 \( dp[ 1][ 1][ d ] \)： 只有根 r=1，左子树 [ 1,0]，右子树 [ 2,1 ]。 \( dp[ 1][ 1][ d] = dp[ 1][ 0][ d-1] + dp[ 2][ 1][ d-1] + w[ 1][ 1 ] \) 需要 d≥1，否则 d-1 <0 时左右子树无穷大。 比如 d=1： \( dp[ 1][ 0][ 0]=0.05, dp[ 2][ 1][ 0 ]=0.1 \) 所以 = 0.05+0.1+0.25=0.4 类似计算 \( dp[ 2][ 2][ d] \)，然后 \( dp[ 1][ 2][ d ] \) 枚举根 r=1,2 比较。 最终 \( dp[ 1][ 2][ 2 ] \) 即为答案。 关键点总结 状态增加一维“允许的深度”来满足深度限制。 转移时左右子树的允许深度减 1。 初始化空子树时，代价为对应伪关键字概率，且只要深度限制 ≥0 就允许。 最终答案为 \( dp[ 1][ n][ D ] \)。 这样，我们就在经典最优 BST 问题上加入了深度限制，并用区间 DP 的三维状态解决了问题。