Optimal worst case trees

Design and analysis of sorting and searching algorithms lead to the study of rooted trees with information stored either at the leaves or at all vertices. We consider the problem of minimising the maximum search cost when n items must be stored. Trees which achieve this minimum are almost regular and can usually be found in constant time. If regular trees are used, the maximum cost for a search is nearly best possible. If information is stored at all vertices, the root degree of large optimum trees take on one of two adjacent values, and both usually occur infinitely often for linear cost.