ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Self-adjusting binary search trees
Full text pdf formatPdf (2.46 MB)
Source Journal of the ACM (JACM) archive
Volume 32 ,  Issue 3  (July 1985) table of contents
Pages: 652 - 686  
Year of Publication: 1985
ISSN:0004-5411
Authors
Daniel Dominic Sleator  AT&T Bell Laboratories, Murray Hill, NJ
Robert Endre Tarjan  AT&T Bell Laboratories, Murray Hill, NJ
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 68,   Downloads (12 Months): 552,   Citation Count: 145
Additional Information:

abstract   references   cited by   index terms   review   collaborative colleagues   peer to peer  

Tools and Actions: Review this Article  
Save this Article to a Binder    Display Formats: BibTex  EndNote ACM Ref   
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/3828.3835
What is a DOI?

ABSTRACT

The splay tree, a self-adjusting form of binary search tree, is developed and analyzed. The binary search tree is a data structure for representing tables and lists so that accessing, inserting, and deleting items is easy. On an n-node splay tree, all the standard search tree operations have an amortized time bound of O(log n) per operation, where by “amortized time” is meant the time per operation averaged over a worst-case sequence of operations. Thus splay trees are as efficient as balanced trees when total running time is the measure of interest. In addition, for sufficiently long access sequences, splay trees are as efficient, to within a constant factor, as static optimum search trees. The efficiency of splay trees comes not from an explicit structural constraint, as with balanced trees, but from applying a simple restructuring heuristic, called splaying, whenever the tree is accessed. Extensions of splaying give simplified forms of two other data structures: lexicographic or multidimensional search trees and link/cut trees.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
ABRAMSON, N.Information Theory and Coding. McGraw-Hill, New York, 1983.
 
2
ADEL'SON-VEL'SKII, G.M., AND LANDIS, E.M.An algorithm for the organization of information. Soy. Math. Dokl. 3 (1962), 1259-1262.
 
3
Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
4
Brian Allen , Ian Munro, Self-Organizing Binary Search Trees, Journal of the ACM (JACM), v.25 n.4, p.526-535, Oct. 1978  [doi>10.1145/322092.322094]
 
5
BAYER, R. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta inf i (1972), 290-306.
 
6
BAYER, R., AND MCCREIGHT, E.Organization of large ordered indexes. Acta Inf. 1 (1972), 173- l ot~ 07.
 
7
BENT, S.W., SLEATOR, D.D., AND TARJAN, R.E.Biased 2-3 trees, In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE, New v,,,.t, l oQa ,,,,,,-,o,-.,-,'~A~--'~A. ~ Ul ix, 1 .,vUV, VIJ.
 
8
BENT, S.W., SLEATOR, D.D., AND TARJAN, R.E.biased search trees.SlAM J. Comput. To be published.
 
9
BENTLEY J.L AND MCGEOGH.C WORST CASTE-PUBLICATION tics. Submitted for publication.
 
10
BITNER, J.R. Heuristics that dynamically organize data structures. SIAM J. Comput. 8 (1979), 82-110.
 
11
BROWN, M.R., AND TARJAN, R.E. Design and analysis of a data structure for representing sorted lists. SIAM J. Comput 9 (1980), 594-614.
 
12
Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
 
13
FEIGENBAUM, J., AND TARJAN, R.E.Two new kinds of biased search trees. Bell Syst. Tech. J. 62 (1983), 3139-3158.
14
Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States  [doi>10.1145/800105.803395]
 
15
Ralf Hartmut Güting , Hans-Peter Kriegel, Multidimensional B-tree: An Efficient Dynamic File Structure for Exact Match Queries, GI - 10. Jahrestagung, p.375-388, September 30-October 02, 1980
 
16
Hu, T.C., AND TUCKER, A.C.Optimal computer-search trees and variable-length alphabetic codes. SIAM J. Appl. Math. 37 (1979), 246-256.
 
17
HUDDLESTON, S. An improved bound on the performance of self-adjusting search trees. Unpub- Iished research note, Computer Science Dept., Univ. of California, Irvine, Calif., 1983.
 
18
Scott Huddleston , Kurt Mehlhorn, Robust Balancing in B-Trees, Proceedings of the 5th GI-Conference on Theoretical Computer Science, p.234-244, March 23-25, 1981
 
19
HUDDLESTON, S., AND MEHLHORN, KA new data structure for representing sorted lists. Acta Inf. 17 (1982), 157-184.
 
20
KNUTH, D.E.Optimum binary search trees. Acta Inf. 1 (1971), 14-25.
 
21
Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
 
22
Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
23
S. Rao Kosaraju, Localized search in sorted lists, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.62-69, May 11-13, 1981, Milwaukee, Wisconsin, United States  [doi>10.1145/800076.802458]
 
24
MAIER, D., AND SALVETER, S. Hysterical B-trees. Inf. Proc. Lett. 12 ( 1981 ), 199-202.
 
25
MEHLHORN, K.Dynamic binary search trees. SIAM J. Comput. 8 (1979), I75-I98.
 
26
NIEVERGELT, J., AND REINGOLD, E.MB.inary search trees of bounded balance. SIAM J. Comput. 2 (1973), 33-43.
 
27
SLEATOR, D.D.An O(nm log n) algorithm for maximum network flow. Tech. Rep. STAN-CS-80- 831. Computer Science Dept., Stanford Univ., Stanford, Calif., 1980.
28
Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.235-245, December 1983  [doi>10.1145/800061.808752]
 
29
Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983  [doi>10.1016/0022-0000(83)90006-5]
30
Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985  [doi>10.1145/2786.2793]
 
31
Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986  [doi>10.1137/0215004]
 
32
STEPHENSON, C.J.A method for constructing binary search trees by making insertions at the root. Int. J.Comput.Inf,Sci.9(1980),15-29.
33
Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975  [doi>10.1145/321879.321884]
 
34
Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
 
35
TARjAN, R.E.Amortized computational complexity. SIAM J. Appl. Discrete Meth. 6 (1985), 306-3 ! 8.
 
36
R E Tarjan, Sequential access in splay trees takes linear time, Combinatorica, v.5 n.4, p.367-378, Sept. 1985  [doi>10.1007/BF02579253]
37
Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984  [doi>10.1145/62.2160]

CITED BY  145
 
Amr Elmasry, On the sequential access theorem and deque conjecture for splay trees, Theoretical Computer Science, v.314 n.3, p.459-466, 10 April 2004
R. Chaudhuri , H. Höft, Splaying a search tree in preorder takes linear time, ACM SIGACT News, v.24 n.2, p.88-93, Spring 1993
Ranjan Chaudhuri, On preorder splaying in binary search trees(abstract and references only), Proceedings of the 19th annual conference on Computer Science, p.649, April 1991, San Antonio, Texas, United States
 
Erik D. Demaine , John Iacono , Stefan Langerman, Proximate point searching, Computational Geometry: Theory and Applications, v.28 n.1, p.29-40, May 2004
 
Martin Fürer, Randomized splay trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.903-904, January 17-19, 1999, Baltimore, Maryland, United States
Wei Jiang , Chen Ding , Roland Cheng, Memory access analysis and optimization approaches on splay trees, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-6, October 22-23, 2004, Houston, Texas
 
George F. Georgakopoulos, Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees, Journal of Algorithms, v.51 n.1, p.64-76, 1 April 2004
R. Cole, On the dynamic finger conjecture for splay trees, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.8-17, May 13-17, 1990, Baltimore, Maryland, United States
 
N. Manjikian , W. M. Loucks, Using split event sets to form and schedule event combinations in discrete event simulation, Proceedings of the 25th annual symposium on Simulation, p.184-191, April 1992, Orlando, Florida, United States
Michael J. Fischer , Michael S. Paterson, Fishspear: a priority queue algorithm, Journal of the ACM (JACM), v.41 n.1, p.3-30, Jan. 1994
Michael L. Fredman, On the efficiency of pairing heaps and related data structures, Journal of the ACM (JACM), v.46 n.4, p.473-501, July 1999
D D Sleator , R E Tarjan , W P Thurston, Rotation distance, triangulations, and hyperbolic geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.122-135, May 28-30, 1986, Berkeley, California, United States
Bradley C. Kuszmaul, A segmented parallel-prefix VLSI circuit with small delays for small segments, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
 
Xiao Zhong-e , Rob Simmonds , Brian Unger , John Cleary, Parallel and distributed simulation: fast cell level ATM network simulation, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
Chengwen Chris Wang , Jonathan Derryberry , Daniel Dominic Sleator, O(log log n)-competitive dynamic binary search trees, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.374-383, January 22-26, 2006, Miami, Florida
 
Eric Tannier , Anne Bergeron , Marie-France Sagot, Advances on sorting by reversals, Discrete Applied Mathematics, v.155 n.6-7, p.881-888, April, 2007
Ben Pfaff, Performance analysis of BSTs in system software, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
Beomjoo Seo , Roger Zimmermann, Efficient disk replacement and data migration algorithms for large disk subsystems, ACM Transactions on Storage (TOS), v.1 n.3, p.316-345, August 2005
K. Bruce Erickson , Richard E. Ladner , Anthony Lamarca, Optimizing static calendar queues, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.3, p.179-214, July 2000
D. W. Jones, Application of splay trees to data compression, Communications of the ACM, v.31 n.8, p.996-1007, Aug. 1988
 
Michael T. Goodrich, Competitive tree-structured dictionaries, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.494-495, January 09-11, 2000, San Francisco, California, United States
 
Amr Elmasry, Parameterized self-adjusting heaps, Journal of Algorithms, v.52 n.2, p.103-119, August 2004
Roger Hoover, Dynamically bypassing copy rule chains in attribute grammars, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.14-25, January 01, 1986, St. Petersburg Beach, Florida
 
Kiem-Phong Vo, Cdt: a general and efficient container data type library, Proceedings of the Annual Technical Conference on Proceedings of the USENIX 1997 Annual Technical Conference, p.12-12, January 06-10, 1997, Anaheim, California
 
Tony W. Lai , Derick Wood, Adaptive heuristics for binary search trees and constant linkage cost, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.72-77, January 28-30, 1991, San Francisco, California, United States
Mutsumi Fujihara , Kiyoshi Yoneda, Simulation through explicit state description and its application to semiconductor fab operation, Proceedings of the 24th conference on Winter simulation, p.899-907, December 13-16, 1992, Arlington, Virginia, United States
 
Susanne Albers , Marek Karpinski, Randomized splay trees: theoretical and experimental results, Information Processing Letters, v.81 n.4, p.213-221, 28 February 2002
Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, ACM SIGPLAN Notices, v.27 n.10, p.92-109, Oct. 1992
William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990
 
Cameron Kiddle , Rob Simmonds , Brian Unger, Channel based sequential simulation, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Wai Teng Tang , Rick Siow Mong Goh , Ian Li-Jin Thng, Ladder queue: An O(1) priority queue structure for large-scale discrete event simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.3, p.175-204, July 2005
 
Dinesh Ramanathan , Sandy Irani , Rajesh Gupta, Latency effects of system level power management algorithms, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
 
Avrim Blum , Shuchi Chawla , Adam Kalai, Static optimality and dynamic search-optimality in lists and trees, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-8, January 06-08, 2002, San Francisco, California
 
John J. DiLeo, FreeSML: delivering on the open-source simulation language promise, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Haim Kaplan , Eyal Molad , Robert E. Tarjan, Dynamic rectangular intersection with priorities, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Dinesh Ramanathan , Rajesh Gupta, System level online power management algorithms, Proceedings of the conference on Design, automation and test in Europe, p.606-611, March 27-30, 2000, Paris, France
 
John Iacono, Alternatives to splay trees with O(log n) worst-case access times, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.516-522, January 07-09, 2001, Washington, D.C., United States
 
Igal Galperin , Ronald L. Rivest, Scapegoat trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.165-174, January 25-27, 1993, Austin, Texas, United States
Susanne Albers, New results on web caching with request reordering, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
Yoav Zibin , Joseph (Yossi) Gil, Incremental algorithms for dispatching in dynamically typed languages, ACM SIGPLAN Notices, v.38 n.1, p.126-138, January 2003
 
Tomasz Radzik, Improving time bounds on maximum generalised flow computations by contracting the network, Theoretical Computer Science, v.312 n.1, p.75-97, 26 January 2004
 
Bruce Spencer , J. D. Horton, Efficient Algorithms to Detect and Restore Minimality, an Extension of the Regular Restriction of Resolution, Journal of Automated Reasoning, v.25 n.1, p.1-34, July 2000
Seonghun Cho , Sarataj Sahni, Weight-biased leftist trees and modified skip lists, Journal of Experimental Algorithmics (JEA), 3, p.2-es, 1998
 
Haim Kaplan , Robert E. Tarjan , Kostas Tsioutsiouliklis, Faster kinetic heaps and their use in broadcast scheduling, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.836-844, January 07-09, 2001, Washington, D.C., United States
Kim S. Lee , Huizhu Lu , D. D. Fisher, A hierarchical single-key-lock access control using the Chinese remainder theorem, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.491-496, April 1992, Kansas City, Missouri, United States
 
William R. Burley , Sandy Irani, On algorithm design for metrical task systems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.420-429, January 22-24, 1995, San Francisco, California, United States
Brian C. Dean , Zachary H. Jones, Exploring the duality between skip lists and binary search trees, Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina
 
Cheng Hian Goh , Beng Chin Ooi , D. Sim , Kian-Lee Tan, GHOST: Fine Granularity Buffering of Indexes, Proceedings of the 25th International Conference on Very Large Data Bases, p.339-350, September 07-10, 1999
 
R. Yugo Kartono Isal , Alistair Moffat , Alwin C. H. Ngai, Enhanced word-based block-sorting text compression, Australian Computer Science Communications, v.24 n.1, p.129-137, January-February 2002
 
William Evans , David Kirkpatrick, Restructuring ordered binary trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.477-486, January 09-11, 2000, San Francisco, California, United States
R. Brown, Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem, Communications of the ACM, v.31 n.10, p.1220-1227, Oct. 1988
Robert Rönngren , Rassul Ayani , Richard M. Fujimoto , Samir R. Das, Efficient implementation of event sets in Time Warp, ACM SIGSIM Simulation Digest, v.23 n.1, p.101-108, July 1993
 
Lucas Chi Kwong Hui , Charles Martel, On efficient unsuccessful search, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.217-227, September 1992, Orlando, Florida, United States
R. Sundar , R. E. Tarjan, Unique binary search tree representations and equality-testing of sets and sequences, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.18-25, May 13-17, 1990, Baltimore, Maryland, United States
 
William Evans , David Kirkpatrick, Restructuring ordered binary trees, Journal of Algorithms, v.50 n.2, p.168-193, February 2004
Tomasz Radzik, Implementation of dynamic trees with in-subtree operations, Journal of Experimental Algorithmics (JEA), 3, p.9-es, 1998
 
Tzvika Hartman , Roded Sharan, A 1.5-approximation algorithm for sorting by transpositions and transreversals, Journal of Computer and System Sciences, v.70 n.3, p.300-320, May 2005
 
Amr Elmasry, Deterministic jumplists, Nordic Journal of Computing, v.12 n.1, p.27-39, March 2005
 
Steffen Heinz , Justin Zobel, Performance of data structures for small sets of strings, Australian Computer Science Communications, v.24 n.1, p.87-94, January-February 2002
Jeffrey S. Steinman, Discrete-event simulation and the event horizon part 2: event list management, ACM SIGSIM Simulation Digest, v.26 n.1, p.170-178, July 1996
Correspondence-based data structures for double-ended priority queues, Journal of Experimental Algorithmics (JEA), 5, p.2-es, 2000
 
Robert Rönngren , Rassul Ayani, Service oriented scheduling in Time Warp, Proceedings of the 26th conference on Winter simulation, p.1340-1346, December 11-14, 1994, Orlando, Florida, United States
Jeffrey S. Vitter, An efficient I/O interface for optical disks, ACM Transactions on Database Systems (TODS), v.10 n.2, p.129-162, June 1985
Rabin A. Sugumar , Santosh G. Abraham, Efficient simulation of caches under optimal replacement with applications to miss characterization, ACM SIGMETRICS Performance Evaluation Review, v.21 n.1, p.24-35, June 1993
Richard M. Fujimoto, The virtual machine, ACM SIGARCH Computer Architecture News, v.19 n.1, p.35-44, March 1991
Girija Narlikar , Francis Zane, Performance modeling for fast IP lookups, ACM SIGMETRICS Performance Evaluation Review, v.29 n.1, p.1-12, June 2001
John Iacono , Stefan Langerman, Proximate planar point location, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
Robert Rönngren , Rassul Ayani, Adaptive checkpointing in Time Warp, ACM SIGSIM Simulation Digest, v.24 n.1, p.110-117, July 1994
R. M. Fujimoto, The virtual time machine, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.199-208, June 18-21, 1989, Santa Fe, New Mexico, United States
 
Robert E. Tarjan , Renato F. Werneck, Self-adjusting top trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
 
Dennis Grinberg , Sivaramakrishnan Rajagopalan , Ramarathnam Venkatesan , Victor K. Wei, Splay trees for data compression, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.522-530, January 22-24, 1995, San Francisco, California, United States
 
Salem Derisavi , Holger Hermanns , William H. Sanders, Optimal state-space lumping in Markov chains, Information Processing Letters, v.87 n.6, p.309-315, 30 September 2003
 
Ralf Hinze , Ross Paterson, Finger trees: a simple general-purpose data structure, Journal of Functional Programming, v.16 n.2, p.197-217, March 2006
 
Scott A. Crosby , Dan S. Wallach, Denial of service via algorithmic complexity attacks, Proceedings of the 12th conference on USENIX Security Symposium, p.3-3, August 04-08, 2003, Washington, DC
 
Jeff Bonwick , Jonathan Adams, Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.15-33, June 25-30, 2001
 
R. P. Cheetham , B. J. Oommen , D. T. H. Ng, Adaptive Structuring of Binary Search Trees Using Conditional Rotations, IEEE Transactions on Knowledge and Data Engineering, v.5 n.4, p.695-704, August 1993
Alok Aggarwal , Ashok Chandra, Virtual memory algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.173-185, May 02-04, 1988, Chicago, Illinois, United States
 
Eric J. Anderson , Kirsten Hildrum , Anna R. Karlin , April Rasala , Michael Saks, On list update and work function algorithms, Theoretical Computer Science, v.287 n.2, p.393-418, 28 September 2002
Ralf Hinze, Bootstrapping one-sided flexible arrays, ACM SIGPLAN Notices, v.37 n.9, p.2-13, September 2002
 
Greg N. Frederickson, A data structure for dynamically maintaining rooted trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.175-184, January 25-27, 1993, Austin, Texas, United States
Jeff S. Steinman, Discrete-event simulation and the event horizon, ACM SIGSIM Simulation Digest, v.24 n.1, p.39-49, July 1994
Baruch Awerbuch , Yossi Azar , Amos Fiat , Tom Leighton, Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.519-530, May 22-24, 1996, Philadelphia, Pennsylvania, United States
 
Guy E. Blelloch , Bruce M. Maggs , Shan Leung Maverick Woo, Space-efficient finger search on degree-balanced search trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
 
Lauri Malmi, A new method for updating and rebalancing tree-type main memory dictionaries, Nordic Journal of Computing, v.3 n.2, p.111-130, Summer 1996
Rodrigo G. Luque , João L. D. Comba , Carla M. D. S. Freitas, Broad-phase collision detection using semi-adjusting BSP-trees, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia
 
Amos Fiat , Haim Kaplan, Making data structures confluently persistent, Journal of Algorithms, v.48 n.1, p.16-58, August 2003
 
Robert F. Cohen , Roberto Tamassia, Dynamic expression trees and their applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.52-61, January 28-30, 1991, San Francisco, California, United States
Jop F. Sibeyn , James Abello , Ulrich Meyer, Heuristics for semi-external depth first search on directed graphs, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
 
R. Yugo Kartono Isal , Alistair Moffat, Word-based block-sorting text compression, Australian Computer Science Communications, v.23 n.1, p.92-99, January-February 2001
 
Joan M. Lucas, A direct algorithm for restricted rotation distance, Information Processing Letters, v.90 n.3, p.129-134, 16 May 2004
Jörg Keller , Thomas Rauber , Bernd Rederlechner, Conservative circuit simulation on shared-memory multiprocessors, ACM SIGSIM Simulation Digest, v.26 n.1, p.126-134, July 1996
Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986
A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States
 
Ha Yoon Song , Richard A. Meyer , Rajive Bagrodia, An empirical study of conservative scheduling, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.165-172, May 28-31, 2000, Bologna, Italy
 
Travis Gagie, Large alphabets and incompressibility, Information Processing Letters, v.99 n.6, p.246-251, 30 September 2006
 
Adam Kalai , Santosh Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, v.71 n.3, p.291-307, October 2005
Loukas Georgiadis , Robert E. Tarjan , Renato F. Werneck, Design of data structures for mergeable trees, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.394-403, January 22-26, 2006, Miami, Florida
 
Amos Fiat , Haim Kaplan, Making data structures confluently persistent, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.537-546, January 07-09, 2001, Washington, D.C., United States
Funda Ergun , S. Cenk Sahinalp , Jonathan Sharp , Rakesh Sinha, Biased dictionaries with fast insert/deletes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.483-491, July 2001, Hersonissos, Greece
 
Melissa E. O'Neill , F. Warren Burton, A new method for functional arrays, Journal of Functional Programming, v.7 n.5, p.487-513, September 1997
Amalia Duch , Conrado Martínez, Improving the performance of multidimensional search using fingers, Journal of Experimental Algorithmics (JEA), 10, 2005
Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986
 
Eljas Soisalon-Soininen , Peter Widmayer, Single and bulk updates in stratified trees: an amortized and worst-case analysis, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
Rick Siow Mong Goh , Ian Li-Jin Thng, Twol-amalgamated priority queues, Journal of Experimental Algorithmics (JEA), v.9 n.es, 2004
G. Badr , B. J. Oommen, On using conditional rotations and randomized heuristics for self-organizing ternary search tries, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
Genetha A. Gray , Tamara G. Kolda, Algorithm 856: APPSPACK 4.0: asynchronous parallel pattern search for derivative-free optimization, ACM Transactions on Mathematical Software (TOMS), v.32 n.3, p.485-507, September 2006
 
Stephan Schulz, E - a brainiac theorem prover, AI Communications, v.15 n.2,3, p.111-126, August 2002
Arne Thesen, Writing simulations from scratch: Pascal implementations, Proceedings of the 19th conference on Winter simulation, p.152-164, December 14-16, 1987, Atlanta, Georgia, United States
 
Frode B. Nilson, GMSim: a tool for compositional GSMP modeling, Proceedings of the 30th conference on Winter simulation, p.555-562, December 13-16, 1998, Washington, D.C., United States
 
Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
 
Stephan Schulz, E - a brainiac theorem prover, AI Communications, v.15 n.2, p.111-126, September 2002
 
Haim Kaplan , Elad Verbin, Sorting signed permutations by reversals, revisited, Journal of Computer and System Sciences, v.70 n.3, p.321-341, May 2005
Andrew Goldberg , Robert Tarjan, Finding minimum-cost circulations by canceling negative cycles, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.388-397, May 02-04, 1988, Chicago, Illinois, United States
 
Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
 
M. L. Fredman , D. S. Johnson , L. A. Mc Geoch , G. Ostheimer, Data structures for traveling salesmen, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.145-154, January 25-27, 1993, Austin, Texas, United States
 
Tzvika Hartman , Ron Shamir, A simpler and faster 1.5-approximation algorithm for sorting by transpositions, Information and Computation, v.204 n.2, p.275-290, February 2006
 
David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook , Moti Yung, Maintenance of a minimum spanning forest in a dynamic planar graph, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.1-11, January 22-24, 1990, San Francisco, California, United States
 
Yuguang Wu , Richard Muntz, Stack Evaluation of Arbitrary Set-Associative Multiprocessor Caches, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.930-942, September 1995
 
Willibald Doeringer , Günter Karjoth , Mehdi Nassehi, Routing on longest-matching prefixes, IEEE/ACM Transactions on Networking (TON), v.4 n.1, p.86-97, Feb. 1996
Guy E. Blelloch , Margaret Reid-Miller, Fast set operations using treaps, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.16-26, June 28-July 02, 1998, Puerto Vallarta, Mexico
Valentina Ciriani , Paolo Ferragina , Fabrizio Luccio , S. Muthukrishnan, A data structure for a sequence of string accesses in external memory, ACM Transactions on Algorithms (TALG), v.3 n.1, February 2007
Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by canceling negative cycles, Journal of the ACM (JACM), v.36 n.4, p.873-886, Oct. 1989
Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988
Stephen Alstrup , Jacob Holm , Kristian De Lichtenberg , Mikkel Thorup, Maintaining information in fully dynamic trees with top trees, ACM Transactions on Algorithms (TALG), v.1 n.2, p.243-264, October 2005
A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States
 
Alistair Moffat , R. Yugo Kartono Isal, Word-based text compression using the Burrows-Wheeler transform, Information Processing and Management: an International Journal, v.41 n.5, p.1175-1192, September 2005
Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986
Bertrand Anckaert , Mariusz Jakubowski , Ramarathnam Venkatesan, Proteus: virtualization for diversified tamper-resistance, Proceedings of the ACM workshop on Digital rights management, October 30-30, 2006, Alexandria, Virginia, USA
Matthew S. Tschantz , Michael D. Ernst, Javari: adding reference immutability to Java, ACM SIGPLAN Notices, v.40 n.10, October 2005
Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996
Robert Rönngren , Rassul Ayani, A comparative study of parallel and sequential priority queue algorithms, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.157-209, April 1997
Chen Ding , Yutao Zhong, Predicting whole-program locality through reuse distance analysis, ACM SIGPLAN Notices, v.38 n.5, May 2003
 
Ro-Yu Wu , Jou-Ming Chang , Yue-Li Wang, A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations, Theoretical Computer Science, v.355 n.3, p.303-314, 14 April 2006
 
Gerald Paul, A Complexity O(1) priority queue for event driven molecular dynamics simulations, Journal of Computational Physics, v.221 n.2, p.615-625, February, 2007
 
Michael T. Goodrich , Mark Orletsky , Kumar Ramaiyer, Methods for achieving fast query times in point location data structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.757-766, January 05-07, 1997, New Orleans, Louisiana, United States
 
G. Ciardo , R. L. Jones, III , A. S. Miner , R. I. Siminiceanu, Logic and stochastic modeling with SMART, Performance Evaluation, v.63 n.6, p.578-608, June 2006
 
Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.29-38, January 06-08, 2002, San Francisco, California
 
Christopher D. Carothers , Richard M. Fujimoto, Efficient Execution of Time Warp Programs on Heterogeneous, NOW Platforms, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.299-317, March 2000
Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Self-improving algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.261-270, January 22-26, 2006, Miami, Florida
Steffen Heinz , Justin Zobel , Hugh E. Williams, Burst tries: a fast, efficient data structure for string keys, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.192-223, April 2002
 
Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Journal of Algorithms, v.53 n.2, p.115-136, November 2004
 
G. Horn , A. Kvalbein , J. Blomskøld , E. Nilsen, An empirical comparison of generators for self similar simulated traffic, Performance Evaluation, v.64 n.2, p.162-190, February, 2007
Michael C. Loui, Strategic directions in research in theory of computing, ACM Computing Surveys (CSUR), v.28 n.4, p.575-590, Dec. 1996
Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990
Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching


General Terms:
Algorithms, Performance, Theory, Verification


REVIEW

"David W. Ballew : Reviewer"

This paper develops and analyzes the splay tree, a form of self-adjusting binary search tree. The basic problem being considered is that of carrying out a sequence of access operations on the tree; in order for the total access time t  more...

Collaborative Colleagues:
Daniel Dominic Sleator: colleagues
Robert Endre Tarjan: colleagues

Peer to Peer - Readers of this Article have also read: