{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:25:42Z","timestamp":1742981142469,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":24,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_263","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:04:14Z","timestamp":1461269054000},"page":"1423-1426","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["O(log log n)-Competitive Binary Search Tree"],"prefix":"10.1007","author":[{"given":"Chengwen Chris","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Sleator","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"263_CR151","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00453-003-1015-8","volume":"36","author":"A Blum","year":"2003","unstructured":"Blum A, Chawla S, Kalai A (2003) Static optimality and dynamic search-optimality in lists and trees. Algorithmica 36:249\u2013260","journal-title":"Algorithmica"},{"issue":"1","key":"263_CR152","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/S009753979732699X","volume":"30","author":"R Cole","year":"2000","unstructured":"Cole R (2000) On the dynamic finger conjecture for splay trees II: the proof. SIAM J Comput 30(1):44\u201385","journal-title":"SIAM J Comput"},{"issue":"1","key":"263_CR153","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539797326988","volume":"30","author":"R Cole","year":"2000","unstructured":"Cole R, Mishra B, Schmidt J, Siegel A (2000) On the dynamic finger conjecture for splay trees I: splay sorting log\u00a0n-block sequences. SIAM J Comput 30(1):1\u201343","journal-title":"SIAM J Comput"},{"key":"263_CR154","unstructured":"Crane CA (1972) Linear lists and priority queues as balanced binary trees. Technical report STAN-CS-72-259, Computer Science Department, Stanford University"},{"issue":"1","key":"263_CR155","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(82)90083-7","volume":"15","author":"K Culik II","year":"1982","unstructured":"Culik II K, Wood D (1982) A note on some tree similarity measures. Inf Process Lett 15(1):39\u201342","journal-title":"Inf Process Lett"},{"issue":"1","key":"263_CR156","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/S0097539705447347","volume":"37","author":"ED Demaine","year":"2007","unstructured":"Demaine ED, Harmon D, Iacono J, Patrascu M (2007) Dynamic optimality-almost. SIAM J Comput 37(1):240\u2013251","journal-title":"SIAM J Comput"},{"key":"263_CR157","unstructured":"Derryberry J, Sleator DD, Wang CC (2005) A lower bound framework for binary search trees with rotations. Technical report CMU-CS-05-187, Carnegie Mellon University"},{"issue":"3","key":"263_CR158","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/j.tcs.2004.01.019","volume":"314","author":"A Elmasry","year":"2004","unstructured":"Elmasry A (2004) On the sequential access theorem and deque conjecture for splay trees. Theor Comput Sci 314(3):459\u2013466","journal-title":"Theor Comput Sci"},{"key":"263_CR159","unstructured":"Georgakopoulos GF (2005) How to splay for log\u00a0log\u00a0n-competitiveness. In: Proceedings of the 4th international workshop on experimental and efficient algorithms (WEA), Santorini Island, pp\u00a0570\u2013579"},{"issue":"1","key":"263_CR1510","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-004-1136-8","volume":"42","author":"J Iacono","year":"2005","unstructured":"Iacono J (2005) Key-independent optimality. Algorithmica 42(1):3\u201310","journal-title":"Algorithmica"},{"key":"263_CR1511","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF00264289","volume":"1","author":"DE Knuth","year":"1971","unstructured":"Knuth DE (1971) Optimum binary search trees. Acta Inf 1:14\u201325","journal-title":"Acta Inf"},{"issue":"2","key":"263_CR1512","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(89)90069-0","volume":"31","author":"F Luccio","year":"1989","unstructured":"Luccio F, Pagli L (1989) On the upper bound on the rotation distance of binary trees. Inf Process Lett 31(2):57\u201360","journal-title":"Inf Process Lett"},{"issue":"5","key":"263_CR1513","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0020-0190(88)90153-6","volume":"26","author":"E M\u00e4kinen","year":"1988","unstructured":"M\u00e4kinen E (1988) On the rotation distance of binary trees. Inf Process Lett 26(5):271\u2013272","journal-title":"Inf Process Lett"},{"issue":"3","key":"263_CR1514","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator DD, Tarjan RE (1985) Self-adjusting binary search trees. J ACM 32(3):652\u2013686","journal-title":"J ACM"},{"key":"263_CR1515","doi-asserted-by":"crossref","unstructured":"Sleator DD, Tarjan RE, Thurston WP (1986) Rotation distance, triangulations, and hyperbolic geometry. In: Proceedings 18th ACM symposium on theory of computing (STOC), Berkeley, pp\u00a0122\u2013135","DOI":"10.1145\/12130.12143"},{"key":"263_CR1516","doi-asserted-by":"crossref","unstructured":"Sundar R (1989) Twists, turns, cascades, deque conjecture, and scanning theorem. In: Proceedings 30th IEEE symposium on foundations of computer science (FOCS), pp\u00a0555\u2013559","DOI":"10.1109\/SFCS.1989.63534"},{"issue":"1","key":"263_CR1517","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01191208","volume":"12","author":"R Sundar","year":"1992","unstructured":"Sundar R (1992) On the deque conjecture for the splay algorithm. Combinatorica 12(1):95\u2013124","journal-title":"Combinatorica"},{"issue":"4","key":"263_CR1518","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF02579253","volume":"5","author":"R Tarjan","year":"1985","unstructured":"Tarjan R (1985) Sequential access in play trees takes linear time. Combinatorica 5(4):367\u2013378","journal-title":"Combinatorica"},{"key":"263_CR1519","doi-asserted-by":"crossref","unstructured":"Tarjan RE (1983) Data structures and network algorithms. In: CBMS-NSF regional conference series in applied mathematics, vol.\u00a044. SIAM, Philadelphia","DOI":"10.1137\/1.9781611970265"},{"key":"263_CR1520","unstructured":"Wang CC (2006) Multi-splay trees. Ph.D. thesis, Carnegie Mellon University"},{"key":"263_CR1521","unstructured":"Wang CC, Derryberry J, Sleator DD (2006) O(loglog\u00a0n)-competitive dynamic binary search trees. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms (SODA), Miami, pp\u00a0374\u2013383"},{"issue":"1","key":"263_CR1522","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0218004","volume":"18","author":"R Wilber","year":"1989","unstructured":"Wilber R (1989) Lower bounds for accessing binary search trees with rotations. SIAM J Comput 18(1):56\u201367","journal-title":"SIAM J Comput"},{"key":"263_CR1523","doi-asserted-by":"crossref","unstructured":"Demaine ED, Harmon D, Iacono J, Kane D, Patrascu, M (2009) The Geometry of binary search trees. In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), New York, pp\u00a0496\u2013505","DOI":"10.1137\/1.9781611973068.55"},{"key":"263_CR1524","unstructured":"Lucas J (1988) Canonical forms for competitive binary search tree algorithms. Technical report DCS-TR-250, Rutgers University"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:04:00Z","timestamp":1553097840000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_263"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_263","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}