Contents

• Contents
• Optimal Topological Bifurcating Arborescences. Definitions, Algorithms, and History
  • Binary Trees
    • Binary Search Trees
    • Alphabetic Binary Trees
    • Optimal Binary Trees
    • Prefix-free Binary Encoding
    • Optimal Binary Trees vs. Optimal Alphabetic Binary Search Trees
  • History Overview
• Hu-Tucker Algorithm
  • Overview
  • Detailed Description
    • Phase I, Combination
    • Phase II Level Assignment
    • Phase III, Recombination
    • Correctness
• Implementation Models and Complexity Evaluation
  • Phase I
    • Fast Implementation Model
    • Fast Implementation Time Complexity Evaluation
    • Implementation Model of Combination Phase With Local Minimum Compatible Pairs.
  • Phase II
    • Implementation Model
  • Phase III
    • Implementation Model
  • Time and Space Complexity of the Hu-Tucker Algorithm
  • Building OABST
  • Mergable Heaps
    • Leftist Heaps
• The Fast Implementation Builds OABST for 2,000,000 nodes!
  • Break Even Point
  • LMCP Implementation vs. Fast Implementation Compared for Large Data Sets.
  • Time Complexity of All Phases of the Hu-Tucker Algorithm
  • Experimental Time Complexity vs. Theoretical Time Complexity
  • Example Book Encoding
    • Comparison of Different Compression Algorithms
  • Experimental Comparison of the Cost of the Huffman and the Hu-Tucker Trees
  • Conclusions
• Hu-Tucker Algorithm, Phase I, Combination
  • Fast Implementation
  • Implementation with Local Minimum Compatible Pairs
• Building OABST using the Stack Algorithm
• Leftist Heap Operations
• Bibliography