Biased 2-3 trees

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

doi:10.1109/SFCS.1980.4567825

Biased 2-3 trees

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

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

1 Scopus citations

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 language	English (US)
Article number	4567825
Pages (from-to)	248-254
Number of pages	7
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/SFCS.1980.4567825
State	Published - 1980
Externally published	Yes
Event	21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States Duration: Oct 13 1980 → Oct 15 1980

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/SFCS.1980.4567825

Cite this

@article{94af94a7044d44e18f3c0b62ee2f5b85,

title = "Biased 2-3 trees",

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

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

note = "Publisher Copyright: {\textcopyright} 1980 IEEE Computer Society. All rights reserved.; 21st Annual Symposium on Foundations of Computer Science, FOCS 1980 ; Conference date: 13-10-1980 Through 15-10-1980",

year = "1980",

doi = "10.1109/SFCS.1980.4567825",

language = "English (US)",

pages = "248--254",

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

issn = "0272-5428",

}

TY - JOUR

T1 - Biased 2-3 trees

AU - Bent, Samuel W.

AU - Sleator, Daniel D.

AU - Tarjan, Robert E.

PY - 1980

Y1 - 1980

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

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

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

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

U2 - 10.1109/SFCS.1980.4567825

DO - 10.1109/SFCS.1980.4567825

M3 - Conference article

AN - SCOPUS:85068081334

SN - 0272-5428

SP - 248

EP - 254

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 4567825

T2 - 21st Annual Symposium on Foundations of Computer Science, FOCS 1980

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