Combining binary search trees

Erik D. Demaine; John Iacono; Stefan Langerman; Özgür Özkan

doi:10.1007/978-3-642-39206-1_33

Combining binary search trees

Erik D. Demaine, John Iacono, Stefan Langerman, Özgür Özkan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any "well-behaved" bound on the running time of the given BSTs, for any online access sequence. (A BST has a well-behaved bound with f(n) overhead if it spends at most O(f(n)) time per access and its bound satisfies a weak sense of closure under subsequences.) In particular, we obtain a BST data structure that is O(log log n) competitive, satisfies the working set bound (and thus satisfies the static finger bound and the static optimality bound), satisfies the dynamic finger bound, satisfies the unified bound with an additive O(log log n) factor, and performs each access in worst-case O(log n) time.

Original language	English (US)
Title of host publication	Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Pages	388-399
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-39206-1_33
State	Published - 2013
Event	40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia Duration: Jul 8 2013 → Jul 12 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7965 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
Country/Territory	Latvia
City	Riga
Period	7/8/13 → 7/12/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-39206-1_33

Cite this

Demaine, E. D., Iacono, J., Langerman, S., & Özkan, Ö. (2013). Combining binary search trees. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings (PART 1 ed., pp. 388-399). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7965 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-39206-1_33

Combining binary search trees. / Demaine, Erik D.; Iacono, John; Langerman, Stefan et al.
Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1. ed. 2013. p. 388-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7965 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Demaine, ED, Iacono, J, Langerman, S & Özkan, Ö 2013, Combining binary search trees. in Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7965 LNCS, pp. 388-399, 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013, Riga, Latvia, 7/8/13. https://doi.org/10.1007/978-3-642-39206-1_33

Demaine ED, Iacono J, Langerman S, Özkan Ö. Combining binary search trees. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. 2013. p. 388-399. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-39206-1_33

@inproceedings{9d8ce07b831f4f73b3fb2c07427044df,

title = "Combining binary search trees",

abstract = "We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any {"}well-behaved{"} bound on the running time of the given BSTs, for any online access sequence. (A BST has a well-behaved bound with f(n) overhead if it spends at most O(f(n)) time per access and its bound satisfies a weak sense of closure under subsequences.) In particular, we obtain a BST data structure that is O(log log n) competitive, satisfies the working set bound (and thus satisfies the static finger bound and the static optimality bound), satisfies the dynamic finger bound, satisfies the unified bound with an additive O(log log n) factor, and performs each access in worst-case O(log n) time.",

author = "Demaine, {Erik D.} and John Iacono and Stefan Langerman and {\"O}zg{\"u}r {\"O}zkan",

year = "2013",

doi = "10.1007/978-3-642-39206-1_33",

language = "English (US)",

isbn = "9783642392054",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "388--399",

booktitle = "Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings",

edition = "PART 1",

note = "40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 ; Conference date: 08-07-2013 Through 12-07-2013",

}

TY - GEN

T1 - Combining binary search trees

AU - Demaine, Erik D.

AU - Iacono, John

AU - Langerman, Stefan

AU - Özkan, Özgür

PY - 2013

Y1 - 2013

N2 - We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any "well-behaved" bound on the running time of the given BSTs, for any online access sequence. (A BST has a well-behaved bound with f(n) overhead if it spends at most O(f(n)) time per access and its bound satisfies a weak sense of closure under subsequences.) In particular, we obtain a BST data structure that is O(log log n) competitive, satisfies the working set bound (and thus satisfies the static finger bound and the static optimality bound), satisfies the dynamic finger bound, satisfies the unified bound with an additive O(log log n) factor, and performs each access in worst-case O(log n) time.

AB - We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any "well-behaved" bound on the running time of the given BSTs, for any online access sequence. (A BST has a well-behaved bound with f(n) overhead if it spends at most O(f(n)) time per access and its bound satisfies a weak sense of closure under subsequences.) In particular, we obtain a BST data structure that is O(log log n) competitive, satisfies the working set bound (and thus satisfies the static finger bound and the static optimality bound), satisfies the dynamic finger bound, satisfies the unified bound with an additive O(log log n) factor, and performs each access in worst-case O(log n) time.

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

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

U2 - 10.1007/978-3-642-39206-1_33

DO - 10.1007/978-3-642-39206-1_33

M3 - Conference contribution

AN - SCOPUS:84880317052

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 388

EP - 399

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -

Combining binary search trees

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this