有向树与最优树

有向树
定义：设T是有向树，如果它有一个结点的入度为0，其余结点的入度均为1，则称T为根树。入度为0的结点称为树根，出度非0的结点称为分支点，出度为0的点称为树叶。
从根结点到结点v的有向路长度称为v的层数。最大层数称为树的高度。

定义：如果T的分支点都至多有m个儿子，称T为m元树。若每个分支点都恰有m个儿子，称为正则m元树。若正则m元树的所有树叶都在同一层，称为完全m元树。

定理1. 正则二元树的分支点数i与树叶数t满足\(i=t-1\)。
定理2. 设T是一颗正则二元树，I表示各分支点的层数之和，E表示各树叶的层数之和，则\(E=I+2i\)。

最优树
定义：设二元树T有t片树叶\(v_1,\cdots, v_t\)，分别带权\(w_1,\cdots, w_t\in \mathbb R^+\)，则称T为赋权二元树，称\(w(T)=\sum\limits_{i=1}^t w_i\cdot l(v_i)\)为二元树T的权，其中\(l(v)\)是树叶v的层数。

定义：在所有含t片树叶，且叶子权重分别为\(w_1,\cdots,w_t\)的二元树中，权最小的二元树称为最优二元树。

给定正实数\(w_1,\cdots,w_t\)，构造一颗带权\(w_1,\cdots, w_t\)的最优二元树的哈夫曼算法可描述如下：
初始化\(S=\{w_1,\cdots,w_t\}, V=\{v_1,\cdots, v_t\}, E=\emptyset, w(v_i)=w_i\)；
从S中取出权最小的\(w_a,w_b\)，令\(w'=w_a+w_b\)；
更新S：删去\(w_a,w_b\)并加入\(w'\)， V中加入权为\(w'\)的结点\(v'\)，E中加入\(v'\)与\(v_a,v_b\)的连边；
当S只有一个元素时结束。

编码
定义：设\(A=\{\beta_1,\cdots, \beta_m\}\)是一个字符串集合，若对\(A\)中任意两个不同的码字\(\beta_i,\beta_j\)，都互相不是对方前缀，则称A为前缀码。

一个二元前缀码唯一对应一颗有序二元树。
给定字符集\(\{A_1,\cdots, A_t\}\)，及表示这些字符的二元前缀码\(\{\beta_1,\cdots, \beta_t\}\)，如果\(A_i\)出现的频率为\(w_i\)，码字\(\beta_i\)的长度为\(l_i\)，则用此二元前缀信息码表示信息花费的比特量是\(\sum\limits _{i=1}^t l_iw_i.\)

    所属分类：离散数学     发表于2022-08-23