BIASED SEARCH TREES.

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

doi:10.1137/0214041

BIASED SEARCH TREES.

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

Research output: Contribution to journal › Article › peer-review

106 Scopus citations

Abstract

Considered is the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. The authors described two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. They also presented and analyzed efficient update algorithms for biased search trees. They listed several applications of such trees.

Original language	English (US)
Pages (from-to)	545-568
Number of pages	24
Journal	SIAM Journal on Computing
Volume	14
Issue number	3
DOIs	https://doi.org/10.1137/0214041
State	Published - 1985
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0214041

Cite this

@article{391b6f30e9654c8f86a7afac2daafd0d,

title = "BIASED SEARCH TREES.",

abstract = "Considered is the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. The authors described two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. They also presented and analyzed efficient update algorithms for biased search trees. They listed several applications of such trees.",

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

year = "1985",

doi = "10.1137/0214041",

language = "English (US)",

volume = "14",

pages = "545--568",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - BIASED SEARCH TREES.

AU - Bent, Samuel W.

AU - Sleator, Daniel D.

AU - Tarjan, Robert E.

PY - 1985

Y1 - 1985

N2 - Considered is the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. The authors described two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. They also presented and analyzed efficient update algorithms for biased search trees. They listed several applications of such trees.

AB - Considered is the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. The authors described two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. They also presented and analyzed efficient update algorithms for biased search trees. They listed several applications of such trees.

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

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

U2 - 10.1137/0214041

DO - 10.1137/0214041

M3 - Article

AN - SCOPUS:0022102465

SN - 0097-5397

VL - 14

SP - 545

EP - 568

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

BIASED SEARCH TREES.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this