BIASED 2-3 TREES.

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

doi:10.1109/sfcs.1980.15

BIASED 2-3 TREES.

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

Research output: Contribution to journal › Conference article › peer-review

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 language	English (US)
Pages (from-to)	248-254
Number of pages	7
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
DOIs	https://doi.org/10.1109/sfcs.1980.15
State	Published - 1980
Event	Annu Symp Found Comput Sci Proc 21st - Syracuse, NY, USA Duration: Oct 13 1980 → Oct 15 1980

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Access to Document

10.1109/sfcs.1980.15

Cite this

@article{9b4db54c900c4d52b33632ebb2e7cebc,

title = "BIASED 2-3 TREES.",

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.",

author = "Bent, {Samuel W.} and Sleator, {Daniel D.} and Tarjan, {Robert E.}",

year = "1980",

doi = "10.1109/sfcs.1980.15",

language = "English (US)",

pages = "248--254",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "Annu Symp Found Comput Sci Proc 21st ; Conference date: 13-10-1980 Through 15-10-1980",

}

TY - JOUR

T1 - BIASED 2-3 TREES.

AU - Bent, Samuel W.

AU - Sleator, Daniel D.

AU - Tarjan, Robert E.

PY - 1980

Y1 - 1980

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0019244405&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0019244405&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1980.15

DO - 10.1109/sfcs.1980.15

M3 - Conference article

AN - SCOPUS:0019244405

SN - 0272-5428

SP - 248

EP - 254

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Annu Symp Found Comput Sci Proc 21st

Y2 - 13 October 1980 through 15 October 1980

ER -

BIASED 2-3 TREES.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this