{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:11:40Z","timestamp":1743149500056,"version":"3.40.3"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_41","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"566-577","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Zip Trees"],"prefix":"10.1007","author":[{"given":"Robert E.","family":"Tarjan","sequence":"first","affiliation":[]},{"given":"Caleb C.","family":"Levy","sequence":"additional","affiliation":[]},{"given":"Stephen","family":"Timmel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"issue":"4","key":"41_CR1","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23(4), 493\u2013507 (1952)","journal-title":"Ann. Math. Stat."},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"Dean, B.C., Jones, Z.H.: Exploring the duality between skip lists and binary search trees. In: Proceedings of the 45th Annual Southeast Regional Conference, pp. 395\u2013400. ACM Press (2007)","DOI":"10.1145\/1233341.1233413"},{"issue":"4","key":"41_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2689412","volume":"11","author":"B Haeupler","year":"2015","unstructured":"Haeupler, B., Sen, S., Tarjan, R.E.: Rank-balanced trees. ACM Trans. Algorithms 11(4), 1\u201326 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"41_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/321105.321108","volume":"9","author":"TN Hibbard","year":"1962","unstructured":"Hibbard, T.N.: Some combinatorial properties of certain trees with applications to searching and sorting. J. ACM 9(1), 13\u201328 (1962)","journal-title":"J. ACM"},{"issue":"2","key":"41_CR5","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 45(2), 288\u2013323 (1998)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"41_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(95)00141-I","volume":"153","author":"H Prodinger","year":"1996","unstructured":"Prodinger, H.: Combinatorics of geometrically distributed random variables: left-to-right maxima. Discrete Math. 153(1\u20133), 253\u2013270 (1996)","journal-title":"Discrete Math."},{"issue":"6","key":"41_CR7","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. Commun. ACM 33(6), 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"issue":"4\u20135","key":"41_CR8","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R Seidel","year":"1996","unstructured":"Seidel, R., Aragon, C.R.: Randomized search trees. Algorithmica 16(4\u20135), 464\u2013497 (1996)","journal-title":"Algorithmica"},{"issue":"2","key":"41_CR9","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02576649","volume":"17","author":"R Sprugnoli","year":"1980","unstructured":"Sprugnoli, R.: Randomly balanced binary trees. Calcolo 17(2), 99\u2013117 (1980)","journal-title":"Calcolo"},{"issue":"1","key":"41_CR10","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF00995807","volume":"9","author":"CJ Stephenson","year":"1980","unstructured":"Stephenson, C.J.: A method for constructing binary search trees by making insertions at the root. Int. J. Comput. Inf. Sci. 9(1), 15\u201329 (1980)","journal-title":"Int. J. Comput. Inf. Sci."},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E., Levy, C.C., Timmel, S.: Zip trees. arXiv e-prints arXiv:1806.06726 (2018)","DOI":"10.1007\/978-3-030-24766-9_41"},{"key":"41_CR12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265","volume-title":"Data structures and network algorithms","author":"RE Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data structures and network algorithms. Society for Industrial and Applied Mathematics, Philadelphia (1983)"},{"key":"41_CR13","unstructured":"Timmel, S.: Zip trees: a new approach to concurrent binary search trees. http:\/\/arks.princeton.edu\/ark:\/88435\/dsp01gh93h214f. Senior Thesis, Department of Mathematics, Princeton University (2017)"},{"issue":"4","key":"41_CR14","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229\u2013239 (1980)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24766-9_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:56:18Z","timestamp":1710266178000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}