最优二叉搜索树(带有查询失败情况)

最优二叉搜索树(不考虑查找失败的情况)详情见另一篇文章

这里是简单地介绍一些这个问题的解题思路,也是采用动态规划策略,思路也大致相似。

问题定义: 现有n个排好序的数\(a_1,a_2,\cdots,a_n\),并且它们的查找概率分别是 \(p_1,p_2,\cdots,p_n\),查找失败的概率为: \(q_0,q_1,q_2,\cdots,q_n\) 如何构造一颗二叉排序树,使得平均查找次数最少?

首先易知该问题满足最优子结构性质,可以采用动态规划求解,动态数组dp定义通上一篇文章。 定义\(A[i][j]\)表示序列 \(a_{i},a_{i+1},\cdots,a_j\)对应的最优二叉排序树下的最小查询次数。因此原问题就是要求解 \(A[1][n]\)

不同的是分析状态转移方程。

这里需要将查找失败的情况当做与父亲节点同高度的虚拟节点,初始化就比较好分析。当选择某一个节点k作为根节点时,左右子树的所有节点的高度都增加1(包括真实节点和虚拟节点1)。这样额外的开销可以分为三个部分:左子树\(\sum^{k-1}_{x=i}p_x\), \(\sum^{k-1}_{x=i-1}q_x\) ,右子树 \(\sum^{j}_{x=k+1}p_x\), \(\sum^{j}_{x=k}\),根节点 \(p_k\)。

累加起来就是 \(\sum^{j}_{x=i}p_x+\sum^{j}_{x=i-1}q_x\)

那么状态转移方程就是: \(A[i][j]=\mathop{min}_{i\leq k\leq j} \{ A[i][k-1]+A[k+1][j] + \sum^{j}_{x=i}p_x+\sum^{j}_{x=i-1}q_x \}\)

比不考虑查询失败情况下多加了一项而已。

考虑边界和初始化情况,当i>j时,视为空树,代价为0。当i=j时,代价为\(p_i+q_{i-1}+q_i\)符合状态转移方程的定义,因此后续的逻辑就是正确的。

求解过程,自底向上求解,最终求出 \(A[1][n]\)

时间复杂度上界同样是 \(O(n^3)\),空间复杂度 \(O(n^2)\)

练习:

答案:

发表评论

电子邮件地址不会被公开。 必填项已用*标注