Expected Costs in Some Classes of Binary Search Trees

Abstract The average path lengths, or costs, in several classes of binary seareh trees are discussed and compared. Two kinds of random trees are introduced based on a model for randomly constructed trees. In addition to them, a quasi-optimum tree, called “descending tree”, is taken for the evaluation of the cost. It is shown that a hierarchical relation in terms of the expected cost holds among those three classes, if the probabilities that each record is inserted into tree or is requested are assigned “randomly” in some sense. Also discussed is a similar relation between two types of self-organizing search trees which dynamically change their structures to reduce the cost.