老师出了个变态二叉搜索树（BST）有关问题，求大神感激不尽
老师出了个变态二叉搜索树（BST）问题，求大神感激不尽
二叉搜索树（BST，或称二叉排序树）是一颗满足如下条件的二叉树
1.每个节点包含一个键值（关键字值）
2.每个节点有最多两个孩子
3.对于任意两个节点x和y，它们满足下述搜索性质：
a）如果y在x的左子树里，则key[y] <= key[x]
b) 如果y在x的右子树里，则key[y] >= key[x]
问题：
n个键{a1,a2,a3......an},a1 < a2 <...< an，其相应的查找概率为{p1,p2,p3......pn}。构成最优BST，希望用最少的键值比较次数找到每个关键码（键值）即如何构造这颗最优BST，使得这颗树的平均查找次数C[1，N]最小。
C[i，j]表示由{ai,ai + 1,......aj}构成的BST的平均查找次数。
1.利用动态规划求解该问题，如何分段？
2.写出求C[i，j]的递推方程
3.写出求解该问题的描述性算法
4.写出实现该算法的程序代码
------解决方案--------------------
google Static Optimal BSTs, 隐约记得最好的算法能达到 O(n^2).
------解决方案--------------------
普通的做法n^3，CLRS上一个有提示的练习题可以让你写出n^2，那个办法也是已知的最好的。OBST不少变种可以做到低平方，但是OBST本身还没找到低平方的。
爱莉prpr（
------解决方案--------------------
加点赫夫曼树的思想就o了
二叉搜索树（BST，或称二叉排序树）是一颗满足如下条件的二叉树
1.每个节点包含一个键值（关键字值）
2.每个节点有最多两个孩子
3.对于任意两个节点x和y，它们满足下述搜索性质：
a）如果y在x的左子树里，则key[y] <= key[x]
b) 如果y在x的右子树里，则key[y] >= key[x]
问题：
n个键{a1,a2,a3......an},a1 < a2 <...< an，其相应的查找概率为{p1,p2,p3......pn}。构成最优BST，希望用最少的键值比较次数找到每个关键码（键值）即如何构造这颗最优BST，使得这颗树的平均查找次数C[1，N]最小。
C[i，j]表示由{ai,ai + 1,......aj}构成的BST的平均查找次数。
1.利用动态规划求解该问题，如何分段？
2.写出求C[i，j]的递推方程
3.写出求解该问题的描述性算法
4.写出实现该算法的程序代码
------解决方案--------------------
google Static Optimal BSTs, 隐约记得最好的算法能达到 O(n^2).
------解决方案--------------------
普通的做法n^3，CLRS上一个有提示的练习题可以让你写出n^2，那个办法也是已知的最好的。OBST不少变种可以做到低平方，但是OBST本身还没找到低平方的。
爱莉prpr（
------解决方案--------------------
加点赫夫曼树的思想就o了