Rooted tree and binary tree Theorem 5.19: A full binary tree with t leaves contains i=t-l internal vertices
▪ Rooted tree and binary tree ▪ Theorem 5.19: A full binary tree with t leaves contains i=t-1 internal vertices
Theorem 5.20: Let t be a full binary tree. We denote the sum of length of simple paths from root to all internal vertices by l, and the sum of length of simple paths from root to all leaves by E. Then E=I+2i. where i is the number of internal vertices Proof: Let us apply induction on the number i of internal vertices E=2 and =o when i=l
▪ Theorem 5.20: Let T be a full binary tree. We denote the sum of length of simple paths from root to all internal vertices by I, and the sum of length of simple paths from root to all leaves by E. Then E=I+2i, where i is the number of internal vertices. ▪ Proof: Let us apply induction on the number i of internal vertices. ▪ E=2 and I=0 when i=1
Suppose that result holds for i=k-1 For i=k, we chose internal vertex v so that its children are leaves. we have a new tree which is obtained by omitting edges of incident v and its children By the inductive hypothesis, E =T+2(k-1) We denote the length of path from root to v by l E'=E-l-2,I=I-l. E=E+H2=+2(k-1)+2=l-+2(k-1)+l+2=I+2k Let T be a full m-ary tree. Then E=(m-1)l+mi, where i is the number of internal vertices
▪ Suppose that result holds for i=k-1 ▪ For i=k, we chose internal vertex v so that its children are leaves. We have a new tree which is obtained by omitting edges of incident v and its children. ▪ By the inductive hypothesis, E'=I'+2(k-1) ▪ We denote the length of path from root to v by l. ▪ E'=E- l-2, I'=I-l. ▪ E= E'+l+2=I'+2(k-1)+l+2=I-l+2(k-1)+l+2=I+2k。 ▪ Let T be a full m-ary tree. Then E=(m-1)I+mi, where i is the number of internal vertices
5.6 Prefix codes and optimal tree a b c d e 001100101001 The set 00, 110,010, 10,01 is called code 010010 ead or cc? The string of e is prefix of string of c c:111 The set 100, 110, 111, 10,01 is called prefix code
5.6 Prefix codes and optimal tree ▪a b c d e ▪00 110 010 10 01 ▪The set {00,110,010,10,01} is called code ▪010010 ▪ead or cc? ▪The string of e is prefix of string of c ▪c: 111 ▪The set {00,110,111,10,01}is called prefix code
Definition 31: Codes with this property which the bit string for a letter never occurs as the first part of the bit string for another letter are called prefix codes Theorem 5.21: We can construct a prefix code from any binary tree, and we can construct a binary tree from the prefix codes. Proof:(1)We can construct a prefix code from any binary tree where the left edge at each internal vertex is labeled by 0 and the right edge by a 1 and where the leaves are labeled by characters (2)We can construct a binary tree from the prefix codes
▪ Definition 31: Codes with this property which the bit string for a letter never occurs as the first part of the bit string for another letter are called prefix codes. ▪ Theorem 5.21: We can construct a prefix code from any binary tree, and we can construct a binary tree from the prefix codes. ▪ Proof: (1) We can construct a prefix code from any binary tree where the left edge at each internal vertex is labeled by 0 and the right edge by a 1 and where the leaves are labeled by characters ▪ (2)We can construct a binary tree from the prefix codes