{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T21:22:33Z","timestamp":1775078553531,"version":"3.50.1"},"reference-count":27,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4576,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1994,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A process of growing a random recursive tree <jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is studied. The sequence {<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>} is shown to be a sequence of \u201csnapshots\u201d of a Crump\u2013Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of <jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is asymptotic, with probability one, to <jats:italic>c<\/jats:italic> log <jats:italic>n<\/jats:italic>. In particular, <jats:italic>c<\/jats:italic> = <jats:italic>e<\/jats:italic> = 2.718 \u2026 for the uniform recursive tree, and <jats:italic>c<\/jats:italic> = (2\u03b3)<jats:sup>\u22121<\/jats:sup>, where \u03b3<jats:italic>e<\/jats:italic><jats:sup>1+\u03b3<\/jats:sup> = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random <jats:italic>m<\/jats:italic>\u2010ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union\u2010find tree, and our theorem on the height of the uniform recursive tree. \u00a9 1994 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240050207","type":"journal-article","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T20:18:21Z","timestamp":1180729101000},"page":"337-347","source":"Crossref","is-referenced-by-count":118,"title":["Note on the heights of random recursive trees and random <i>m<\/i>\u2010ary search trees"],"prefix":"10.1002","volume":"5","author":[{"given":"Boris","family":"Pittel","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Lecture Notes in Computer Science","author":"Bergeron F.","year":"1992"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/1426138"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.2307\/3213469"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(68)90005-X"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5930"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00265991"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010206"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90061-2"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/2683046"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996611"},{"key":"e_1_2_1_12_2","first-page":"903","article-title":"Discussion on Professor Kingman's paper","volume":"1","author":"Kesten H.","year":"1973","journal-title":"Ann. Probab."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996266"},{"key":"e_1_2_1_14_2","volume-title":"The Art of Computer Programming 3. Sorting and Searching","author":"Knuth D. E.","year":"1973"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90009-9"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(92)90252-S"},{"key":"e_1_2_1_17_2","unstructured":"H.Mahmoud Personal communication 1992."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0605010"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040204"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005874"},{"key":"e_1_2_1_21_2","first-page":"49","article-title":"Recursive trees with no nodes of outdegree one","volume":"66","author":"Meir A.","year":"1974","journal-title":"Congr. Numer."},{"key":"e_1_2_1_22_2","first-page":"125","volume-title":"London Math. Soc. Lecture Notes, Ser 13","author":"Moon J.","year":"1974"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(70)90071-4"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.2307\/3213526"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(84)90141-0"},{"key":"e_1_2_1_26_2","first-page":"151","article-title":"The height of binary search trees","volume":"11","author":"Robson J.","year":"1979","journal-title":"Aust. Comput. J."},{"key":"e_1_2_1_27_2","first-page":"313","volume-title":"Random Graphs '87","author":"Szymanski J.","year":"1990"},{"key":"e_1_2_1_28_2","first-page":"297","article-title":"On the nonuniform random recursive tree","volume":"33","author":"Szymanski J.","year":"1987","journal-title":"Ann. Discrete Math."}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240050207","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240050207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,15]],"date-time":"2023-10-15T22:34:52Z","timestamp":1697409292000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240050207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["10.1002\/rsa.3240050207"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240050207","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}