{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:19:18Z","timestamp":1725664758217},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_151","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:37:25Z","timestamp":1330292245000},"page":"428-439","source":"Crossref","is-referenced-by-count":1,"title":["Binary search trees: How low can you go?"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"37_CR1","first-page":"263","volume":"146","author":"G. M. Adel'son-Vel'skii","year":"1962","unstructured":"G. M. Adel'son-Vel'skii and E. M. Landis. An Algorithm for the Organisation of Information. Dokl. Akad. Nauk SSSR, 146:263\u2013266, 1962. In Russian. English translation in Soviet Math. Dokl., 3:1259\u20131263, 1962.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"A. Andersson. Optimal bounds on the dictionary problem. In Proc. Symp. on Optimal Algorithms, Varna, volume 401 of LNCS, pages 106\u2013114. Springer-Verlag, 1989.","DOI":"10.1007\/3-540-51859-2_10"},{"key":"37_CR3","volume-title":"PhD thesis","author":"A. Andersson","year":"1990","unstructured":"A. Andersson. Efficient Search Trees. PhD thesis, Department of Computer Science, Lund University, Sweden, 1990."},{"key":"37_CR4","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF01237235","volume":"28","author":"A. Andersson","year":"1990","unstructured":"A. Andersson, C. Icking, R. Klein, and T. Ottmann. Binary search trees of almost optimal height. Acta Informatica, 28:165\u2013178, 1990.","journal-title":"Acta Informatica"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"A. Andersson and T. W. Lai. Fast updating of well-balanced trees. In SWAT'90, volume 447 of LNCS, pages 111\u2013121. Springer-Verlag, 1990.","DOI":"10.1007\/3-540-52846-6_82"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"A. Andersson and T. W. Lai. Comparison-efficient and write-optimal searching and sorting. In ISA'91, volume 557 of LNCS, pages 273\u2013282. Springer-Verlag, 1991.","DOI":"10.1007\/3-540-54945-5_71"},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"P. F. Dietz and R. Raman. A constant update time finger search tree. Information Processing Letters, 52, 1994.","DOI":"10.1016\/0020-0190(94)00115-4"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"P. F. Dietz, J. I. Seiferas, and J. Zhang. A tight lower bound for on-line monotonie list labeling. In SWAT'94, volume 824 of LNCS, pages 131\u2013142. Springer-Verlag, 1994.","DOI":"10.1007\/3-540-58218-5_12"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"P. F. Dietz and D. D. Sleator. Two algorithms for maintaining order in a list. In 19th STOC, pages 365\u2013372, 1987.","DOI":"10.1145\/28395.28434"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"P. F. Dietz and J. Zhang. Lower bounds for monotonic list labeling. In SWAT'90, volume 447 of LNCS, pages 173\u2013180. Springer-Verlag, 1990.","DOI":"10.1007\/3-540-52846-6_87"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"R. Fleischer. A simple balanced search tree with O(1) worst-case update time. In ISSAC'93, volume 762 of LNCS, pages 139\u2013146. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-57568-5_243"},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"L. J. Guibas and R. Sedgewick. A Dichromatic Framework for Balanced Trees. In 19th FOCS, pages 8\u201321, 1978.","DOI":"10.1109\/SFCS.1978.3"},{"key":"37_CR13","volume-title":"PhD thesis","author":"T. Lai","year":"1990","unstructured":"T. Lai. Efficient Maintenance of Binary Search Trees. PhD thesis, Department of Computer Science, University of Waterloo, Canada, 1990."},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"T. Lai and D. Wood. Updating almost complete trees or one level makes all the difference. In STACS'90, volume 415 of LNCS, pages 188\u2013194. Springer-Verlag, 1990.","DOI":"10.1007\/3-540-52282-4_42"},{"issue":"3","key":"37_CR15","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C. Levcopoulos","year":"1988","unstructured":"C. Levcopoulos and M. H. Overmars. A balanced search tree with O(1) worst-case update time. Acta Informatica, 26(3):269, 1988.","journal-title":"Acta Informatica"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"H. A. Maurer, T. Ottmann, and H.-W. Six. Implementing dictionaries using binary trees of very small height. Information Processing Letters, 5, 1976.","DOI":"10.1016\/0020-0190(76)90094-6"},{"key":"37_CR17","volume-title":"The Design of Dynamic Data Structures","author":"M. H. Overmars","year":"1983","unstructured":"M. H. Overmars. The Design of Dynamic Data Structures. Springer, Berlin, 1983."},{"key":"37_CR18","volume-title":"PhD thesis","author":"J. Zhang","year":"1993","unstructured":"J. Zhang. Density Control and On-Line Labeling Problems. PhD thesis, Department of Computer Science, University of Rochester, New York, 1993."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_151.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:06:07Z","timestamp":1605647167000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_151","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}