key ernst key peter the results of procedure find are shown in fig and demonstrate that the structures obtained for the three cases may differ significantly the total weight is the path length of the balanced tree is and that of the optimal tree is balanced tree optimal tree albert not considering key misses albert albert ernst ernst peter ernst peter peter fig the trees generated by the optimal tree procedure it is evident from this algorithm that the effort to determine the optimal structure is of the order of alsothe amount of required storage is of the order this is unacceptable if is very large algorithms with greater efficiency are therefore highly desirable one of them is the algorithm developed by hu and tucker [ - which requires only (nstorage and ( *log( )computations howeverit considers only the case in which the key frequencies are zeroi where only the unsuccessful search trials are registered another algorithmalso requiring (nstorage elements and ( *log( )computations was described by walker and gotlieb [ - instead of trying to find the optimumthis algorithm merely promises to yield nearly optimal tree it can therefore be based on heuristic principles the basic idea is the following consider the nodes (genuine and special nodesbeing distributed on linear scaleweighted by their frequencies (or probabilitiesof access then find the node which is closest to the center of gravity this node is called the centroidand its index is (si < < *ai(si < < *biw rounded to the nearest integer if all nodes have equal weightthen the root of the desired optimal tree evidently coincides with the centroid otherwise so the reasoning goes it will in most cases be in the close neighborhood of the centroid limited search is then used to find the local optimumwhereafter this procedure is applied to the resulting two subtrees the likelihood of the root lying very close to the centroid grows with the size of the tree as soon as the subtrees have reached manageable sizetheir optimum can be determined by the above exact algorithm -trees so farwe have restricted our discussion to trees in which every node has at most two descendantsi to binary trees this is entirely satisfactory iffor instancewe wish to represent family relationships with preference to the pedigree viewin which every person is associated with his parents after allno one has more than two parents but what about someone who prefers the posterity viewhe has to cope with the fact that some people have more than two childrenand his trees will contain nodes with many branches for lack of better termwe shall call them multiway trees of coursethere is nothing special about such structuresand we have already encountered all the programming and data definition facilities to cope with such situations iffor instancean absolute upper limit on the number of children is given (which is admittedly somewhat futuristic assumption)then one may represent the children as an array component of the record representing person if the number of children varies strongly among different personshoweverthis may result in poor utilization of available storage in this case it will be much more appropriate to arrange the offspring as linear listwith pointer