ai< x < ai+1

suppose i=1 then

do<x< if

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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+3 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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,362 questions

55,788 answers

192,413 comments

90,933 users