as i read some material about Optimal BST, i ran into a trouble.

for following key i find two optimal BST with Average Cost = 30. 1 optimal BST using Dynamic programming Algorithm and 1 by hand !

key : 1/ 2/ 3 /4/ 5

frequencies: 10 / 8/ 6/ 4/ 2

i think always the Optimal BST using dynamic programming always has a unique solution. am i wrong ? or may be we have 2 or more optimal BST and all is correct.

  • 1
    $\begingroup$ What have you tried? Have you tried looking for a case where you have two optimal BSTs? You might want to play around with small trees. It's not clear what you mean "two optimal BST using dynamic programming", especially since you haven't specified the specific algorithm; and it's not clear why we'd care whether a particular algorithm can produce a unique solution or not, as opposed to whether multiple optimal solutions exist (which you have already answered). $\endgroup$ – D.W. Jun 8 '14 at 22:24
  • $\begingroup$ Consider the case of two keys with equal frequencies. There are only two BSTs, and they have equal average cost. $\endgroup$ – JeffE Jun 11 '14 at 12:07

There can be multiple optimal BSTs. Consider keys/frequencies

$\qquad\displaystyle \Bigl(1,\frac{1}{4}\Bigr), \Bigl(2,\frac{1}{4}\Bigr), \Bigl(3,\frac{1}{4}\Bigr), \Bigl(4,\frac{1}{4}\Bigr)$;

all of the following trees have optimal average (weighted) search cost $2$:

enter image description here


Raphael is right: it is certainly possible to have several optimal trees, especially when all frequencies are equal.

To return to your specific example, also here you have two optimal trees, as you yourself have observed. Considering the keys $3-5$ as right subtree of the root $2$ we have to following possibilities (where the figure indicates frequencies). The "weighted pathlength", the average number of steps to find a key in the tree (starting with 1 step for the root) equals $2\cdot6+1\cdot4+2\cdot2$ and $1\cdot6+2\cdot4+3\cdot2$, respectively. Both equal to $20$.

  4           6
 / \           \
6   2           4

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.