instead of using the probabilities pi and qjwe will subsequently use such frequency counts and denote them by ai number of times the search argument equals ki bj number of times the search argument lies between kj and kj+ by conventionb is the number of times that is less than and bn is the frequency of being greater than kn (see fig we will subsequently use to denote the accumulated weighted path length instead of the average path lengthp (si < < ai*hi(si < < bi* 'ithusapart from avoiding the computation of the probabilities from measured frequency countswe gain the further advantage of being able to use integers instead of fractions in our search for the optimal tree considering the fact that the number of possible configurations of nodes grows exponentially with nthe task of finding the optimum seems rather hopeless for large optimal treeshoweverhave one significant property that helps to find themall their subtrees are optimal too for instanceif the tree in fig is optimalthen the subtree with keys and is also optimal as shown this property suggests an algorithm that systematically finds larger and larger treesstarting with individual nodes as smallest possible subtrees the tree thus grows from the leaves to the rootwhich issince we are used to drawing trees upside-downthe bottom-up direction [ - the equation that is the key to this algorithm is derived as followslet be the weighted path length of treeand let pl and pr be those of the left and right subtrees of its root clearlyp is the sum of pl and prand the number of times search travels on the leg to the rootwhich is simply the total number of search trials we call the weight of the tree its average path length is then /wp pl pr (si < < ai(si < < bithese considerations show the need for denotation of the weights and the path lengths of any subtree consisting of number of adjacent keys let ij be the optimal subtree consisting of nodes with keys ki+ ki+ kj then let wij denote the weight and let pij denote the path length of ij clearly , and , these quantities are defined by the following recurrence relationswii bi wij wi, - aj bj ( < <npii wii ( < <npij wij min ki < (pi, - pkj ( < < ( < <nthe last equation follows immediately from the definitions of and of optimality since there are approximately / values pijand because its definition calls for choice among all cases such that ji <nthe minimization operation will involve approximately / operations knuth pointed out that factor can be saved by the following considerationwhich alone makes this algorithm usable for practical purposes let rij be value of which achieves the minimum for it is possible to limit the search for rij to much smaller intervali to reduce the number of the - evaluation steps the key is the observation that if we have found the root rij of the optimal subtree ijthen neither extending the tree by adding node at the rightnor shrinking the tree by removing its leftmost node ever can cause the optimal root to move to the left this is expressed by the relation ri, - <rij <ri+ , which limits the search for possible solutions for rij to the range ri, - ri+ , this results in total number of elementary steps in the order of