BIASED SEARCH TREES.

Samuel W. Bent, Daniel D. Sleator, Robert E. Tarjan

Research output: Contribution to journalArticle

93 Scopus citations

Abstract

Considered is 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. The authors described 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. They also presented and analyzed efficient update algorithms for biased search trees. They listed several applications of such trees.

Original languageEnglish (US)
Pages (from-to)545-568
Number of pages24
JournalSIAM Journal on Computing
Volume14
Issue number3
DOIs
StatePublished - Jan 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'BIASED SEARCH TREES.'. Together they form a unique fingerprint.

  • Cite this