TR-126: Adaptive Structuring of Binary Search Trees Using Conditional Rotations

Abstract

Consider a set= {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
i>={s1 ,s2, … , sN } and are to be arranged lexicographically using a binary search tree. If i> is known a priori, it is well known [7] that an optimal binary search tree may be constructed using and i>. We consider the case when i> is not known a priori. A new restructuring heuristic is introduced that requires three extra integer memory Iocations per record, and this restructuring of the tree is performed only if it decreases the weighted path length of. the overall resultant tree. We also present a space optimized version of the latter restructuring mechanism which requires only one extra integer field per record. We show that the cost of the tree is reduced by each restructuring operation, and present experimental results to demonstrate the superiority of our algorithm over all other efficient static and dynamic schemes that exist in the literature.