Dynamic deferred data structuring

Yu-Tai Ching; Kurt Mehlhorn; Michiel H.M. Smid

doi:10.1016/0020-0190(90)90171-S

Dynamic deferred data structuring

Yu-Tai Ching^*, Kurt Mehlhorn, Michiel H.M. Smid

^*Corresponding author for this work

Institute of Data Science and Engineering

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

6 Scopus citations

Abstract

Let S be a set of n reals. We show how to process on-line a sequence of r membership queries, insertions and deletions in time O(r log(n + r) + (n + r) log r). This is optimal in the binary comparison model.

Original language	English
Pages (from-to)	37-40
Number of pages	4
Journal	Information Processing Letters
Volume	35
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(90)90171-S
State	Published - 15 Jun 1990

Keywords

Data structure
deferred data structure
dictionary problem
on-line
weight-balanced trees

Access to Document

10.1016/0020-0190(90)90171-S

Cite this

@article{06a5c246441347f685d84c64e5f8c1a0,

title = "Dynamic deferred data structuring",

abstract = "Let S be a set of n reals. We show how to process on-line a sequence of r membership queries, insertions and deletions in time O(r log(n + r) + (n + r) log r). This is optimal in the binary comparison model.",

keywords = "Data structure, deferred data structure, dictionary problem, on-line, weight-balanced trees",

author = "Yu-Tai Ching and Kurt Mehlhorn and Smid, {Michiel H.M.}",

year = "1990",

month = jun,

day = "15",

doi = "10.1016/0020-0190(90)90171-S",

language = "English",

volume = "35",

pages = "37--40",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Dynamic deferred data structuring

AU - Ching, Yu-Tai

AU - Mehlhorn, Kurt

AU - Smid, Michiel H.M.

PY - 1990/6/15

Y1 - 1990/6/15

N2 - Let S be a set of n reals. We show how to process on-line a sequence of r membership queries, insertions and deletions in time O(r log(n + r) + (n + r) log r). This is optimal in the binary comparison model.

AB - Let S be a set of n reals. We show how to process on-line a sequence of r membership queries, insertions and deletions in time O(r log(n + r) + (n + r) log r). This is optimal in the binary comparison model.

KW - Data structure

KW - deferred data structure

KW - dictionary problem

KW - on-line

KW - weight-balanced trees

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

U2 - 10.1016/0020-0190(90)90171-S

DO - 10.1016/0020-0190(90)90171-S

M3 - Article

AN - SCOPUS:0025447231

SN - 0020-0190

VL - 35

SP - 37

EP - 40

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Dynamic deferred data structuring

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this