Editing Splay tree (section)

== References ==

*{{cite journal 
|last1=Afek 
|first1=Yehuda 
|last2=Kaplan 
|first2=Haim 
|last3=Korenfeld 
|first3=Boris 
|last4=Morrison 
|first4=Adam 
|last5=Tarjan 
|first5=Robert E. 
|title=The CB tree: a practical concurrent self-adjusting search tree 
|journal=Distributed Computing 
|date=2014 
|volume=27 
|issue=6 
|pages=393–417 
|doi=10.1007/s00446-014-0229-0 
|url=http://arks.princeton.edu/ark:/88435/pr14z66
}}
*{{cite journal
 | first1 = Susanne
 | last1 = Albers
 | first2 = Marek
 | last2 = Karpinski
 | title = Randomized Splay Trees: Theoretical and Experimental Results
 | journal = [[Information Processing Letters]]
 | volume = 81
 | issue = 4
 | pages = 213–221
 | date = 28 February 2002
 | url = http://www14.in.tum.de/personen/albers/papers/ipl02.pdf
 | doi=10.1016/s0020-0190(01)00230-7
}}
*{{cite journal
 | first1 = Brian
 | last1 = Allen
 | first2 = Ian
 | last2 = Munro
 | title = Self-organizing binary search trees
 | journal = [[Journal of the ACM]]
 | volume = 25
 | pages = 526–535
 | date = October 1978
 | issue = 4
 | doi = 10.1145/322092.322094
 | s2cid = 15967344
| doi-access = free
 }}
*{{cite journal
 | last1 = Brinkmann | first1 = Gunnar
 | last2 = Degraer | first2 = Jan
 | last3 = De Loof | first3 = Karel
 | title = Rehabilitation of an unloved child: semi-splaying
 | journal = Software: Practice and Experience
 | volume = 39 | issue = 1 | pages = 33–45
 | date = January 2009
 | doi = 10.1002/spe.v39:1
 | hdl = 11382/102133
 | citeseerx = 10.1.1.84.790
 | url = http://caagt.ugent.be/preprints/splay_spe.pdf
 | quote = The results show that semi-splaying, which was introduced in the same paper as splaying, performs better than splaying under almost all possible conditions. This makes semi-splaying a good alternative for all applications where normally splaying would be applied. The reason why splaying became so prominent while semi-splaying is relatively unknown and much less studied is hard to understand.
}}
*{{cite journal
 | first1 = Richard
 | last1 = Cole
 | first2 = Bud
 | last2 = Mishra
 | first3 = Jeanette
 | last3 = Schmidt
 | first4 = Alan
 | last4 = Siegel
 | title = On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
 | journal = [[SIAM Journal on Computing]]
 | volume = 30 | issue = 1
 | pages = 1–43
 | date = January 2000
 | doi = 10.1137/s0097539797326988
| citeseerx = 10.1.1.36.4558
 }}
*{{cite journal
 | first = Richard
 | last = Cole
 | title = On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
 | journal = [[SIAM Journal on Computing]]
 | volume = 30 | issue = 1
 | pages = 44–85
 | date = January 2000
 | doi = 10.1137/S009753979732699X
| citeseerx = 10.1.1.36.2713
 }}
*{{cite journal
 | first = Amr
 | last = Elmasry
 | title = On the sequential access theorem and Deque conjecture for splay trees
 | journal = Theoretical Computer Science
 | volume = 314
 | issue = 3
 | pages = 459–466
 | date = April 2004
 | doi = 10.1016/j.tcs.2004.01.019
 | url = https://www.researchgate.net/publication/220150614
| doi-access = 
 }}
*{{cite book
 | first1 = Michael
 | last1 = Goodrich
 | first2 = Roberto
 | last2 = Tamassia
 | first3 = Michael
 | last3 = Goldwasser
 | title = Data Structures and Algorithms in Java
 | publisher = Wiley
 | page = 506
 | edition = 6
 | year = 2014
 | isbn = 978-1-118-77133-4
 | language = en
}}
*{{cite conference
 | last1 = Grinberg | first1 = Dennis
 | last2 = Rajagopalan | first2 = Sivaramakrishnan
 | last3 = Venkatesan | first3 = Ramarathnam
 | last4 = Wei | first4 = Victor K.
 | editor-last = Clarkson | editor-first = Kenneth L.
 | contribution = Splay trees for data compression
 | contribution-url = https://dl.acm.org/citation.cfm?id=313651.313812
 | quote = Average depth of access in a splay tree is proportional to the entropy.
 | pages = 522–530
 | publisher = ACM/SIAM
 | title = Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22–24 January 1995. San Francisco, California, USA
 | year = 1995}}
*{{cite book
 | first = Donald
 | last = Knuth
 | author-link = Donald Knuth
 | title = [[The Art of Computer Programming]]
 | volume = 3: Sorting and Searching
 | edition = 3rd
 | publisher = Addison-Wesley
 | year = 1997
 | isbn = 0-201-89685-0
 | page = 478  <!-- section 6.2.3 -->
 | quote = The time needed to access data in a splay tree is known to be at most a small constant multiple of the access time of a statically optimum tree, when amortized over any series of operations.
}}
*{{cite book
 | first = Joan M.
 | last = Lucas
 | contribution = On the Competitiveness of Splay Trees: Relations to the Union-Find Problem
 | title = On-line Algorithms: Proceedings of a DIMACS Workshop, February 11–13, 1991
 | publisher = [[DIMACS|Center for Discrete Mathematics and Theoretical Computer Science]]
 | series = Series in Discrete Mathematics and Theoretical Computer Science
 | volume = 7
 | pages = 95–124
 | date = 1991
 | isbn = 0-8218-7111-0
}}
*{{cite conference
 | first = Seth
 | last = Pettie
 | title = Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
 | journal = Proc. 19th ACM-SIAM Symposium on Discrete Algorithms
 | pages = 1115–1124
 | year = 2008
 | bibcode = 2007arXiv0707.2160P
 | volume = 0707
 | arxiv = 0707.2160
 | url = http://web.eecs.umich.edu/~pettie/papers/Deque.pdf
}}
*{{cite journal
 | first1 = Daniel D.
 | last1 = Sleator
 | author1-link = Daniel Sleator
 | first2 = Robert E.
 | last2 = Tarjan
 | author2-link = Robert Tarjan
 | title = Self-Adjusting Binary Search Trees
 | journal = [[Journal of the ACM]]
 | volume = 32
 | issue = 3
 | pages = 652–686
 | year = 1985
 | url = https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
 | doi = 10.1145/3828.3835
 | s2cid = 1165848
}}
*{{cite journal
 | first = Rajamani
 | last = Sundar
 | title = On the Deque conjecture for the splay algorithm
 | journal = Combinatorica
 | volume = 12
 | pages = 95–124
 | year = 1992
 | issue = 1
 | doi = 10.1007/BF01191208
 | s2cid = 27422556
}}
*{{cite journal
 | first = Robert E.
 | last = Tarjan
 | author-link = Robert Tarjan
 | title = Sequential access in splay trees takes linear time
 | journal = Combinatorica
 | volume = 5
 | issue = 4
 | pages = 367–378
 | year = 1985
 | doi = 10.1007/BF02579253
 | s2cid = 34757821
}}
*{{cite journal
 |first1= Michael A.
 |last1 = Bender
 |first2 = Alex
 |last2 = Conway
 |first3 = Martin
 |last3 = Farach-Colton
 |first4 = William
 |last4 = Kuszmaul
 |first5 = Guido
 |last5 = Tagliavini
 |title = Tiny Pointers
 |journal = Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
 |pages=477–508
 |isbn=978-1-61197-755-4
 |year = 2023|doi = 10.1137/1.9781611977554.ch21
 |s2cid = 244709005
 }}