I was given this 
Binary Search Tree. The question asks whether this tree can ever be optimal with $2.1$ expected comparisons, and I am completely lost on how to even approach this problem. Trying to construct weights for which this works seems impossible, but I also don't know how I would go about disproving the statement.
$\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
Suppose the probality of each element being searched by the node label itself is denoted by the node label itself. Then the expected cost is given by:
$1\times A + 2\times B + 3\times D + 4\times (C+E) = 2.1$ (given)
Also, we have $A+B+D+C+E = 1$ (probabilities)
From these two, we get $1\times B + 2\times D + 3\times (C+E) = 1.1$
In order to make this tree optimal, the search frequencies must follow the following inequalities:
$A \ge B+D+C+E$ [implies $A$ must be at least $0.5$]
$B \ge D+C+E$ [implies $B$ must be at least $0.25$]
$D \ge C$ and
$D \ge E$
This will give us $A+B+2D \ge 1.1$, which gives $D \ge C+E+0.1$. This, together with the above inequalities, somewhat forces your hand.
Since, $A\ge 0.5, B\ge 0.25$ we have $D+C+E\le 0.25$. This give us $0\le C+E\le 0.075$ and $0.175 \le D \le 0.25$. Thus maximum value $1\times A + 2\times B + 3\times D + 4\times (C+E)$ can get is $1\times 0.5 + 2\times 0.25 + 3\times 0.175 + 4\times 0.075 = 1.825 \le 2.1 ~~~~\square$
