We study the problem of evaluating a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. Reading the value of a variable is done at the expense of some cost, and the goal is to design a strategy (decision tree) for evaluating the function incurring as little cost as possible in the worst case or in expectation (according to a prior distribution on the possible variables assignments). Except for particular cases of the problem, in general, only the minimization of one of these two measures is addressed in the literature. However, there are instances of the problem for which the minimization of one measure leads to a strategy with a high cost with respect to the other measure (even exponentially bigger than the optimal). We provide a new construction which can guarantee a trade-off between the two criteria. More precisely, given a decision tree guaranteeing expected cost @math and a decision tree guaranteeing worst cost @math our method can guarantee for any chosen trade-off value @math to produce a decision tree whose worst cost is @math and whose expected cost is @math These bounds are improved for the relevant case of uniform testing costs. Motivated by applications, we also study a variant of the problem where the cost of reading a variable depends on the variable's value. We provide an @math approximation algorithm for the minimization of the worst cost measure, which is best possible under the assumption @math .
An algorithm that constructs an optimal height-restricted binary tree for a set of n weights in @math time, where L is the maximum permitted height, is presented. This is an improvement over the fastest previously known algorithm, which requires @math time. The algorithm is a hybrid, combining a technique by Hu and Tan with a technique by Michael Garey. An algorithm is given for constructing a binary tree of minimum weighted path length for n nonnegative weights under the constraint that no path length exceed a given bound L. The number of operations required is proportional to @math . Such problems, which impose an additional constraint on the usual Huffman tree, arise in many applications, including computer file searching and the construction of optimal prefix codes under certain practical conditions. 