首页 > 试题广场 >

5. 设S=｛X1 ，X2 ，···，X

[问答题]

5. 设S=｛X₁ ，X₂ ，···，X_n ｝是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X_i ，其概率为b_i 。（2）在二叉搜索树的叶结点中确定X∈（X_i ，X_i+1 ），其概率为a_i 。在表示S的二叉搜索树T中，设存储元素X_i 的结点深度为C_i ；叶结点（X_i ，X_i+1 ）的结点深度为d_i ，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]=｛X_i ，X_i+1 ，···，X_j ｝最优值为m[i][j]，W[i][j]= a_i-1+b_i+···+b_j+a_j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？