V
Varun
Guest
Varun Asks: Optimal Binary Search Trees Knuth
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.
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.
SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.