{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T16:24:52Z","timestamp":1776356692259,"version":"3.51.2"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01994884","type":"journal-article","created":{"date-parts":[[2005,8,4]],"date-time":"2005-08-04T20:22:09Z","timestamp":1123186929000},"page":"316-332","source":"Crossref","is-referenced-by-count":19,"title":["Average search and update costs in skip lists"],"prefix":"10.1007","volume":"32","author":[{"given":"Thomas","family":"Papadakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Ian Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patricio V.","family":"Poblete","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01994884_CR1","doi-asserted-by":"crossref","unstructured":"Aragon, C. R. and Seidel, R. G.Randomized search trees. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park, NC, Oct. 1989, pp. 540\u2013545.","DOI":"10.1109\/SFCS.1989.63531"},{"issue":"1","key":"BF01994884_CR2","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1093\/comjnl\/32.1.68","volume":"32","author":"J. Culberson","year":"1989","unstructured":"Culberson, J. and Munro, J. I.Explaining the behaviour of binary search trees under prolonged updates: a model and simulations. The Computer Journal, vol. 32, no. 1, Feb. 1989, pp. 68\u201375.","journal-title":"The Computer Journal"},{"issue":"3","key":"BF01994884_CR3","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01840390","volume":"5","author":"J. Culberson","year":"1990","unstructured":"Culberson, J. and Munro, J. I.Analysis of the standard deletion algorithms in exact fit domain for binary search trees. Algorithmica, vol. 5, no. 3, 1990, pp. 295\u2013311.","journal-title":"Algorithmica"},{"key":"BF01994884_CR4","series-title":"Technical Report","volume-title":"Expected time analysis of skip lists","author":"L. Devroye","year":"1990","unstructured":"Devroye, L.Expected time analysis of skip lists. Technical Report, School of Computer Science, McGill University, Montreal, 1990."},{"key":"BF01994884_CR5","doi-asserted-by":"crossref","unstructured":"Devroye, L.A limit theory for random skip lists. Annals of Applied Probability, to appear.","DOI":"10.1214\/aoap\/1177005651"},{"key":"BF01994884_CR6","unstructured":"Flajolet, P.Mathematical methods in the analysis of algorithms and data structures. In Trends in Theoretical Computer Science, B\u00f6rger, E., ed., Computer Science Press, 1988, pp. 225\u2013304."},{"key":"BF01994884_CR7","unstructured":"Knuth, D. E.The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 1973."},{"key":"BF01994884_CR8","unstructured":"Mahmoud, H.Evolutions of Random Search Trees, John Wiley & Sons, 1991."},{"key":"BF01994884_CR9","doi-asserted-by":"crossref","unstructured":"Papadakis, T., Munro, J. I. and Poblete, P.Analysis of the expected search cost in skip lists. Lecture Notes in Computer Science, no. 447, Proceedings of the 2nd Scandinavian Workshop of Algorithm Theory. Bergen, Norway, July 1990, pp. 160\u2013172.","DOI":"10.1007\/3-540-52846-6_86"},{"issue":"6","key":"BF01994884_CR10","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh, W.Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, vol. 33, no. 6, June 1990, pp. 668\u2013676.","journal-title":"Communications of the ACM"},{"key":"BF01994884_CR11","series-title":"Technical Report","volume-title":"A skip list cook book","author":"W. Pugh","year":"1989","unstructured":"Pugh, W.A skip list cook book. Technical Report CS-TR-2286, Department of Computer Science, University of Maryland, College Park, July 1989."},{"key":"BF01994884_CR12","doi-asserted-by":"crossref","unstructured":"Vitter, J. S. and Flajolet, P.Average-case analysis of algorithms and data structures. InHandbook of Theoretical Computer Science, The MIT Press, 1990, pp. 431\u2013524.","DOI":"10.1016\/B978-0-444-88071-0.50014-X"}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994884.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01994884\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T17:37:22Z","timestamp":1586367442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01994884"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01994884"],"URL":"https:\/\/doi.org\/10.1007\/bf01994884","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}