7-3 最优二叉搜索树 分数 10 作者 任唯 单位 河北农业大学 设 S={x 1 ​ ,x 2 ​ ,...,x n ​ } 是有序集，且 x 1 ​ <x 2 ​ <...<x n ​ ，表示有序集S的二叉搜索树利用二叉树的结点来存储有序集中的元素。在该二叉搜索树中搜索一个元素x，结果有两种情形： 在二叉搜索树的内结点中找到 x=x i ​ （即找到了实结点），设这种情况的概率为 p i ​ 在二叉搜索树的叶节点中确定 x∈(x i ​ ,x i+1 ​ )（即找到了虚结点），设这种情况的概率为 q i ​ 设根节点的深度为0，存储元素 x i ​ 的结点深度为 c i ​ ，叶节点(x j ​ ,x j+1 ​ )的结点深度为 d j ​ ，在该二叉搜索树中进行一次搜索所需的平均比较次数为 m，那么有公式： m=∑ i=1 n ​ p i ​ (1+c i ​ )+∑ j=0 n ​ q j ​ d j ​ m又称为二叉搜索树 T 的平均路长，本题的要求是对于有序集 S 及其存取概率分布(q 0 ​ ,p 1 ​ ,q 1 ​ ,..,p n ​ ,q n ​ )，在所有表示有序集 S 的二叉搜索树中找出一颗具有最小平均路长的二叉搜索树。 image-20210225215359687.png 输入格式: 第一行给出有序集中的元素数量 n (2<n<10) 第二行给出内结点（实结点）的存取概率分布 p 1 ​ ,..,p n ​ 第三行给出叶节点（虚结点）的存取概率分布 q 0 ​ ,q 1 ​ ,..,q n ​ 输出格式: 第一行输出最小 m ，保留两位小数。 第二行先序遍历输出二叉树，对于实结点输出其编号，对于虚结点输出.，每一个符号后有一个空格，若有多个满足要求的二叉树，则输出根节点编号最小的。 输入样例: 3 0.50 0.1 0.05 0.15 0.1 0.05 0.05 输出样例: 1.50 1 . 2 . 3 . .

### 最优二叉搜索树的算法实现与计算方法 #### 动态规划解决最优二叉搜索树问题 为了构建一棵最优二叉搜索树（Optimal Binary Search Tree, OBST），可以采用动态规划的方法。该方法通过分解原问题为多个子问题并逐步求解，最终得到全局最优解。 对于给定的有序集合 \( S = \{a_1, a_2, \dots, a_n\} \)，以及对应的存取概率分布 \( C = \{q(0), p(1), q(1), p(2), \dots, p(n), q(n)\} \)，目标是最小化平均查找路径长度 \( t \)： \[ t = \sum_{i=1}^{n} p(i)(1 + d(i)) + \sum_{j=0}^{n} q(j)d(j). \] 其中： - \( d(i) \) 表示节点 \( a_i \) 的深度； - \( d(j) \) 表示空隙节点 \( (a_j, a_{j+1}) \) 的深度。 ##### 定义状态变量 定义以下三个数组用于记录中间结果： - \( c[i][j] \): 从 \( i \) 到 \( j \) 构造的一颗子树的最小代价。 - \( w[i][j] \): 从 \( i \) 到 \( j \) 的累积权重，\( w[i][j] = \sum_{k=i}^{j} p(k) + \sum_{k=i-1}^{j} q(k) \)[^2]。 - \( r[i][j] \): 从 \( i \) 到 \( j \) 的子树根节点索引。 初始条件设置为单个节点的情况，即当 \( i = j \) 时，有 \( c[i][i] = p(i) + q(i-1) + q(i) \). ##### 转移方程 对于任意区间 \( [i, j] \)，假设其根节点为 \( k \)，则可以通过枚举所有可能的根节点位置 \( k \in [i, j] \) 来更新 \( c[i][j] \): \[ c[i][j] = \min_{i \leq k \leq j} \{c[i][k-1] + c[k+1][j]\} + w[i][j]. \] 这里需要注意的是，当 \( k = i \) 或者 \( k = j \) 时，相应的左子树或者右子树为空，则对应部分的成本应视为零[^2]。 ##### 实现代码 以下是基于 Python 的动态规划实现代码： ```python def optimal_bst(p, q, n): INF = float('inf') # 初始化二维列表 c = [[0]*(n+2) for _ in range(n+2)] w = [[0]*(n+2) for _ in range(n+2)] r = [[0]*(n+2) for _ in range(n+2)] # 边界情况初始化 for i in range(1, n+2): w[i][i-1] = q[i-1] c[i][i-1] = 0 # 填充表格 for length in range(1, n+1): # 长度从1到n for i in range(1, n-length+2): j = i + length -1 w[i][j] = w[i][j-1] + p[j] + q[j] min_cost = INF # 寻找最佳分割点k for k in range(i, j+1): cost = c[i][k-1] + c[k+1][j] if cost < min_cost: min_cost = cost root = k c[i][j] = min_cost + w[i][j] r[i][j] = root return c[1][n], r # 测试数据 p = [0, 0.15, 0.10, 0.05, 0.10, 0.20] q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10] n = len(p)-1 cost, roots = optimal_bst(p, q, n) print(f"Minimum average search time: {cost}") for row in roots: print(row) ``` 此程序实现了寻找最优二叉搜索树的过程，并返回了最低成本和每段区间的根节点信息。 #### 平均路长计算方法 一旦得到了最优二叉搜索树结构之后，可以根据之前提到的公式重新遍历整棵树来精确计算实际的平均查找次数 \( t \)。这一步骤通常是在理论分析阶段完成，在具体应用中往往只需要知道如何构造这样的树即可[^1]。