A binary search tree is constructed by inserting the following value sequentially:
$$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$ Let $p_v$ be the probability to search for the value $v$ in the binary search tree (for $1\leq v\leq10)$.

$p_v = \frac{1}{25}$ if $v$ is an even number and $p_v = \frac{1}{10}$ if $v$ is an odd number. Determine the average number of comparisons for a successful search of a prime number in a binary search tree.

I know that I have to calculate the expected value, but I don't know where to start. Any help to solve this problem is greatly appreciated.

This is what I have tried:

  • To search for number 3, it takes 1 comparison.
  • To search for number 7, it takes 5 comparisons.
  • To search for number 2, it takes 3 comparisons.
  • To search for number 5, it takes 5 comparisons.

So the average number of comparison to search for a prime number is:
$$\frac{1+5+3+5}{33} = \frac{14}{33}$$

  • $\begingroup$ Please credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$ – D.W. Apr 20 at 5:24
  • 1
    $\begingroup$ We're not looking for posts that are just the statement of an exercise-style task and a request for us to solve it for you / a statement that you don't know where to start. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Apr 20 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.