最优二叉搜索树问题（带成功和失败频率版本）
字数 1910 2025-11-05 08:30:59

最优二叉搜索树问题（带成功和失败频率版本）

题目描述
假设我们有一组有序的关键字序列 \(K = [k_1, k_2, ..., k_n]\)，以及每个关键字被搜索成功的概率 \(P = [p_1, p_2, ..., p_n]\)。同时，我们还有 \(n+1\) 个虚拟键（表示搜索失败的情况），其概率序列为 \(Q = [q_0, q_1, ..., q_n]\)，其中 \(q_i\) 表示搜索值落在 \(k_i\) 和 \(k_{i+1}\) 之间的概率（边界情况：\(q_0\) 对应小于 \(k_1\) 的值，\(q_n\) 对应大于 \(k_n\) 的值）。目标是构建一棵二叉搜索树，使得所有搜索的期望代价最小。期望代价定义为每个节点的深度加一（即访问次数）乘以其概率的总和。

解题过程

  1. 问题分析

    • 二叉搜索树（BST）的搜索代价取决于树的结构。
    • 对于关键字 \(k_i\)，其搜索成功的代价为 \((深度 + 1) \times p_i\)。
    • 对于虚拟键（失败区间），搜索失败的代价为 \((深度 + 1) \times q_i\)。
    • 总期望代价为所有成功和失败情况的代价之和。

  2. 动态规划状态定义
    定义 \(dp[i][j]\) 表示由关键字 \(k_i, k_{i+1}, ..., k_j\) 构成的最优二叉搜索树的最小期望代价（其中 \(1 \leq i \leq j \leq n\)）。
    对于边界情况，当 \(j = i-1\) 时，子树为空，仅剩一个虚拟键 \(q_{i-1}\)，此时代价为 \(q_{i-1}\)。

  3. 状态转移方程

    • 考虑以 \(k_r\)（\(i \leq r \leq j\)）作为根节点时，左子树包含 \(k_i, ..., k_{r-1}\)，右子树包含 \(k_{r+1}, ..., k_j\)。
    • 左子树的期望代价为 \(dp[i][r-1]\)，右子树的期望代价为 \(dp[r+1][j]\)。
    • 当以 \(k_r\) 为根时，所有节点的深度增加 1，因此整棵子树的代价需加上所有概率之和（因为每个概率都被多乘了一次深度增量）。
    • 区间 \([i, j]\) 的概率总和为：

\[ w(i, j) = \sum_{t=i}^{j} p_t + \sum_{t=i-1}^{j} q_t \]

  • 状态转移方程：

\[ dp[i][j] = \min_{i \leq r \leq j} \left\{ dp[i][r-1] + dp[r+1][j] + w(i, j) \right\} \]

  • 基础情况：当 \(j = i-1\) 时，\(dp[i][i-1] = q_{i-1}\)。

  1. 计算顺序
    按区间长度 \(len = 0, 1, ..., n-1\) 递增计算：

    • \(len = 0\)：单个关键字，即 \(i = j\)，此时根节点唯一。
    • 逐步扩大区间长度，利用更短的区间结果。

  2. 示例计算
    假设 \(n=3\)，概率如下：

\[ P = [0.1, 0.2, 0.3], \quad Q = [0.05, 0.1, 0.15, 0.2] \]

  • 计算 \(w(i, j)\)：例如 \(w(1,3) = p_1+p_2+p_3 + q_0+q_1+q_2+q_3 = 0.1+0.2+0.3+0.05+0.1+0.15+0.2 = 1.1\)。
  • 计算 \(dp[1][1]\)：根为 \(k_1\)，左子树为空（代价 \(q_0\)），右子树为空（代价 \(q_1\)），总代价为 \(q_0 + q_1 + w(1,1) = 0.05 + 0.1 + (0.1+0.05+0.1) = 0.4\)。
  • 类似地计算所有区间，最终 \(dp[1][3]\) 即为最小期望代价。
  1. 算法复杂度
    • 时间复杂度：\(O(n^3)\)（三层循环：区间长度、起点、根位置）。
    • 空间复杂度：\(O(n^2)\)（存储 \(dp\) 表）。

关键点

  • 概率总和 \(w(i, j)\) 可通过前缀和预处理至 \(O(1)\) 查询。
  • 此问题体现了区间动态规划的典型结构：枚举根节点，合并左右子树最优解，并附加区间整体代价。
最优二叉搜索树问题（带成功和失败频率版本） 题目描述 假设我们有一组有序的关键字序列 \( K = [ k_ 1, k_ 2, ..., k_ n] \)，以及每个关键字被搜索成功的概率 \( P = [ p_ 1, p_ 2, ..., p_ n] \)。同时，我们还有 \( n+1 \) 个虚拟键（表示搜索失败的情况），其概率序列为 \( Q = [ q_ 0, q_ 1, ..., q_ n] \)，其中 \( q_ i \) 表示搜索值落在 \( k_ i \) 和 \( k_ {i+1} \) 之间的概率（边界情况：\( q_ 0 \) 对应小于 \( k_ 1 \) 的值，\( q_ n \) 对应大于 \( k_ n \) 的值）。目标是构建一棵二叉搜索树，使得所有搜索的 期望代价最小 。期望代价定义为每个节点的深度加一（即访问次数）乘以其概率的总和。 解题过程 问题分析 二叉搜索树（BST）的搜索代价取决于树的结构。 对于关键字 \( k_ i \)，其搜索成功的代价为 \( (深度 + 1) \times p_ i \)。 对于虚拟键（失败区间），搜索失败的代价为 \( (深度 + 1) \times q_ i \)。 总期望代价为所有成功和失败情况的代价之和。 动态规划状态定义 定义 \( dp[ i][ j] \) 表示由关键字 \( k_ i, k_ {i+1}, ..., k_ j \) 构成的 最优二叉搜索树的最小期望代价 （其中 \( 1 \leq i \leq j \leq n \)）。 对于边界情况，当 \( j = i-1 \) 时，子树为空，仅剩一个虚拟键 \( q_ {i-1} \)，此时代价为 \( q_ {i-1} \)。 状态转移方程 考虑以 \( k_ r \)（\( i \leq r \leq j \)）作为根节点时，左子树包含 \( k_ i, ..., k_ {r-1} \)，右子树包含 \( k_ {r+1}, ..., k_ j \)。 左子树的期望代价为 \( dp[ i][ r-1] \)，右子树的期望代价为 \( dp[ r+1][ j ] \)。 当以 \( k_ r \) 为根时， 所有节点的深度增加 1 ，因此整棵子树的代价需加上所有概率之和（因为每个概率都被多乘了一次深度增量）。 区间 \( [ i, j ] \) 的概率总和为： \[ w(i, j) = \sum_ {t=i}^{j} p_ t + \sum_ {t=i-1}^{j} q_ t \] 状态转移方程： \[ dp[ i][ j] = \min_ {i \leq r \leq j} \left\{ dp[ i][ r-1] + dp[ r+1][ j ] + w(i, j) \right\} \] 基础情况：当 \( j = i-1 \) 时，\( dp[ i][ i-1] = q_ {i-1} \)。 计算顺序 按区间长度 \( len = 0, 1, ..., n-1 \) 递增计算： \( len = 0 \)：单个关键字，即 \( i = j \)，此时根节点唯一。 逐步扩大区间长度，利用更短的区间结果。 示例计算 假设 \( n=3 \)，概率如下： \[ P = [ 0.1, 0.2, 0.3], \quad Q = [ 0.05, 0.1, 0.15, 0.2 ] \] 计算 \( w(i, j) \)：例如 \( w(1,3) = p_ 1+p_ 2+p_ 3 + q_ 0+q_ 1+q_ 2+q_ 3 = 0.1+0.2+0.3+0.05+0.1+0.15+0.2 = 1.1 \)。 计算 \( dp[ 1][ 1] \)：根为 \( k_ 1 \)，左子树为空（代价 \( q_ 0 \)），右子树为空（代价 \( q_ 1 \)），总代价为 \( q_ 0 + q_ 1 + w(1,1) = 0.05 + 0.1 + (0.1+0.05+0.1) = 0.4 \)。 类似地计算所有区间，最终 \( dp[ 1][ 3 ] \) 即为最小期望代价。 算法复杂度 时间复杂度：\( O(n^3) \)（三层循环：区间长度、起点、根位置）。 空间复杂度：\( O(n^2) \)（存储 \( dp \) 表）。 关键点 概率总和 \( w(i, j) \) 可通过前缀和预处理至 \( O(1) \) 查询。 此问题体现了区间动态规划的典型结构：枚举根节点，合并左右子树最优解，并附加区间整体代价。