Question

(a) Construct a 2−3 tree for the list f,l,o,w,c,h,a,r,t,i,n,g. Use the alphabetical order of the letters to compare them and insert them successively starting with the empty tree.

(b) Assuming that the probabilities of searching for each of the keys (i.e., the letters) are the same, find the largest number and the average number of key comparisons for successful searches in this tree.

Full description plz

Answer 1

Given:They have been asked to construct a 2-3 tree for list f,l,o,w,c,h,a,r,t,i,n,g right from empty tree we have to insert them and need to find largest number and average number of key comparisons

My answer:(a)

This is 2-3 tree for f,l,o,w,c,h,a,r,t,i,n,g

(b) The largest number of key comparison in successful search will be in the search for f,o.the average number of key comparison will be the following expression

• 1/12 f(f)+1/12 f(l)+1/12 f(o)+1/12 f(w)+1/12 f(c)+1/12 f(h)+1/12 f(a)+1/12 f(r)+1/12 f(t)+1/12 f(i)+1/12 f(n)+1/12 f(g)

After solving this with level values we will get the answer.