Rp. Cheetham et al., ADAPTIVE STRUCTURING OF BINARY SEARCH-TREES USING CONDITIONAL ROTATIONS, IEEE transactions on knowledge and data engineering, 5(4), 1993, pp. 695-704
Citations number
20
Categorie Soggetti
Information Science & Library Science","Computer Sciences, Special Topics","Computer Applications & Cybernetics
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.