{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T03:51:46Z","timestamp":1794369106232,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642106309","type":"print"},{"value":"9783642106316","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10631-6_84","type":"book-chapter","created":{"date-parts":[[2009,12,4]],"date-time":"2009-12-04T02:03:43Z","timestamp":1259892223000},"page":"832-841","source":"Crossref","is-referenced-by-count":2,"title":["Deletion without Rebalancing in Multiway Search Trees"],"prefix":"10.1007","author":[{"given":"Siddhartha","family":"Sen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"84_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":"84_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"84_CR3","doi-asserted-by":"crossref","unstructured":"Bayer, R.: Binary B-trees for virtual memory. In: SIGFIDET, pp. 219\u2013235 (1971)","DOI":"10.1145\/1734714.1734731"},{"key":"84_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."},{"issue":"3","key":"84_CR5","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indexes. Acta Informatica\u00a01(3), 173\u2013189 (1972)","journal-title":"Acta Informatica"},{"issue":"2","key":"84_CR6","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D.: The ubiquitous B-tree. ACM Computing Surveys\u00a011(2), 121\u2013137 (1979)","journal-title":"ACM Computing Surveys"},{"key":"84_CR7","volume-title":"Transaction Processing: Concepts and Techniques","year":"1993","unstructured":"Gray, J., Reuter, A. (eds.): Transaction Processing: Concepts and Techniques. Morgan Kaufmann, San Mateo (1993)"},{"key":"84_CR8","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: FOCS, pp. 8\u201321 (1978)","DOI":"10.1109\/SFCS.1978.3"},{"key":"84_CR9","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Sen, S., Tarjan, R.E.: Rank-balanced trees. In: WADS, pp. 351\u2013362 (2009)","DOI":"10.1007\/978-3-642-03367-4_31"},{"issue":"1","key":"84_CR10","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/202660.202666","volume":"24","author":"J. Jannink","year":"1995","unstructured":"Jannink, J.: Implementing deletion in B\u2009+\u2009-trees. SIGMOD Record\u00a024(1), 33\u201338 (1995)","journal-title":"SIGMOD Record"},{"key":"84_CR11","doi-asserted-by":"crossref","unstructured":"Johnson, T., Shasha, D.: Utilization of B-trees with inserts, deletes and modifies. In: PODS, pp. 235\u2013246 (1989)","DOI":"10.1145\/73721.73745"},{"issue":"1","key":"84_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0022-0000(93)90020-W","volume":"47","author":"T. Johnson","year":"1993","unstructured":"Johnson, T., Shasha, D.: B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half. Journal of Computer and System Sciences\u00a047(1), 45\u201376 (1993)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"84_CR13","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1145\/141484.130338","volume":"21","author":"C. Mohan","year":"1992","unstructured":"Mohan, C., Levine, F.: ARIES\/IM: an efficient and high concurrency index management method using write-ahead logging. SIGMOD Record\u00a021(2), 371\u2013380 (1992)","journal-title":"SIGMOD Record"},{"issue":"1","key":"84_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"Nievergelt, J., Reingold, E.M.: Binary search trees of bounded balance. SIAM J. on Comput.\u00a02(1), 33\u201343 (1973)","journal-title":"SIAM J. on Comput."},{"issue":"1","key":"84_CR15","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"},{"key":"84_CR16","unstructured":"Olson, M.A., Bostic, K., Seltzer, M.I.: Berkeley DB. In: USENIX Annual, FREENIX Track, pp. 183\u2013191 (1999)"},{"key":"84_CR17","unstructured":"Olson, M.A., Bostic, K., Seltzer, M.I.: Berkeley DB (2000)"},{"key":"84_CR18","unstructured":"Sedgewick, R.: Left-leaning red-black trees, www.cs.princeton.edu\/~rs\/talks\/LLRB\/LLRB.pdf"},{"key":"84_CR19","unstructured":"Sen, S., Tarjan, R.E.: Deletion without rebalancing in balanced binary trees. In: SODA (to appear, 2010)"},{"key":"84_CR20","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"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10631-6_84.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:32:26Z","timestamp":1606167146000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10631-6_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106309","9783642106316"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6_84","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}