Answers are grounded in this paper and cite their sources.
An algorithm is given for constructing an alphabetic binary tree of minimum weighted path length (for short, an optimal alphabetic tree). The algorithm needs 4n² + 2n operations and $4n$ storage locations, where n is the number of terminal nodes in the tree. A given binary tree corresponds to a computer search procedure, where the given files or letters (represented by terminal nodes) are partitioned into two parts successively until a particular file or letter is finally identified. If the files or letters are listed alphabetically, such as a dictionary, then the binary tree must have, from left to right, the terminal nodes consecutively. Since different letters have different frequencies (weights) of occurring, an alphabetic tree of minimum weighted path length corresponds to a computer search tree with minimum-mean search time. A binary tree also represents a (variable-length) binary code. In an alphabetic binary code, the numerical binary order of the code words corresponds to the alphabetical order of the encoded letters. An optimal alphabetic tree corresponds to an optimal alphabetic binary code.
No takes yet. Share an insight, caveat, or question.
Hu et al. (1971) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: