最优二叉搜索树问题是指给定一个具有n个关键字的有序序列K=k1k2kn以及它们被访问的概率P=p1p2pn构建一棵二叉搜索树使得搜索某个关键字ki的平均比较次数最小。该问题称为最优二叉搜索树问题。假设给定一个有序序列K=12345以及它们被访问的概率P=0102030103。根据以上问题写出结论

对于给定的有序序列K和概率P，最优二叉搜索树的构建方式如下：

1. 将K数组扩展为K'= {0, k1, k2, ..., kn, n+1}，其中0和n+1是两个虚拟节点，表示小于K1和大于Kn的值。

2. 定义一个二维数组W[i][j]表示在K[i]到K[j]之间构建二叉搜索树的平均比较次数，定义C[i][j]表示W[i][j]的最小值。

3. 初始化C[i][i-1]=0，表示空树的平均比较次数为0。

4. 对于每个子序列K[i...j]，枚举根节点K[r]，计算W[i][j]，并更新C[i][j]为W[i][j]的最小值。

5. 最终所求的最优二叉搜索树的平均比较次数为C[1][n]。

对于本题中给定的有序序列K={1,2,3,4,5}，以及它们被访问的概率P={0.1,0.2,0.3,0.1,0.3}，根据以上算法可得到最优二叉搜索树的平均比较次数为2.3。其中，根节点为3，左子树为{1,2}，右子树为{4,5}。在搜索节点1时，需要比较2次，在搜索节点2时，需要比较3次，在搜索节点3时，需要比较1次，在搜索节点4时，需要比较3次，在搜索节点5时，需要比较2次。因此，平均比较次数为(0.12+0.23+0.31+0.13+0.3*2)=2.3