{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T05:21:36Z","timestamp":1741152096249,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642192210"},{"type":"electronic","value":"9783642192227"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_23","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T08:03:12Z","timestamp":1300089792000},"page":"226-237","source":"Crossref","is-referenced-by-count":0,"title":["Skip Lift: A Probabilistic Alternative to Red-Black Trees"],"prefix":"10.1007","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Karim","family":"Dou\u00efeb","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/s004539900061","volume":"16","author":"C.R. Aragon","year":"1996","unstructured":"Aragon, C.R., Seidel, R.: Randomized search trees. Algorithmica\u00a016, 464\u2013497 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"23_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00453-004-1138-6","volume":"42","author":"A. Bagchi","year":"2005","unstructured":"Bagchi, A., Buchsbaum, A.L., Goodrich, M.T.: Biased skip lists. Algorithmica\u00a042(1), 31\u201348 (2005)","journal-title":"Algorithmica"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Informatica\u00a01, 173\u2013189 (1972)","journal-title":"Acta Informatica"},{"issue":"3","key":"23_CR4","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"S.W. Bent","year":"1985","unstructured":"Bent, S.W., Sleator, D., Tarjan, R.: Biased search trees. SIAM Journal on Computing\u00a014(3), 545\u2013568 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR5","unstructured":"Bose, P., Dou\u00efeb, K., Langerman, S.: Dynamic optimality for skip lists and B-trees. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp. 1106\u20131114 (2008)"},{"issue":"2","key":"23_CR6","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/S0022-0000(03)00013-8","volume":"67","author":"G.S. Brodal","year":"2003","unstructured":"Brodal, G.S., Lagogiannis, G., Makris, C., Tsakalidis, A.K., Tsichlas, K.: Optimal finger search trees in the pointer machine. J. Comput. Syst. Sci.\u00a067(2), 381\u2013418 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/3-540-36494-3_26","volume-title":"STACS 2003","author":"H. Br\u00f6nnimann","year":"2003","unstructured":"Br\u00f6nnimann, H., Cazals, F., Durand, M.: Randomized jumplists: A jump-and-walk dictionary data structure. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 283\u2013294. Springer, Heidelberg (2003)"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/297096.297111","volume":"3","author":"S. Cho","year":"1998","unstructured":"Cho, S., Sahni, S.: Weight-biased leftist trees and modified skip lists. J. Exp. Algorithmics\u00a03, 2 (1998)","journal-title":"J. Exp. Algorithmics"},{"issue":"10","key":"23_CR9","doi-asserted-by":"publisher","first-page":"3139","DOI":"10.1002\/j.1538-7305.1983.tb03469.x","volume":"62","author":"J. Feigenbaum","year":"1983","unstructured":"Feigenbaum, J., Tarjan, R.: Two new kinds of biased search trees. Bell System Technical Journal\u00a062(10), 3139\u20133158 (1983)","journal-title":"Bell System Technical Journal"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1142\/S0129054196000117","volume":"7","author":"R. Fleischer","year":"1996","unstructured":"Fleischer, R.: A simple balanced search tree with O(1) worst-case update time. International Journal of Foundations of Computer Science\u00a07, 137\u2013149 (1996)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-03367-4_31","volume-title":"Algorithms and Data Structures","author":"B. Haeupler","year":"2009","unstructured":"Haeupler, B., Sen, S., Tarjan, R.E.: Rank-balanced trees. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 351\u2013362. Springer, Heidelberg (2009)"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Leonidas, R.S., Guibas, J.: A dichromatic framework for balanced trees. In: Proc. 19th IEEE Symp. on Foundations of Computer Science, pp. 8\u201321 (1978)","DOI":"10.1109\/SFCS.1978.3"},{"issue":"3","key":"23_CR13","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C. Levcopoulos","year":"1988","unstructured":"Levcopoulos, C., Overmars, M.: A balanced search tree with O(1) worst-case update time. Acta Informatica\u00a026(3), 269\u2013277 (1988)","journal-title":"Acta Informatica"},{"key":"23_CR14","unstructured":"Martinez, C., Roura, S.: Optimal and nearly optimal static weighted skip lists. Technical report, LSI-95-34-R, Dept. Llenguatges i Sistemes Inform\u00e0tics (Universitat Polit\u00e8chnica de Catalunya) (1995)"},{"issue":"2","key":"23_CR15","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/274787.274812","volume":"45","author":"C. Mart\u00ednez","year":"1998","unstructured":"Mart\u00ednez, C., Roura, S.: Randomized binary search trees. J. ACM\u00a045(2), 288\u2013323 (1998)","journal-title":"J. ACM"},{"key":"23_CR16","unstructured":"Munro, I., Papadakis, T., Sedgewick, R.: Deterministic skip lists. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 367\u2013375 (1992)"},{"key":"23_CR17","unstructured":"Papadakis, T.: Skip lists and probabilistic analysis of algorithms. PhD thesis, University of Waterloo, Department of Computer Science and Faculty of Mathematics (Available as Tech. Report CS-93-28) (1993)"},{"issue":"6","key":"23_CR18","doi-asserted-by":"publisher","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\u00a033(6), 668\u2013676 (1990)","journal-title":"Communications of the ACM"},{"issue":"5","key":"23_CR19","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. Process. Lett.\u00a016(5), 253\u2013257 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T06:37:11Z","timestamp":1741070231000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}