Biased Search Trees

Authors:
  • SBSamuel W. Bent
    Samuel W. Bent
  • DSDaniel D. Sleator
    Daniel D. Sleator
  • RTRobert E. Tarjan
    Robert E. Tarjan

Abstract
We consider the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. We describe two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. We present and analyze efficient update algorithms for biased search trees. We list several applications of such trees.

This publication has 23 references indexed in Scilit: