we are now ready to construct the optimization algorithm in detail we recall the following definitionswhich are based on optimal trees ij consisting of nodes with keys ki+ kj aithe frequency of search for ki bjthe frequency of search argument between kj and kj+ wijthe weight of ij pijthe weighted path length of ij rijthe index of the root of ij we declare the following arraysabp, ,rarray + of integer(* [ not used*array + of integerarray + + of integerassume that the weights wij have been computed from and in straightforward way now consider as the argument of the procedure opttree to be developed and consider as its resultbecause describes the tree structure completely may be considered an intermediate result starting out by considering the smallest possible subtreesnamely those consisting of no nodes at allwe proceed to larger and larger trees let us denote the width - of the subtree ij by then we can trivially determine the values pii for all trees with according to the definition of pijfor : to do [ , : [iend in the case we deal with trees consisting of single nodewhich plainly is also the root (see fig for : to - do : + [ , : [ ,jp[ ,ip[ , ] [ , : end kj|aj bj- bj wj- - wj- fig optimal search tree with single node note that denotes the left index limit and the right index limit in the considered tree ij for the cases we use repetitive statement with ranging from to nthe case spanning the entire tree , in each case the minimal path length pij and the associated root index rij are determined by simple repetitive statement with an index ranging over the interval given for rijfor : to do for : to - do : +hfind and min min ki (pi, - pkj such that ri, - + ,jp[ , :min [ , ] [ , : end end