大二上学习数据结构lec

1、Static DictionariesCollection of items.Each item is a pair.(key, element)Pairs have different keys.Operations are:initialize/createget (search)Each item/key/element has an estimated access frequency (or probability).Consider binary search tree only.ExampleKeyProbabilitya0.8b0.1c0.1abca b cCost = 0.8

2、 * 2 + 0.1 * 1 + 0.1 * 2 = 1.9abcCost = 0.8 * 1 + 0.1 * 2 + 0.1 * 3 = 1.2Search TypesSuccessful.Search for a key that is in the dictionary.Terminates at an internal node.Unsuccessful.Search for a key that is not in the dictionary.Terminates at an external/failure node.f0abcf1f2f3Internal And Externa

3、l NodesA binary tree with n internal nodes has n + 1 external nodes.Let s1, s2, , sn be the internal nodes, in inorder.key(s1) key(s2) key(sn).Let key(s0) = infinity and key(sn+1) = infinity.Let f0, f1, , fn be the external nodes, in inorder.fi is reached iff key(si) search key key(si+1).f0abcf1f2f3

4、Cost Of Binary Search TreeLet pi = probability for key(si).Let qi = probability for key(si) search key key(si+1).Sum of ps and qs = 1.Cost of tree = S0 = i = n qi (level(fi) 1) + S1= i = n pi * level(si)Cost = weighted path length.f0abcf1f2f3Brute Force AlgorithmGenerate all binary search trees with

5、 n internal nodes.Compute the weighted path length of each.Determine tree with minimum weighted path length.Number of trees to examine is O(4n/n1.5).Brute force approach is impractical for large n.Dynamic ProgrammingKeys are a1 a2 an.Let Ti j= least cost tree for ai+1, ai+2, , aj.T0n= least cost tre

6、e for a1, a2, , an.a3a5a6a7a4f2f3f5f4f7f6Ti j includes pi+1, pi+2, , pj and qi, qi+1, , qj.T2,7Ti j= least cost tree for ai+1, ai+2, , aj.ci j= cost of Ti j = Si = u = j qu (level(fu) 1) + Si u = j pu * level(su).ri j= root of Ti j.wi j= weight of Ti j = sum of ps and qs in Ti j = pi+1+ pi+2+ + pj +

7、 qi + qi+1 + + qjTerminologyi = jTi j includes pi+1, pi+2, , pj and qi, qi+1, , qj.Ti i includes qi only.fiTiici i = cost of Ti i = 0.ri i = root of Ti i = 0.wi i = weight of Ti i = sum of ps and qs in Ti i = qii jTi j= least cost tree for ai+1, ai+2, , aj.Ti j includes pi+1, pi+2, , pj and qi, qi+1

8、, , qj.Let ak, i k = j, be in the root of Ti j.akLRTi jL includes pi+1, pi+2, , pk-1 and qi, qi+1, , qk-1.R includes pk+1, pi+2, , pj and qk, qk+1, , qj.cost(L)L includes pi+1, pi+2, , pk-1 and qi, qi+1, , qk-1.cost(L) = weighted path length of L when viewed as a stand alone binary search tree.LCont

9、ribution To cijci j = Si = u = j qu (level(fu) 1) + Si u = j pu * level(su).When L is viewed as a subtree of Ti j , the level of each node is 1 more than when L is viewed as a stand alone tree. So, contribution of L to cij is cost(L) + wi k-1.LakLRTi jcijContribution of L to cij is cost(L) + wi k-1.

10、Contribution of R to cij is cost(R) + wkj.cij = cost(L) + wi k-1 + cost(R) + wkj + pk = cost(L) + cost(R) + wijakLRTi jcijcij = cost(L) + cost(R) + wijcost(L) = cik-1cost(R) = ckjcij = cik-1 + ckj + wijDont know k.cij = mini k = jcik-1 + ckj + wijakLRTi jcijcij = mini k = jcik-1 + ckj + wijrij = k t

11、hat minimizes right side.akLRTi jComputation Of c0n And r0nStart with ci i = 0, ri i = 0, wi i = qi, 0 = i = n (zero-key trees).Use cij = mini k = jcik-1 + ckj + wij to compute cii+1, ri i+1, 0 = i = n 1 (one-key trees).Now use the equation to compute cii+2, ri i+2, 0 = i = n 2 (two-key trees).Now use the equation to compute cii+3, ri i+3, 0 = i = n 3 (three-key trees).Continue until c0n and r0n(n-key tree) have been computed.Computation Of c0n And r0ncij, rij, i = j1234123400Complexity cij = mini k = jcik-1 + ckj + wij O(n) time to compute one cij. O(n2) cijs to compute.Total time is O(n3