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

This is a very simple question, I will explain steps-by-steps:

First, you need to count total elements and total comparisons in your tree

Second, you need to know that for each element in the tree, it takes $\frac{total \ comparisons}{total \ elements}$ average comparisons to search for an element in the tree.

Third, if the problem gives you a probability to search for an element, you need to multiply it by each element.

Now back to your question:

  • Total elements = $10$, total comparisons = $1 \cdot 1 + 2 \cdot 2 + 3\cdot 3 + 2 \cdot 4 + 2\cdot 5 = 33$ (this is calculated by taking the total nodes at each level and multiply it by the level, you need to draw the tree to understand).
  • The tree has $5$ odd elements and $5$ even elements, you need to do now is to take the probability and multiply it by each element, which in your case is $\frac{1}{10} \cdot 5 + \frac{1}{25} \cdot 5 = \frac{1}{2} + \frac{1}{5} = \frac{7}{10}$.
  • Now your expected value is: $E(x) = \frac{33}{\frac{7}{10} \cdot 10} = \frac{33}{7}$, which is also the solution for your problem.
  • $\begingroup$ Your explanation is very clear, thank you so much! $\endgroup$ – Jennifer Apr 20 at 12:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.