BIASED 2-3 TREES.

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

Research output: Contribution to journalConference article

12 Scopus citations

Abstract

A new data structure for maintaining collections of weighted items is described. The access time for an item of weight w in a collection of total weight W is proportional to log(W/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)
Pages (from-to)248-254
Number of pages7
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Jan 1 1980
EventAnnu Symp Found Comput Sci Proc 21st - Syracuse, NY, USA
Duration: Oct 13 1980Oct 15 1980

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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

  • Cite this