Article

O(log log n)-competitive dynamic binary search trees

Authors:

Chengwen Chris Wang,

Jonathan Derryberry,

Daniel Dominic SleatorAuthors Info & Claims

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

Pages 374 - 383

Published: 22 January 2006 Publication History

Get Access

Abstract

The Dynamic Optimality Conjecture [ST85] states that splay trees are competitive (within a constant competitive factor) among the class of all binary search tree (BST) algorithms. Despite 20 years of research this conjecture is still unresolved. Recently, Demaine et al. [DHIP04] suggested searching for alternative algorithms which have small but non-constant competitive factors. They proposed Tango, a BST algorithm which is nearly dynamically optimal - its competitive ratio is O(log log n) instead of a constant. Unfortunately, for many access patterns, such as random and sequential, Tango is worse than other BST algorithms by a factor of log log n.In this paper, we introduce the multi-splay tree (MST) data structure, which is the first O(log log n)-competitive BST to simultaneously achieve O(log n) amortized cost and O(log² n) worst-case cost per query. We also prove the sequential access lemma for MSTs, which states that sequentially accessing all keys takes linear time. Thus, MSTs are O(log log n)-competitive like Tango but, unlike Tango, require only O(log n) amortized time per access in an arbitrary sequence and only O(1) amortized time per access during a sequential access sequence.Furthermore, we generalize the standard framework for competitive analysis of BST algorithms to include updates (insertions and deletions) in addition to queries. In doing so, we extend the lower bound of Wilber [Wil89] and Demaine et al. [DHIP04] to handle these update operations. We show how MSTs can be modified to support these update operations and be O(log log n)-competitive in the new framework while maintaining the rest of the properties above.

References

[1]

{BCK02} Avrim Blum, Shuchi Chawla, and Adam Kalai. Static optimality and dynamic search-optimality in lists and trees. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1--8, 2002.

Digital Library

Google Scholar

[2]

{CMSS00} Richard Cole, Bud Mishra, Jeanette Schmidt, and Alan Siegel. On the dynamic finger conjecture for splay trees. Part I: Splay Sorting log n-Block Sequences. Siam J. Comput., 30:1--43, 2000.

Digital Library

Google Scholar

[3]

{Col00} Richard Cole. On the dynamic finger conjecture for splay trees. Part II: The Proof. Siam J. Comput., 30:44--85, 2000.

Digital Library

Google Scholar

[4]

{CW82} K. Culik, II and D. Wood. A note on some tree similarity measures. Inform. Process. Lett., pages 39--42, 1982.

Google Scholar

[5]

{DHIP04} Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu. Dynamic Optimality-Almost. FOCS, 2004.

Google Scholar

[6]

{Elm04} Amr Elmasry. On the sequential access theorem and deque conjecture for splay trees. Theoretical Computer Science, 314:459--466, 2004.

Digital Library

Google Scholar

[7]

{GS78} L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pages 8--12, 1978.

Google Scholar

[8]

{ST85} Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652--686, July 1985.

Digital Library

Google Scholar

[9]

{STT86} D. D. Sleator, R. E. Tarjan, and W. P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. Proc. 18th Annual ACM Symposium on Theory of Computing, pages 122--135, 1986.

Digital Library

Google Scholar

[10]

{Sun89} R. Sundar. Twists, turns, cascades, deque conjecture, and scanning theorem. Proceedings of the 13th Symposium on Foundations of Computer Science, pages 555--559, 1989.

Google Scholar

[11]

{Sun92} R. Sundar. On the deque conjecture for the splay algorithm. Combinatorica, 12:95--124, 1992.

Google Scholar

[12]

{Tar83} Robert Endre Tarjan. Data structures and network algorithms. Society for Industrial and Applied Mathematics, 1983.

Digital Library

Google Scholar

[13]

{Tar85} R. Tarjan. Sequential access in splay trees takes linear time. Combinatorica, 5:367--378, 1985.

Digital Library

Google Scholar

[14]

{Wil89} Robert Wilber. Lower bounds for accessing binary search trees with rotations. SIAM Journal on Computing, 18(1):56--67, 1989.

Digital Library

Google Scholar

Cited By

View all

Kozma LSaranurak TDiakonikolas IKempe DHenzinger M(2018)Smooth heaps and a dual view of self-adjusting data structuresProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188864(801-814)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188864
Fray KMorgan KWirth AZobel J(2017)Practical adaptive search trees with performance boundsProceedings of the Australasian Computer Science Week Multiconference10.1145/3014812.3014836(1-8)Online publication date: 30-Jan-2017
https://dl.acm.org/doi/10.1145/3014812.3014836
Schmid SAvin CScheideler CBorokhovich MHaeupler BLotker Z(2016)SplayNetIEEE/ACM Transactions on Networking10.1109/TNET.2015.241031324:3(1421-1433)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2410313
Show More Cited By

Index Terms

O(log log n)-competitive dynamic binary search trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
      2. Trees
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Fully dynamic connectivity in O(log n(log log n)²) amortized expected time
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O(log n(log log n)²) amortized expected update time and O(log n/log log log n) query time, which ...
An O(log n log log n) space algorithm for undirected st-connectivity
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

We present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam [6] and uses the universal exploration sequences for trees constructed by Koucký [13]. Our ...
Efficient maintenance of binary search trees

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

January 2006

1261 pages

ISBN:0898716055

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
917
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kozma LSaranurak TDiakonikolas IKempe DHenzinger M(2018)Smooth heaps and a dual view of self-adjusting data structuresProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188864(801-814)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188864
Fray KMorgan KWirth AZobel J(2017)Practical adaptive search trees with performance boundsProceedings of the Australasian Computer Science Week Multiconference10.1145/3014812.3014836(1-8)Online publication date: 30-Jan-2017
https://dl.acm.org/doi/10.1145/3014812.3014836
Schmid SAvin CScheideler CBorokhovich MHaeupler BLotker Z(2016)SplayNetIEEE/ACM Transactions on Networking10.1109/TNET.2015.241031324:3(1421-1433)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2410313
Park EMount D(2012)A self-adjusting data structure for multidimensional point setsProceedings of the 20th Annual European conference on Algorithms10.1007/978-3-642-33090-2_67(778-789)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33090-2_67
Bose PCollette SFagerberg RLangerman S(2012)De-amortizing binary search treesProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part I10.1007/978-3-642-31594-7_11(121-132)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31594-7_11
Fox K(2011)Upper bounds for maximally greedy binary search treesProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033225(411-422)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033225
Bose PDouïeb KDujmović VFagerberg R(2010)An O(log log n)-competitive binary search tree with optimal worst-case access timesProceedings of the 12th Scandinavian conference on Algorithm Theory10.1007/978-3-642-13731-0_5(38-49)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13731-0_5
Demaine EHarmon DIacono JKane DPătraşcu MMathieu C(2009)The geometry of binary search treesProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496825(496-505)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496825
Pettie STeng S(2008)Splay trees, Davenport-Schinzel sequences, and the deque conjectureProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347204(1115-1124)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347204
Bose PDouïeb KLangerman STeng S(2008)Dynamic optimality for skip lists and B-treesProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347203(1106-1114)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347203
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fully dynamic connectivity in O(log n(log log n)²) amortized expected time

An O(log n log log n) space algorithm for undirected st-connectivity

Efficient maintenance of binary search trees