{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T03:04:23Z","timestamp":1773025463502,"version":"3.50.1"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2010,3,5]],"date-time":"2010-03-05T00:00:00Z","timestamp":1267747200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,5]]},"abstract":"<jats:p>We study the number of random records in a binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.<\/jats:p>","DOI":"10.1017\/s096354830999068x","type":"journal-article","created":{"date-parts":[[2010,3,5]],"date-time":"2010-03-05T09:30:19Z","timestamp":1267781419000},"page":"391-424","source":"Crossref","is-referenced-by-count":19,"title":["Random Records and Cuttings in Binary Search Trees"],"prefix":"10.1017","volume":"19","author":[{"given":"CECILIA","family":"HOLMGREN","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2010,3,5]]},"reference":[{"key":"S096354830999068X_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4015-8"},{"key":"S096354830999068X_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S096354830999068X_ref10","doi-asserted-by":"crossref","unstructured":"[10] Holmgren C. (2009) A weakly 1-stable limiting distribution for the number of random records and cuttings in split trees. Submitted.","DOI":"10.46298\/dmtcs.3570"},{"key":"S096354830999068X_ref9","first-page":"269","article-title":"Random records and cuttings in split trees: Extended abstract","volume":"AI","author":"Holmgren","year":"2008","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"S096354830999068X_ref8","volume-title":"Probability: A Graduate Course","author":"Gut","year":"2005"},{"key":"S096354830999068X_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20233"},{"key":"S096354830999068X_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_7"},{"key":"S096354830999068X_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5930"},{"key":"S096354830999068X_ref1","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1214\/aoap\/1015345394","article-title":"The profile of binary search trees","volume":"11","author":"Chauvin","year":"2001","journal-title":"Ann. Applied Probab."},{"key":"S096354830999068X_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-7915-6_24"},{"key":"S096354830999068X_ref11","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v12-1253"},{"key":"S096354830999068X_ref16","first-page":"43","article-title":"Quicksort algorithm again revisited","volume":"no. 2","author":"Knessl","year":"1999","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"S096354830999068X_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00216-X"},{"key":"S096354830999068X_ref7","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller","year":"1971"},{"key":"S096354830999068X_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20086"},{"key":"S096354830999068X_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700006698"},{"key":"S096354830999068X_ref17","volume-title":"The Art of Computer Programming I: Fundamental Algorithms","author":"Knuth","year":"1997"},{"key":"S096354830999068X_ref18","volume-title":"The Art of Computer Programming III: Sorting and Searching","author":"Knuth","year":"2002"},{"key":"S096354830999068X_ref4","first-page":"47","volume-title":"Stein's Method and Applications","author":"Devroye","year":"2005"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354830999068X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T19:36:44Z","timestamp":1685475404000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354830999068X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,5]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["S096354830999068X"],"URL":"https:\/\/doi.org\/10.1017\/s096354830999068x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,5]]}}}