A New Algorithm for Minimum Cost Binary Trees

作者： Adriano M. Garsia , Michelle L. Wachs

DOI: 10.1137/0206045

关键词: Discrete mathematics 、 Weight-balanced tree 、 Ternary search tree 、 Algorithm 、 Time complexity 、 Suurballe's algorithm 、 Random binary tree 、 Reverse-delete algorithm 、 Geometry of binary search trees 、 Mathematics 、 Binary search tree

摘要: A new algorithm for constructing minimum cost binary trees in $O(n \log n)$ time is presented. The similar to the well-known Hu-Tucker algorithm. Our proof of validity based on finite variational methods and therefore quite different somewhat simpler than also yields some additional information about structure trees. This permits a linear implementation our special case.