On optimal trees

The merits of different shapes of trees as data storage structures are compared. Given a tree data structure, the worst-case cost of searching the tree is studied, under weak assumptions about the cost of searches. In particular, it is assumed that the cost of a search path is the sum of the costs of the nodes on it, and that the cost of a node depends only on the outdegree of that node. The main results of the paper are that there are regular trees (as defined in the paper) which are nearly optimal among trees with a given number of nodes, and that minimal-cost trees are often nearly regular.