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.

(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.

Consider permutations of the 26-character lowercase alphabet
Σ={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}.
In how many of these permutations do
a,b,c occur consecutively and in that
order?
In how many of these permutations does a appear before
b and b appear before c?

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 1 minute ago

asked 8 minutes ago

asked 37 minutes ago

asked 39 minutes ago

asked 42 minutes ago

asked 47 minutes ago

asked 51 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago