On Tree-Growing Search Strategies

A search algorithm that adds a key to a sorted file can be represented by a {\it deterministic} tree whose external nodes are equally likely targets for insertion. The collection of algorithms that one uses throughout the stages of insertion sort is called a {\it search strategy}. Using the concept of ``tree-growing'' strategy, we demonstrate that most practical algorithm have a normal behavior. We present a sufficient condition for normality of tree-growing strategies. The sufficient condition specifies a relationship between the overall variance and the rate of growth in height of the sequence of trees that the search strategy ``grows''.