{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:12:02Z","timestamp":1763467922607},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642033667"},{"type":"electronic","value":"9783642033674"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03367-4_31","type":"book-chapter","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T03:56:42Z","timestamp":1248062202000},"page":"351-362","source":"Crossref","is-referenced-by-count":10,"title":["Rank-Balanced Trees"],"prefix":"10.1007","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[]},{"given":"Siddhartha","family":"Sen","sequence":"additional","affiliation":[]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","first-page":"1259","volume":"3","author":"G.M. Adel\u2019son-Vel\u2019skii","year":"1962","unstructured":"Adel\u2019son-Vel\u2019skii, G.M., Landis, E.M.: An algorithm for the organization of information. Sov. Math. Dokl.\u00a03, 1259\u20131262 (1962)","journal-title":"Sov. Math. Dokl."},{"key":"31_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-57155-8_236","volume-title":"Algorithms and Data Structures","author":"A. Andersson","year":"1993","unstructured":"Andersson, A.: Balanced search trees made simple. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 60\u201371. Springer, Heidelberg (1993)"},{"doi-asserted-by":"crossref","unstructured":"Bayer, R.: Binary B-trees for virtual memory. In: SIGFIDET, pp. 219\u2013235 (1971)","key":"31_CR3","DOI":"10.1145\/1734714.1734731"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BF00289509","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R.: Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Inf.\u00a01, 290\u2013306 (1972)","journal-title":"Acta Inf."},{"doi-asserted-by":"crossref","unstructured":"Brown, M.R.: A storage scheme for height-balanced trees. Inf. Proc. Lett., 231\u2013232 (1978)","key":"31_CR5","DOI":"10.1016\/0020-0190(78)90005-4"},{"unstructured":"Foster, C.C.: A study of avl trees. Technical Report GER-12158, Goodyear Aerospace Corp. (1965)","key":"31_CR6"},{"doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: FOCS, pp. 8\u201321 (1978)","key":"31_CR7","DOI":"10.1109\/SFCS.1978.3"},{"key":"31_CR8","volume-title":"The Art of Computer Programming, Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming, Sorting and Searching, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"doi-asserted-by":"crossref","unstructured":"Nievergelt, J., Reingold, E.M.: Binary search trees of bounded balance. SIAM J. on Comput., 33\u201343 (1973)","key":"31_CR9","DOI":"10.1137\/0202005"},{"issue":"1","key":"31_CR10","first-page":"51","volume":"16","author":"H.J. Olivi\u00e9","year":"1982","unstructured":"Olivi\u00e9, H.J.: A new class of balanced search trees: Half balanced binary search trees. ITA\u00a016(1), 51\u201371 (1982)","journal-title":"ITA"},{"unstructured":"Sedgewick, R.: Left-leaning red-black trees, \n                  \n                    http:\/\/www.cs.princeton.edu\/rs\/talks\/LLRB\/LLRB.pdf","key":"31_CR11"},{"key":"31_CR12","volume-title":"The Algorithm Design Manual","author":"S.S. Skiena","year":"1998","unstructured":"Skiena, S.S.: The Algorithm Design Manual. Springer, Heidelberg (1998)"},{"issue":"5","key":"31_CR13","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0020-0190(83)90099-6","volume":"16","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Updating a balanced search tree in O(1) rotations. Inf. Proc. Lett.\u00a016(5), 253\u2013257 (1983)","journal-title":"Inf. Proc. Lett."},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebraic and Disc. Methods\u00a06, 306\u2013318 (1985)","journal-title":"SIAM J. Algebraic and Disc. Methods"},{"unstructured":"Tarjan, R.E.: Efficient top-down updating of red-black trees. Technical Report TR-006-85, Department of Computer Science, Princeton University (1985)","key":"31_CR15"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03367-4_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T01:29:50Z","timestamp":1552094990000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03367-4_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033667","9783642033674"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03367-4_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}