Heuristics That Dynamically Organize Data Structures
James R. Bitner · SIAM Journal on Computing · 1979
We first consider heuristics that dynamically alter linked lists, causing more frequently accessed keys to move nearer the “top” of the list. We show that the move to front rule reduces the access time much more quickly than the transposition rule, then give a “hybrid” of these two rules which decreases the access time quickly and has low asymptotic cost. We also discuss rules that assume a counter is associated with each key. Second, we consider rules for binary search trees. The monotonic tree rule performs well only when the entropy of the probability distribution for key requests is low; otherwise, it does not reduce the access time. A final class of rules using rotations give nearly optimal performance.