w(T)=2÷4+424+7÷3+ 122+8÷2+10*2=105 22s 7 28 22 20 10 4
w(T)=2*4+4*4+7*3+ 12*2+8*2+10*2=105
Theorem 5.22 Let t be built according to Huffman algorithm and leaves of T with weight W1,W2,.,w Then T is an optimal tree(Where w,sw2<w3 s. <wk). Proof: Let us apply induction on the number n of vertices The results holds Suppose that result holds for n=k-1 For n=k, By the inductive hypothesis Suppose that nodes in an optimal tree T have weights W1+W2, W3,..., WK. Then This is an optimal tree with weight W1,W2, W3,.,Wk ifTs leaf with weight w1+W2 is replaced by subtree w1+w2
▪ Theorem 5.22: Let T be built according to Huffman algorithm and leaves of T with weight w1 ,w2 ,,wn . Then T is an optimal tree (Where w1w2w3 wk ). ▪ Proof: Let us apply induction on the number n of vertices. ▪ n=2, The results holds Suppose that result holds for n=k-1 For n=k， By the inductive hypothesis, Suppose that nodes in an optimal tree T have weights w1+w2 ,w3 ,,wk . Then This is an optimal tree with weight w1 ,w2 ,w3 ,,wk if T’s leaf with weight w1+w2 is replaced by subtree