Accession Number:

AD0725093

Title:

Path Length of Binary Search Trees.

Descriptive Note:

Technical summary rept.,

Corporate Author:

WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s):

• Hu,T. C.
• Tan,K. C.

Report Date:

1970-11-01

Pagination or Media Count:

32.0

Abstract:

Three new algorithms are introduced in the present paper. The first algorithm constructs a minimum cost tree with restricted maximum path length. i.e. Huffmans 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 Huffmans algorithm is a special case of the T-C algorithm. Author

Descriptors:

• (*GRAPHICS
• BINARY ARITHMETIC)
• (*SEARCH THEORY
• GRAPHICS)
• COMPUTER PROGRAMMING
• MATHEMATICAL PROGRAMMING
• CODING
• ALGORITHMS
• THEOREMS

Subject Categories:

• Theoretical Mathematics
• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE