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

2 Answers 2

1
$\begingroup$

That proof in fact had an error, in exactly the step in the induction that your answer asks about. Knuth published an erratum about it the following year. See Item 2 in [1] (copied below). See also [2] for a tutorial with a different, correct proof.

[1] Knuth, D.E. Optimum binary search trees. Acta Informatica 1, 270 (1972) (see below).

[2] https://doi.org/10.1016/S0304-3975(96)00320-9


enter image description here

$\endgroup$
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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.