Consider a set A = {A1, A2,…, An) of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities S = [S1, S2, …, Sn] and are to be arranged lexicographically using a Binary Search Tree (BST). If S is known a priori, 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 restructuring heuristic is introduced that requires three extra integer memory locations per record. In this scheme the restructuring is performed only if it decreases the Weighted Path Length (WPL) of the overall resultant tree. An optimized version of the latter method which requires only one extra integer field per record has also been presented. Initial simulation results which compare our algorithm with various other static and dynamic schemes seem to indicate that this scheme asymptotically produces trees which are an order of magnitude closer to the optimal one than those produced by many of the other BST schemes reported in the literature.

Additional Metadata
Keywords Adaptive data structures, binary search trees, dynamic data structures, move-to-root heuristic, self organizing structures, splay trees
Persistent URL
Journal IEEE Transactions on Knowledge and Data Engineering
Cheetham, R.P. (Robert P.), Oommen, J, & Ng, D.T.H. (David T.H.). (1993). Adaptive Structuring of Binary Search Trees Using Conditional Rotations. IEEE Transactions on Knowledge and Data Engineering, 5(4), 695–704. doi:10.1109/69.234780