edited by
4,564 views
5 votes
5 votes

Let $n=4$ and $(a_1, a_2, a_3, a_4)$=(do, if, int, while). Let $p(1:4)=\bigg (\dfrac{3}{8}, \dfrac{3}{8}, \dfrac{1}{8}, \dfrac{1}{8} \bigg)$ and $q(1:4)=\bigg(\dfrac{2}{8}, \dfrac{3}{8}, \dfrac{1}{8}, \dfrac{1}{8}, \dfrac{1}{8} \bigg)$ 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:

edited by

1 Answer

6 votes
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 ? 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.

So answer is B

edited by
Answer:

Related questions

3 votes
3 votes
1 answer
1
2 votes
2 votes
2 answers
2
2 votes
2 votes
1 answer
3
go_editor asked Aug 9, 2016
4,298 views
If there are n integers to sort, each integer had d digits and each digit is in the set $\{1, 2, \dots, k\}$, radix sort can sort the numbers in$O(d \: n \: k)$$O(d n^k)$...