ADAPTIVE STRUCTURING OF BINARY SEARCH-TREES USING CONDITIONAL ROTATIONS

Consider a set A = {A1, A2,..., A(N)} of records, where each record is identified by a unique key. The records are accessed based on a set o f access probabilities S = [s1, s2,.., s(N)] and are to be arranged le xicographically using a Binary Search Tree (BST). If S is known a prio ri, it is well known [10] that an optimal BST may be constructed using A and S. We consider the case when S is not known a priori. A new res tructuring heuristic is introduced that requires three extra integer m emory locations per record. In this scheme the restructuring is perfor med only if it decreases the Weighted Path Length (WPL) of the overall resultant tree. An optimized version of the latter method which requi res only one extra integer field per record has also been presented. I nitial simulation results which compare our algorithm with various oth er static and dynamic schemes seem to indicate that this scheme asympt otically produces trees which are an order of magnitude closer to the optimal one than those produced by many of the other BST schemes repor ted in the literature.