{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:25:15Z","timestamp":1726406715199},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578116"},{"type":"electronic","value":"9783540483373"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57811-0_13","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:23:53Z","timestamp":1330262633000},"page":"152-166","source":"Crossref","is-referenced-by-count":0,"title":["Efficient reorganization of binary search trees"],"prefix":"10.1007","author":[{"given":"Micha","family":"Hofri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"issue":"#4","key":"13_CR1","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/322092.322094","volume":"25","author":"B. Allen","year":"1978","unstructured":"B. Allen, I. Munro, \u201cSelf-Organizing Search Trees\u201d, JACM 25, #4, 526\u2013535 (1978).","journal-title":"JACM"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"M.J. Atallah, S.R. Kosaraju, L.L. Larmore, G.L. Miller, S-H Teng, \u201cConstructing Trees in Parallel\u201d, In Proc. of the 2nd IEEE Symposium on Parallel Algorithms and Architectures, (1989).","DOI":"10.1145\/72935.72980"},{"key":"13_CR3","unstructured":"P.J. Bayer, \u201cImproved Bounds on the Costs of Optimal and Balanced Search Trees\u201d, Tech. Memo. 69, Proj. MAC M.I.T. Cambridge MA 1975."},{"issue":"1","key":"13_CR4","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1137\/0208007","volume":"8","author":"J. Bitner","year":"1979","unstructured":"J. Bitner, \u201cHeuristics that Dynamically Organize Data Structures\u201d, SIAM J. Comput, 8,1, pp. 82\u2013110, 1979.","journal-title":"SIAM J. Comput"},{"key":"13_CR5","unstructured":"A. Boneh, M.Hofri, \u201cThe Coupon-Collector Problem Revisited.\u201d Purdue University, Department of Computer Science, CSD-TR-952, February 1990."},{"key":"13_CR6","volume-title":"An Introduction to Probability Theory and its Applications","author":"W. Feller","year":"1968","unstructured":"W. Feller, An Introduction to Probability Theory and its Applications John Willey, New York, 1968."},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"M. L. Fredman, \u201cTwo Applications of a Probabilistic Search Technique: Sorting X+Y and Building Balanced Search Trees\u201d, 7th ACM Symp. on Theory of Computing, Albuquerque 1975.","DOI":"10.1145\/800116.803774"},{"key":"13_CR8","unstructured":"I. Galperin, R. Rivest, \u201cScapegoat Trees\u201d, In Proc. of the 4th ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, January 25\u201327, 1993."},{"key":"13_CR9","first-page":"41","volume":"16","author":"R. Guttler","year":"1980","unstructured":"R. Guttler, K. Mehlhorn, W. Schneider, \u201cBinary Search Trees: Average and Worst Case Behavior\u201d, Jour. of Information Processing and Cybernetics, 16, 41\u201361, (1980).","journal-title":"Jour. of Information Processing and Cybernetics"},{"key":"13_CR10","first-page":"533","volume":"12","author":"M. Hofri","year":"1991","unstructured":"M. Hofri, H. Shachnai, \u201cSelf-Organizing Lists and Independent References \u2014 a Statistical Synergy\u201d, Jour. of Alg., 12, 533\u2013555, (1991).","journal-title":"Jour. of Alg."},{"key":"13_CR11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(91)90040-O","volume":"37","author":"M. Hofri","year":"1991","unstructured":"M. Hofri, H. Shachnai, \u201cOn the Optimality of Counter Scheme for Dynamic Linear Lists\u201d, Inf. Process. Lett., 37, 175\u2013179, (1991).","journal-title":"Inf. Process. Lett."},{"key":"13_CR12","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF00289510","volume":"1","author":"T. C. Hu","year":"1972","unstructured":"T.C. Hu, K. C. Tan, \u201cLeast Upper Bound on the Cost of Optimum Binary Search Trees\u201d, Acta Information, 1, 307\u2013310, (1972).","journal-title":"Acta Information"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"D.G. Kirkpatrick, T.M. Przytycka, \u201cParallel Construction of Binary Trees with Almost Optimal Weighted Path Length\u201d, In Proc. of the 2nd IEEE Symposium on Parallel Algorithms and Architectures, (1990).","DOI":"10.1145\/97444.97690"},{"key":"13_CR14","first-page":"11","volume":"1","author":"D. E. Knuth","year":"1971","unstructured":"D.E. Knuth, \u201cOptimum Binary Search Trees\u201d, Acta Informatica 1, 11\u201325,1971.","journal-title":"Acta Informatica"},{"key":"13_CR15","volume-title":"The Art of Computer Programming, Vol 3: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D.E. Knuth, The Art of Computer Programming, Vol 3: Sorting and Searching Addison-Wesley, Reading MA 1973."},{"key":"13_CR16","unstructured":"T. W. Lai, D. Wood, \u201cAdaptive Heuristics for Binary Search Trees and Constant Linkage Cost\u201d, In Proc. of the end ACM-SIAM Symposium on Discrete Algorithms, pp. 72\u201377, San Francisco, CA, January 28\u201330, 1991."},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF00264563","volume":"5","author":"K. Mehlhorn","year":"1975","unstructured":"K. Mehlhorn, \u201cNearly Optimal Binary Search Trees\u201d, Acta Informatica 5 287\u2013295, (1975).","journal-title":"Acta Informatica"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, A. Tsakalidis, \u201cData. Structures\u201d. In J. van Leeuwen, editor, Algorithms and Complexity, Vol A, chapter 6, pp. 301\u2013341, Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50011-4"},{"issue":"#3","key":"13_CR19","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D.D. Sleator, R.E. Tarjan, \u201cSelf-Adjusting Binary search Trees\u201d, JACM 32, #3, 652\u2013686 (1985).","journal-title":"JACM"},{"issue":"2","key":"13_CR20","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"D.D. Sleator, R.E. Tarjan, \u201cAmortized Efficiency of List Update and Paging Rules\u201d, Commun. ACM 28,2, pp. 202\u2013208, (1985).","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57811-0_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:14:14Z","timestamp":1605647654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57811-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578116","9783540483373"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-57811-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}