{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:25:25Z","timestamp":1725488725546},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540668367"},{"type":"electronic","value":"9783540466918"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46691-6_6","type":"book-chapter","created":{"date-parts":[[2007,8,9]],"date-time":"2007-08-09T20:42:24Z","timestamp":1186692144000},"page":"72-83","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Rebalancing a Binary Search Tree"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,6,9]]},"reference":[{"key":"6_CR1","first-page":"263","volume":"146","author":"G. M. Adelson-Velskii","year":"1962","unstructured":"G. M. Adel\u2019son-Vel\u2019skii 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-1263, 1962. 72","journal-title":"An Algorithm for the Organisation of Information"},{"key":"6_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-51859-2_10","volume-title":"Proc. Symp. on Optimal Algorithms, Varna","author":"A. Andersson","year":"1989","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. 73"},{"key":"6_CR3","volume-title":"Effcient Search Trees","author":"A. Andersson","year":"1990","unstructured":"A. Andersson. Effcient Search Trees. PhD thesis, Department of Computer Science, Lund University, Sweden, 1990. 73, 73, 82"},{"key":"6_CR4","doi-asserted-by":"publisher","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. 73","journal-title":"Acta Informatica"},{"key":"6_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-52846-6_82","volume-title":"SWAT\u201990","author":"A. Andersson","year":"1990","unstructured":"A. Andersson and T. W. Lai. Fast updating of well-balanced trees. In SWAT\u201990, volume 447 of LNCS, pages 111\u2013121. Springer-Verlag, 1990. 73"},{"key":"6_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/3-540-54945-5_71","volume-title":"ISA\u201991","author":"A. Andersson","year":"1991","unstructured":"A. Andersson and T. W. Lai. Comparison-effcient and write-optimal searching and sorting. In ISA\u201991, volume 557 of LNCS, pages 273\u2013282. Springer-Verlag, 1991. 73, 75"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0304-3975(80)90018-3","volume":"11","author":"N. Blum","year":"1980","unstructured":"N. Blum and K. Mehlhorn. On the average number of rebalancing operations in weight-balanced trees. Theoretical Computer Science, 11:303\u2013320, 1980. 72","journal-title":"Theoretical Computer Science"},{"key":"6_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/3-540-61422-2_151","volume-title":"SWAT\u2019 96","author":"R. Fagerberg","year":"1996","unstructured":"R. Fagerberg. Binary search trees: How low can you go? In SWAT\u2019 96, volume 1097 of LNCS, pages 428\u2013439. Springer-Verlag, 1996. 73, 73, 74, 82, 82"},{"doi-asserted-by":"crossref","unstructured":"L. J. Guibas and R. Sedgewick. A Dichromatic Framework for Balanced Trees. In 19th FOCS, pages 8\u201321, 1978. 72","key":"6_CR9","DOI":"10.1109\/SFCS.1978.3"},{"unstructured":"D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973. 74","key":"6_CR10"},{"key":"6_CR11","volume-title":"Effcient Maintenance of Binary Search Trees","author":"T. Lai","year":"1990","unstructured":"T. Lai. Effcient Maintenance of Binary Search Trees. PhD thesis, Department of Computer Science, University of Waterloo, Canada., 1990. 73, 73"},{"key":"6_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/3-540-52282-4_42","volume-title":"STACS\u201990","author":"T. Lai","year":"1990","unstructured":"T. Lai and D. Wood. Updating almost complete trees or one level makes all the difference. In STACS\u201990, volume 415 of LNCS, pages 188\u2013194. Springer-Verlag, 1990. 73"},{"key":"6_CR13","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, T. Ottmann, and H.-W. Six. Implementing dictionaries using binary trees of very small height. Inf. Proc. Letters, 5:11\u201314, 1976. 73, 79","journal-title":"Inf. Proc. Letters"},{"issue":"1","key":"6_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM J. on Computing, 2(1):33\u201343, 1973. 72","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"6_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1137\/0213015","volume":"13","author":"T. Ottmann","year":"1984","unstructured":"T. Ottmann, D. S. Parker, A. L. Rosenberg, H. W. Six, and D. Wood. Minimalcost brother trees. SIAM J. Computing, 13(1):197\u2013217, 1984. 74","journal-title":"SIAM J. Computing"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan. Amortized computational complexity. SIAM J. on Algebraic and Discrete Methods, 6:306\u2013318, 1985. 81","journal-title":"SIAM J. on Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46691-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T05:28:01Z","timestamp":1550726881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46691-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540668367","9783540466918"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-46691-6_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}