问答题X 纠错
设S={X1,X2,···,Xn}是严格递增的有序集,利用二叉树的结点来存储S中的元素,在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形: (1)在二叉搜索树的内结点中找到X=Xi,其概率为bi。 (2)在二叉搜索树的叶结点中确定X∈(Xi,Xi+1),其概率为ai。 在表示S的二叉搜索树T中,设存储元素Xi的结点深度为Ci;叶结点(Xi,Xi+1)的结点深度为di,则二叉搜索树T的平均路长p为多少?假设二叉搜索树T[i][j]={Xi,Xi+1,···,Xj}最优值为m[i][j],W[i][j]= ai-1+bi+···+bj+aj,则m[i][j](1<=i<=j<=n)递归关系表达式为什么?
二叉树T的平均路长
你可能喜欢
问答题
①问题具有最优子结构性质; ②构造最优值的递归关系表达式; ③最优值的算法描述; ④构造最优解;
填空题
O(n*2n);O(min{nc,2n})
赞题库-搜题找答案
(已有500万+用户使用)
无需下载 立即使用
版权所有©考试资料网(ppkao.com)All Rights Reserved