else (*delete ^* :pif right nil then : lefth :true elsif left nil then : righth :true else del( lefth)if then balancel(phend end end end delete fortunatelydeletion of an element in balanced tree can also be performed with -in the worst case - (log noperations an essential difference between the behaviour of the insertion and deletion procedures must not be overlookedhowever whereas insertion of single key may result in at most one rotation (of two or three nodes)deletion may require rotation at every node along the search path considerfor instancedeletion of the rightmost node of fibonacci-tree in this case the deletion of any single node leads to reduction of the height of the treein additiondeletion of its rightmost node requires the maximum number of rotations this therefore represents the worst choice of node in the worst case of balanced treea rather unlucky combination of chances how probable are rotationsthenin generalthe surprising result of empirical tests is that whereas one rotation is invoked for approximately every two insertionsone is required for every five deletions only deletion in balanced trees is therefore about as easy -or as complicated -as insertion optimal search trees so far our consideration of organizing search trees has been based on the assumption that the frequency of access is equal for all nodesthat isthat all keys are equally probable to occur as search argument this is probably the best assumption if one has no idea of access distribution howeverthere are cases (they are the exception rather than the rulein which information about the probabilities of access to individual keys is available these cases usually have the characteristic that the keys always remain the samei the search tree is subjected neither to insertion nor deletionbut retains constant structure typical example is the scanner of compiler which determines for each word (identifierwhether or not it is keyword (reserved wordstatistical measurements over hundreds of compiled programs may in this case yield accurate information on the relative frequencies of occurrenceand thereby of accessof individual keys assume that in search tree the probability with which node is accessed is pr { kipi(si < < pi we now wish to organize the search tree in way that the total number of search steps counted over sufficiently many trials becomes minimal for this purpose the definition of path length is modified by ( attributing certain weight to each node and by ( assuming the root to be at level (instead of )because it accounts for the first comparison along the search path nodes that are frequently accessed become heavy nodesthose that are rarely visited become light nodes the (internalweighted path length is then the sum of all paths from the root to each node weighted by that node' probability of access si < < pi hi hi is the level of node the goal is now to minimize the weighted path length for given probability distribution as an exampleconsider the set of keys with probabilities of access / / / these three keys can be arranged in five different ways as search trees (see fig