关于最优TH—树的费用

对于一般形式的权序列的最优TH-树,本文给出了其费用比较定理和费用的上、下界.同时,对一些比较广泛的权序列的最优TH-树,也得到了清楚的费用公式.     

关于 L(S)的一点结果

设A_(m×n)是行和为R=(r_1,r_2,…,r_m)、列和为Q=(q_1,q_2 …,q_n)的(0,1)矩阵。设δ_i=(1,…,1,0,…,0),其中前r_i个位置为1,其余为0,A_(m×n)=称为A_(m×n)的极左矩阵,记其列和向量为S.设L(S)={S|SS,S的分量递降且为非负整数}。若S、TεL(S),S≠T,ST,且不存在V L(S),V≠S,V≠T,满足SVT,则称S是T的直接后继。设S=(S_1,S_2,…,S_n),T=(t_1,t_2,…,t_n),我们有定理1 若S是T的直接后继,则存在i、j’满足S_i+1=t_i,S_j-l=t_j,S_k=t_k(1≤k≤n,     

关于Huffman树费用的一些结果

Hu.T.C指出,对于一般给定的权序列,在构造出相应的Huffman树之前,尚未建立表达其费用的公式.因此,对某些特殊的权序列,给出Huffman树的费用公式是一个值得研究的课题.在文[2—5]中给出了几个权序列相应的Huffman树的费用公式.对一些较广泛的权序列类,本文得到了相应的Huffman树的费用公式.本文假设W:w_1≤w_2≤…≤w_n(w_1>0)为权序列,H(W)表示相应的Huffman树,C(W)表示H(W)的费用.