{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T09:32:36Z","timestamp":1742635956545,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540535041"},{"type":"electronic","value":"9783540466772"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-53504-7_66","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:06:41Z","timestamp":1330207601000},"page":"100-109","source":"Crossref","is-referenced-by-count":3,"title":["A constant update time finger search tree"],"prefix":"10.1007","author":[{"given":"Paul","family":"Dietz","sequence":"first","affiliation":[]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"11_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"C. Aragon and R. Seidel. Randomized search trees. In Proc. 30th IEEE FOCS, pages 540\u2013545, 1989.","DOI":"10.1109\/SFCS.1989.63531"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"M. Brown and R. Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM Journal of Computing, 1980.","DOI":"10.1137\/0209045"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"P. Dietz and R. Raman. A constant update time finger search tree. Technical Report 321, University of Rochester Computer Science Department, 1989.","DOI":"10.1007\/3-540-53504-7_66"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th ACM STOC, pages 365\u2013372, 1987.","DOI":"10.1145\/28395.28434"},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J. Driscoll","year":"1989","unstructured":"J. Driscoll, N. Sarnak, D. Sleator, and R. Tarjan. Making data structures persistent. Journal of Computer and System Science, 38:86\u2013124, 1989.","journal-title":"Journal of Computer and System Science"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Science, 30:209\u2013221, 1985.","journal-title":"Journal of Computer and System Science"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"L. Guibas, E. McCreight, M. Plass, and J. Roberts. A new representation for sorted lists. In Proc. 9th ACM STOC, pages 49\u201360, 1977.","DOI":"10.1145\/800105.803395"},{"key":"11_CR9","unstructured":"D. Harel. Fast updates with a guaranteed time bound per update. Technical Report 154, University of California, Irvine, 1980."},{"key":"11_CR10","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157\u2013184, 1982.","journal-title":"Acta Informatica"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju. Localized search in sorted lists. In Proc. 13th ACM STOC, pages 62\u201369, 1981.","DOI":"10.1145\/800076.802458"},{"key":"11_CR12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C. Levcopolous","year":"1988","unstructured":"C. Levcopolous and M. H. Overmars. A balanced search tree with O(1) worst-case update time. Acta Informatica, 26:269\u2013278, 1988.","journal-title":"Acta Informatica"},{"key":"11_CR13","unstructured":"M. Overmars. A O(1) average time update scheme for balanced binary search trees. Bull. EATCS, pages 27\u201329, 1982."},{"key":"11_CR14","unstructured":"M. H. Overmars. The design of dynamic data structures, LNCS 156. Springer-Verlag, 1983."},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0019-9958(85)80034-6","volume":"67","author":"A. K. Tsakalidis","year":"1985","unstructured":"A. K. Tsakalidis. AVL-trees for localized search. Information and Control, 67:173\u2013194, 1985.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","Advances in Computing and Information \u2014 ICCI '90"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-53504-7_66.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:08:45Z","timestamp":1742591325000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-53504-7_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540535041","9783540466772"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-53504-7_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}