ai< x < ai+1

suppose i=1 then

do<x< if

I don't understand. Please clarify....

The Gateway to Computer Science Excellence

+5 votes

Let n=4 and $(a_1, a_2, a_3, a_4)$=(do, if, int, while). Let p(1:4)=$(\frac{3}{8}, \frac{3}{8}, \frac{1}{8}, \frac{1}{8})$ and q(1:4)=$(\frac{2}{8}, \frac{3}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8})$ where p(i) and q(i) denotes the probability with which we search $a_i$ and the identifier $x$ being searched satisfy $a_i < x < a_{i+1}$ respectively. The optimal search tree is given by:

0

what are we comparing in this question?

ai< x < ai+1

suppose i=1 then

do<x< if

I don't understand. Please clarify....

ai< x < ai+1

suppose i=1 then

do<x< if

I don't understand. Please clarify....

0

a(i) < x < a(i+1) is nothing but a comparison criteria of searching.

If we search something (= x) in between * do* and

+6 votes

search success nodes (or keys) are

< do , if , int , while > in ascending order.

a(i) < x < a(i+1) is nothing but a comparison criteria of searching.

If we search something (= p) in between *do* and *if. *We would not be able to find p because we simply don't have such node (=p). We can consider that a search failure node, since p is not there in the binary search tree. Corresponding search probabilities of pi given in the question as q[ ] array. Since we have 4 nodes do,if,int,while we have five location of fail search (how five ? **p**1 do **p****2 if p3 int p4 while p5**) So, five locations where possibility of search failure is there.

If we see all the nodes in ascending order they are :

`p1,do,p2,if,p3,int,p4,while,p5 with probability of search 3/8, 3/8, 1/8, 1/8, 2/8, 3/8, 1/8, 1/8, 1/8.`

Option C and D are invalid tree.

So answer is B

52,218 questions

59,891 answers

201,086 comments

118,129 users