12.5: Nearly Optimal Binary Search Trees

To date, no one knows how to construct the optimal binary search tree using less time or storage in the general case of nonzero a's and b's. For this reason it is important to develop algorithms that produce good, but not necessarily optimal, solutions with less time and storage being required. Algorithms have been found that construct nearly optimal binary search trees. The weighted path lengths of such trees cannot differ by more than a constant factor from the optimal value.

12.5.1 Greedy Binary Search Trees

12.5.2 Greedy Construction

12.5.3 Implementation

12.5.4 Alphabetic Codes