patternMinor
Average number of comparisons to locate item in BST
Viewed 0 times
itemnumberbstaveragelocatecomparisons
Problem
This is a GRE practice question.
If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (nodes) in the tree chosen at random?
(A) 1.75
(B) 2
(C) 2.75
(D) 3
(E) 3.25
My answer was 3 because $n=8$ and $\lg(n)$ comparisons should be made, and $\lg(8) = 3$. But the correct answer is 2.75. Can someone explain the correct answer? Thanks!
If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (nodes) in the tree chosen at random?
(A) 1.75
(B) 2
(C) 2.75
(D) 3
(E) 3.25
My answer was 3 because $n=8$ and $\lg(n)$ comparisons should be made, and $\lg(8) = 3$. But the correct answer is 2.75. Can someone explain the correct answer? Thanks!
Solution
Recall, how expected value is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then
$$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$
where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the average over the $C(X)$s.
$$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$
where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the average over the $C(X)$s.
Context
StackExchange Computer Science Q#6085, answer score: 8
Revisions (0)
No revisions yet.