Path Length of Binary Search Trees.

摘要

Three new algorithms are introduced in the present paper. The first algorithm constructs a minimum cost tree with restricted maximum path length. (i.e. Huffman's tree with restricted maximum path length.) The second algorithm constructs a minimum cost feasible tree with minimum path length. (Feasible trees are trees satisfying the alphebetical ordering restrictions). The third algorithm constructs a canonical minimum cost tree,and illustrates that Huffman's algorithm is a special case of the T-C algorithm. (Author)