1.8k views

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:

recategorized | 1.8k views
0
what are we comparing in this question?

ai< x < ai+1

suppose i=1 then

do<x< if

0

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

If we search something (= x) in between do and if. We would not be able to find x because we simply don't have such node (=x). We can consider that a search failure node, since x is not there in the binary search tree. Corresponding search probabilities of xi 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 ? x1 do x2 if x3 int x4 while x5) So, five locations where possibility of search failure is there.

0
ok that I understand.. but,, Is x some integer value or string?
0
In this problem x is string but the situation is generic where x can be integer if we talk about integer keys.
0
ok got it ...thanks :)

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 ? p1 do p2 if pint 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.

by Veteran (56.8k points)
edited by
0
You did not consider unsuccessful search scenario probability.

1
2
3
4
5
6