Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289

Please have a look at this paper, specifically page 18 in which he tries to prove his lemma that $R_{0,n-1} \leq R_{0,n} $ here $R$ refers to the minimal optimal node which will be the root of the binary tree containing elements $a_{0} ... a_{n} $ .

I understood the idea of the proof using induction that for some $k \, j_{k}=i_{k} $ . Now the next part of the proof is cutting and replacing,I have understood perfectly till there. What i don't understand is how $F''$ weighted path length is equal to weighted path length of $F'$ for all $a_{n}$. Can anyone please give me a hint or a solution to that.


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.