TY - JOUR
T1 - Biased 2-3 trees
AU - Bent, Samuel W.
AU - Sleator, Daniel D.
AU - Tarjan, Robert E.
N1 - Funding Information:
Bialed 2·3 Treel* Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan Computer Science Department Stanford UniTersity * Research partially supported by National Science Foundation grant MeS 7826858 and by Office of Naval Research Contract NOOOl4-76-C-0330.
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 -