Q.3: Find the optimal binary merge tree (pattern) for ten files whose length are. 28, 32, 12,5,84,53,91, 35, 3 and 11 also find its weighted external path length.

Answer:

For obtaining optimal binary merge pattern merge two smallest size files at each step

Figure shows a binary image pattern representing the optimal merge pattern obtained for the above 10 files

Weighted external path length

Where di = distance from the route to the external node

Qi = the length of Xi

Here n = 10

Therefore ∑diqi=d1q1+d2q2+….+d10q10

=(4x28) + (3x32)+(5x12)+(7x5)+(2x84)+(3x53)+(2x91)+(3x35)+(7x3)+(6x11)

=112+96+60+35+168+159+182+105+21+66

=1004 (Answer)

notes For Error Please Whatsapp @9300930012