4
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

I am thinking if jk = ik, let's denote jk=ik=m, then we think of subsequences of [0,m-1] and [m+1,n], treat [m+1,n] as a standalone tree. And according to the paper, T and T' will be of same weighted path length if αn = α. So let's make a tree of subsequence [m+1,n] with last item being α, with weighted path length sum being Tk. And then replace the right-subtree of jk/ik with Tk for both T and T'.

Let's denote the weighted path length sum of [0, m-1] of T and T' being T0 and T0'. Because jk = ik, the levels of T and T' are both k. SoC(T) = T0 + k*Ak + Tk(starting from level k+1); C(T') = T1 + k*Ak + Tk(starting from level k+1); And C(T) should be equal to C(T'). So T1 = T1'

Replace right subtree of ik of T with right subtree of jk of T' will yield T'' with same weighted path length as T'.

PS: actually I don't quite know how it proves j2<=i2, j3<=i3 using induction and left-right symmetry, anyone can help answer that?

$\endgroup$

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.