Biased 2-3 trees

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

Research output: Contribution to journalConference article

Abstract

We describe a new data structure for maintaining collections of weighted items. The access time for an item of weight ω in a collection of total weight W is proportional to \og(W/ω) in the worst case (which is optimal in a certain sense), and several other useful operations can be made to work just as fast. The data structure is simpler than previous proposals, but the running time must be amortized over a sequence of operations to achieve the time bounds.

Original languageEnglish (US)
Article number4567825
Pages (from-to)248-254
Number of pages7
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - Jan 1 1980
Externally publishedYes
Event21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States
Duration: Oct 13 1980Oct 15 1980

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Biased 2-3 trees'. Together they form a unique fingerprint.

Cite this