Trees with exponentially growing costs

We investigate code trees and search trees with cost functions that increase exponentially with the depth in the tree. While corresponding coding theorems have been considered in connection with Rényi’s entropy since 1965, the algorithmic aspects of these constructions have not been analyzed before. We propose a generalized Huffman algorithm for the construction of optimal codes in this model and treat related questions for search trees giving bounds on the costs of optimal trees. The algorithm for search tree construction is based on a new form of dynamic programming with the quadrangle inequality.We also consider random trees. Due to the exponential cost function, optimally balanced trees turn out to have significantly lower average costs than random trees, unlike in the standard cost model.