{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:21:56Z","timestamp":1725488516068},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424239"},{"type":"electronic","value":"9783540446347"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44634-6_38","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:20:48Z","timestamp":1186726848000},"page":"414-425","source":"Crossref","is-referenced-by-count":0,"title":["Search Trees with Relaxed Balance and Near-Optimal Height"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rune E.","family":"Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"38_CR1","first-page":"263","volume":"146","author":"G. M. Adel\u2019son-Vel\u2019skii","year":"1962","unstructured":"G. M. Adel\u2019son-Vel\u2019skii and E. M. Landis. An Algorithm for the Organisation of Information. Doklady Akadamii Nauk SSSR, 146:263\u2013266, 1962. In Russian. English translation in Soviet Math. Doklady, 3:1259\u20131263, 1962.","journal-title":"Doklady Akadamii Nauk SSSR"},{"issue":"3","key":"38_CR2","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1006\/jcss.1997.1511","volume":"55","author":"J. Boyar","year":"1997","unstructured":"Joan Boyar, Rolf Fagerberg, and Kim S. Larsen. Amortization Results for Chromatic Search Trees, with an Application to Priority Queues. Journal of Computer and System Sciences, 55(3):504\u2013521, 1997.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"38_CR3","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1016\/S0022-0000(05)80075-3","volume":"49","author":"J. F. Boyar","year":"1994","unstructured":"Joan F. Boyar and Kim S. Larsen. Efficient Rebalancing of Chromatic Search Trees. Journal of Computer and System Sciences, 49(3):667\u2013682, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Leo J. Guibas and Robert Sedgewick. A Dichromatic Framework for Balanced Trees. In Proceedings of the 19th Annual IEEE Symposium on the Foundations of Computer Science, pages 8\u201321, 1978.","DOI":"10.1109\/SFCS.1978.3"},{"issue":"10","key":"38_CR5","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s002360050145","volume":"35","author":"K. S. Larsen","year":"1998","unstructured":"Kim S. Larsen. Amortized Constant Relaxed Rebalancing using Standard Rotations. Acta Informatica, 35(10):859\u2013874, 1998.","journal-title":"Acta Informatica"},{"issue":"3","key":"38_CR6","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1006\/jcss.2000.1705","volume":"61","author":"K. S. Larsen","year":"2000","unstructured":"Kim S. Larsen. AVL Trees with Relaxed Balance. Journal of Computer and System Sciences, 61(3):508\u2013522, 2000.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"38_CR7","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(76)90094-6","volume":"5","author":"H. A. Maurer","year":"1976","unstructured":"H. A. Maurer, Th. Ottmann, and H.-W. Six. Implementing Dictionaries using Binary Trees of Very Small Height. Information Processing Letters, 5(1):11\u201314, 1976.","journal-title":"Information Processing Letters"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Otto Nurmi and Eljas Soisalon-Soininen. Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees. In Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 192\u2013198, 1991.","DOI":"10.1145\/113413.113430"},{"issue":"6","key":"38_CR9","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/s002360050057","volume":"33","author":"O. Nurmi","year":"1996","unstructured":"Otto Nurmi and Eljas Soisalon-Soininen. Chromatic Binary Search Trees\u2014A Structure for Concurrent Rebalancing. Acta Informatica, 33(6):547\u2013557, 1996.","journal-title":"Acta Informatica"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/00207169608804523","volume":"62","author":"O. Nurmi","year":"1996","unstructured":"Otto Nurmi, Eljas Soisalon-Soininen, and Derick Wood. Relaxed AVL Trees, Main-Memory Databases and Concurrency. International Journal of Computer Mathematics, 62:23\u201344, 1996.","journal-title":"International Journal of Computer Mathematics"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"Neil Sarnak and Robert E. Tarjan. Planar Point Location Using Persistent Search Trees. Communications of the ACM, 29:669\u2013679, 1986.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44634-6_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T02:16:49Z","timestamp":1550715409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44634-6_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424239","9783540446347"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-44634-6_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}