ab fig the search trees with nodes the weighted path lengths of trees (ato (eare computed according to their definition as ( / ( / ( / ( / ( / hencein this examplenot the perfectly balanced tree ( )but the degenerate tree (aturns out to be optimal the example of the compiler scanner immediately suggests that this problem should be viewed under slightly more general conditionwords occurring in the source text are not always keywordsas matter of facttheir being keywords is rather the exception finding that given word is not key in the search tree can be considered as an access to hypothetical "special nodeinserted between the next lower and next higher key (see fig with an associated external path length if the probability qi of search argument lying between the two keys ki and ki+ is also knownthis information may considerably change the structure of the optimal search tree hencewe generalize the problem by also considering unsuccessful searches the overall average weighted path length is now (si < < pi*hi(si < < qi* 'iwhere (si < < pi(si < < qi and wherehi is the level of the (internalnode and ' is the level of the external node the average weighted path length may be called the cost of the search treesince it represents measure for the expected amount of effort to be spent for searching the search tree that requires the minimal cost among all trees with given set of keys ki and probabilities pi and qi is called the optimal tree | | | | fig search tree with associated access frequencies for finding the optimal treethere is no need to require that the ' and ' sum up to in factthese probabilities are commonly determined by experiments in which the accesses to nodes are counted