变换成本与距离 Optimal binary search tree 费用最小的o的费用就是和y之间的距离 ■ Binary Search Tree? ■C[x,yJ=C[yml+ twiddle可以 twiddle, a Search tree 可以 replace m Examples? cyn]=C1ymH+ delete可以 delet I Optimal: under some condition C区1yc[Xyn]k可以k m The elements appear with different ■最优子结构:最优解可以分解为子问题的最优解的综合。 frequencie a How to formally define it A search tree Definition for the optimal binary search tree istinct keys stored from smaller value to larger value a We need n+1 dummy keys for values not in K, these dummy keys are do d1,..., dn a The appearance probabilities of k and d are Find a search tree such that: 清华太学未证想 Cost of the searches are minimum The structure of an optimal binary search tree a The expectation cost of search: [See p358 a We need a structure that the optimal solution 15.16] can be constructed from one or many optimal ■ Esearch cost in solution for subproblems Sum[(depth(*)+1)pl+ a Any sub tree of binary search tree contains sum((depth()+1)如] the keys continuing from k to k, and also th Where p are the occurrence possibility of k, q dummy keys from d- to d6 清华大学 宋斌恒 31 变换成本与距离 n Cost(s)=SCost(ti ) n 我们称由x到y的费用最小的s的费用就是x和y之间的距离。 n 子问题空间如何确定: n C[xn ,ym]=C[xn-2 ,ym-2 ]+twiddle 可以 twiddle, n C[xn ,ym]=C[xn-1 ,ym-1 ]+copy 可以 copy, n C[xn ,ym]=C[xn-1 ,ym-1 ]+replace 可以 replace, n C[xn ,ym]=C[xn-1 ,ym]+delete 可以 delete, n C[xn ,ym]=C[xn ,ym-1 ]+insert 可以 insert, n C[xn ,ym]=C[xn-s ,ym]+kill 可以 kill, n 最优子结构：最优解可以分解为子问题的最优解的综合。 n 问题： 清华大学 宋斌恒 32 Optimal binary search tree n Binary Search Tree? n Binary tree n Search tree n Examples? n Optimal: under some condition: n The elements appear with different frequencies n How to formally define it? 清华大学 宋斌恒 33 A search tree k1 k3 k4 k2 d0 d1 d2 d3 d4 清华大学 宋斌恒 34 Definition for the optimal binary search tree n Given a sequence K=<k1 ,k2 ,… kn> of n distinct keys stored orderly from smaller value to larger value. n We need n+1 dummy keys for values not in K, these dummy keys are d0 ,d1 ,… ,dn n The appearance probabilities of ki and dj are given n Find a search tree such that: 清华大学 宋斌恒 35 Cost of the searches are minimum n The expectation cost of search:[See p358 15.16] n E[search cost in T]= Sum[(depth(ki )+1)*pi ]+ sum[(depth(di )+1)*qi ]+ Where pi are the occurrence possibility of ki , qi are the occurrence possibility of di 清华大学 宋斌恒 36 The structure of an optimal binary search tree n We need a structure that the optimal solution can be constructed from one or many optimal solution for subproblems n Any sub tree of binary search tree contains the keys continuing from ki to kj and also the dummy keys from di-1 to dj