3.数据结构课件cs01版

1、CHAPTER 10SEARCH STRUCTURES1 Optimal Binary Search Trees The best for static searching (without insertion and deletion)whileifdodoifwhileifdowhilewhiledoifdowhileif Which one is the best? It depends on how often we need to search each of the identifiers.An external (or failure) nodeAn internal nodeE

2、xtendedBinaryTrees External path length := whilevoidifdoforE = 2 + 2 + 2 + 3 + 4 + 4 = 17 Internal path length := I = 0 + 1 + 1 + 2 + 3 = 7E = I + 2nHW: p.480 #1That means thatwhen I gets larger,E gets larger as well. Worst case ( ? ) I = ? Best case ( ? ) I = ?skewedcomplete1 Optimal Binary Search

3、Trees Given n identifiers a1 a2 an, and the probability of searching for each ai is pi , then for the successful searches, the cost of any binary search tree is Notice that unsuccessful searches terminate at failure nodes.E0 a1 E1 a2 En1 an En where and for all identifiers in some Ei, the search ter

4、minates at the same failure node fi . If qi is the probability that the identifier we are searching for is in Ei , then the cost for the unsuccessful searches is 1 Optimal Binary Search TreesThe total cost of a binary search treewhere An optimal binary search tree for a set of identifiers is one tha

5、t minimizes the cost over all possible binary search trees for this identifier set.Note: Tp for computing the cost of a binary search tree is O( n ). But there are O( 4n / n3/2 ) distinct binary search trees with n identifiers!1 Optimal Binary Search TreesPlease read Example 10.1 on p.474An algorith

6、m with Tp = O( n2 ) Can you believe it?Ti j := OBST for ai+1 , , aj ( i j.ri j := root of Ti j ( ri i = 0 )wi j := weight of Ti j = ( wi i = qi )Ei ai+1 Ej1 aj Ejqi pi+1 qj1 pj qjwi jT0n with root r0n,weight w0n, andcost c0n .1 Optimal Binary Search TreesakLai+1ak1Rak+1ajTi j1 Optimal Binary Search

7、TreesThe total cost of a binary search treeci j = ?pk + cost( L ) + cost( R )+ weight( L ) + weight( R )= pk + ci, k1 + ck j + wi, k1 + wk j = wi j + ci, k1 + ck j Ti j is optimal ri j = k is such that Starting from Ti i = and ci i = 0, we can obtain Ton and c0n .1 Optimal Binary Search TreesExample

8、Let (a1, a2, a3, a4) = ( do, for, void, while ). Let ( p1, p2, p3, p4) = (3, 3, 1, 1) /16 and ( q0, q1, q2, q3, q4) = (2, 3, 1, 1, 1) /16 w00 = 2c00 = 0r00 = 0w11 = 3c11 = 0r11 = 0w22 = 1c22 = 0r22 = 0w33 = 1c33 = 0r33 = 0w44= 1c44 = 0r44 = 0w01 = 8c01 = 8r01 = 1w12 = 7c12 = 7r12 = 2w23 = 3c23 = 3r23 = 3w34 = 3c34 = 3r34 = 4w02 = 12c02 = 19r02 = 1w13 = 9c13 = 12r13 = 2w24 = 5c24 = 8r24 = 3w03 = 14c03 = 25r03 = 2w14 = 11c14 = 19r14 = 2w04 = 16c04 = 32r04 = 2fordovoidwhilej i =1j i =2j i =3j i =4T Wij = O( n + 1 j + i )Trij = O( j i )Let