中国高校课件下载中心 》 教学资源 》 大学文库

复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)18/30

文档信息
资源类别:文库
文档格式:PPT
文档页数:23
文件大小:568KB
团购合买:点击进入团购
内容简介
复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)18/30
刷新页面文档预览

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

字母 频率003560.0139002790.03780.13040.02890.01990.05280.06270.00130.0420.03900249 字母 频率00070.07970.01994000200670.06070.1050.02490.00210.01490007001990.008

字 母 a b c d e f g h i j k l m 频 率 0.0356 0.0139 0.0279 0.0378 0.1304 0.0289 0.0199 0.0528 0.0627 0.0013 0.042 0.0339 0.0249 字 母 n o p q r s t u V w x y z 频 率 0.0707 0.0797 0.0199 0.0012 0.0677 0.0607 0.1045 0.0249 0.0092 0.0149 0.0017 0.0199 0.0008

Definition 32: Let t be a tree with weigths wi sw2s.wl, where li is the path length from the root to vertex i. Say that a binary tree t is optimal if w(T) has its minimum value over all possible trees with the same set of leaf nodes

Definition 32: Let T be a tree with weigths w1w2...wn at its leaf nodes. The weighted leaf path length w(T) of T is W(T)=  = n i i i w l 1 , where li is the path length from the root to vertex i. Say that a binary tree T is optimal if w(T) has its minimum value over all possible trees with the same set of leaf nodes

Example: Let t be a binary tree with weigths 3, 5, 7, 9 a)∑l=48 b)∑w1=47

Example: Let T be a binary tree with weigths 3, 5, 7, 9 a ) = 48, i i w l b)  = 47, i i w l

Huffman algorithm Let aj,a2,..., an be n vertex with weight W1, W2,..., wn and w1≤W2S.W F:forest of n rooted tree each consisting of the single vertex a: with weight w for i=1, 2,on While f is not a tree Begin Replace the rooted trees t and t' of least weights from F with w(t)2w(T')with a tree having a new root that has Tas its left subtree and t'as its right subtree Assign w(T)+w(T) as the weight of the new tree. en d w1+w2 2

▪ Huffman algorithm: ▪ Let a1 ,a2 ,,an be n vertex with weight w1 ,w2 ,,wn and w1w2wn。 ▪ F:=forest of n rooted tree each consisting of the single vertex ai with weight wi for i=1,2,...n. ▪ While F is not a tree ▪ Begin ▪ Replace the rooted trees T and T’ of least weights from F with w(T)≥ w(T’) with a tree having a new root that has T as its left subtree and T’ as its right subtree. Assign w(T)+w(T’) as the weight of the new tree. ▪ end

Example: Find a optimal tree with weight 2,4,7,8,10,12

▪ Example: Find a optimal tree with weight 2,4,7,8,10,12

共23页,试读已结束,阅读完整版请下载
刷新页面下载完整文档
VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
相关文档