设S = {X1, X2, , … , X𝑛}是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，(1)在二叉搜索树中找到X = 𝑋i，其概率为𝑏𝑖；(2) 在二叉搜索树的叶结点中确定X ∈ (𝑋𝑖,𝑋𝑖+1)，其概率为𝑎𝑖.在表示S的 二叉搜索树T中，设存储元素𝑋𝑖的结点深度为c𝑖; 叶结点(𝑋𝑖,𝑋𝑖+1)的结点深度为d𝑖,则二叉搜
索树T的平均路长p为多少？假设二叉搜索树T[i][j] ={𝑋𝑖,𝑋𝑖+1, … , 𝑋𝑗}的最优值为m[i][j]，
w[i][j] = 𝑎𝑖−1 + 𝑏𝑖 + ⋯ + 𝑏𝑗 + 𝑎𝑗,则m[i][j]递归表达式为什么？
（含图）
收藏
