{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:57:51Z","timestamp":1708563471802},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s00236-023-00448-2","type":"journal-article","created":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T13:02:08Z","timestamp":1702645328000},"page":"53-66","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Balancing m-ary search trees with compressions on the fringe"],"prefix":"10.1007","volume":"61","author":[{"given":"Shuyang","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Hatem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hosam","family":"Mahmoud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,15]]},"reference":[{"key":"448_CR1","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1017\/S026996480000084X","volume":"2","author":"D Aldous","year":"1988","unstructured":"Aldous, D., Flannery, B., Palacios, J.L.: Two applications of urn processes the fringe analysis of search trees and the simulation of quasi-stationary distributions of Markov chains. Probab. Eng. Inf. Sci. 2, 293\u2013307 (1988)","journal-title":"Probab. Eng. Inf. Sci."},{"key":"448_CR2","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1002\/rsa.10005","volume":"19","author":"H Chern","year":"2001","unstructured":"Chern, H., Hwang, H.: Phase changes in random $$m$$-ary search trees and generalized Quicksort. Random Struct. Algorithms 19, 316\u2013358 (2001)","journal-title":"Random Struct. Algorithms"},{"key":"448_CR3","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D Comer","year":"1979","unstructured":"Comer, D.: The ubiquitous B-tree. Comput. Surveys 11, 121\u2013137 (1979)","journal-title":"Comput. Surveys"},{"key":"448_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01210596","volume":"30","author":"L Devroye","year":"1993","unstructured":"Devroye, L.: On the expected height of fringe-balanced trees. Acta Inf. 30, 459\u2013466 (1993)","journal-title":"Acta Inf."},{"key":"448_CR5","unstructured":"Frobenius, G.: \u00dcber matrizen aus nicht negativen elementen. Sitzungsber, K\u00f6nigl. Preuss. Akad. Wiss. 456\u2013477 (1912)"},{"key":"448_CR6","doi-asserted-by":"publisher","first-page":"1224","DOI":"10.1017\/apr.2020.38","volume":"52","author":"S Janson","year":"2020","unstructured":"Janson, S.: Mean and variance of balanced P\u00f3lya urns. Adv. Appl. Probab. 52, 1224\u20131248 (2020)","journal-title":"Adv. Appl. Probab."},{"key":"448_CR7","volume-title":"The Art of Computer Programming","author":"D Knuth","year":"1973","unstructured":"Knuth, D.: The Art of Computer Programming, vol. 3. Addison-Wesley, Reading (1973)"},{"key":"448_CR8","volume-title":"Evolution of Random Search Trees","author":"H Mahmoud","year":"1992","unstructured":"Mahmoud, H.: Evolution of Random Search Trees. Wiley, New York (1992)"},{"key":"448_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0020-0190(97)00184-1","volume":"65","author":"H Mahmoud","year":"1998","unstructured":"Mahmoud, H.: On rotations in fringe-balanced binary trees. Inf. Process. Lett. 65, 41\u201346 (1998)","journal-title":"Inf. Process. Lett."},{"key":"448_CR10","doi-asserted-by":"publisher","DOI":"10.1201\/9781420059847","volume-title":"P\u00f3lya Urn Models","author":"H Mahmoud","year":"2008","unstructured":"Mahmoud, H.: P\u00f3lya Urn Models. Chapman-Hall, Orlando (2008)"},{"key":"448_CR11","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/0196-6774(89)90023-0","volume":"10","author":"H Mahmoud","year":"1989","unstructured":"Mahmoud, H., Pittel, B.: Analysis of the space of search trees under the random insertion algorithm. J. Algorithms 10, 52\u201375 (1989)","journal-title":"J. Algorithms"},{"key":"448_CR12","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01608487","volume":"2","author":"A Panholzer","year":"1998","unstructured":"Panholzer, A., Prodinger, H.: An analytic approach for the analysis of rotations in fringe-balanced binary search trees. Ann. Combin. 2, 173\u2013184 (1998)","journal-title":"Ann. Combin."},{"key":"448_CR13","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/BF01449896","volume":"64","author":"O Perron","year":"1907","unstructured":"Perron, O.: Zur theorie der matrices. Math. Ann. 64, 248\u2013263 (1907)","journal-title":"Math. Ann."},{"key":"448_CR14","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/0196-6774(85)90003-3","volume":"6","author":"P Poblete","year":"1985","unstructured":"Poblete, P., Munro, J.: The analysis of a fringe heuristic for binary search trees. J. Algorithms 6, 336\u2013350 (1985)","journal-title":"J. Algorithms"},{"key":"448_CR15","volume-title":"Stochastic Processes","author":"S Ross","year":"1983","unstructured":"Ross, S.: Stochastic Processes. John Wiley, New York (1983)"},{"key":"448_CR16","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0304-4149(96)00094-4","volume":"65","author":"R Smythe","year":"1996","unstructured":"Smythe, R.: Central limit theorems for urn models. Stochastic Processes Appl. 65, 115\u2013137 (1996)","journal-title":"Stochastic Processes Appl."},{"key":"448_CR17","first-page":"109","volume":"27","author":"R Baeze-Yates","year":"1995","unstructured":"Baeze-Yates, R.: Fringe analysis revisited. Assoc. Comput. Mach.: Comput. Surveys 27, 109\u2013119 (1995)","journal-title":"Assoc. Comput. Mach.: Comput. Surveys"},{"key":"448_CR18","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1051\/ita\/1989230303351","volume":"23","author":"M R\u00e9gnier","year":"1989","unstructured":"R\u00e9gnier, M.: A limiting distribution for quicksort. RAIRO-Theor. Inf. Appl. 23, 335\u2013343 (1989)","journal-title":"RAIRO-Theor. Inf. Appl."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-023-00448-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-023-00448-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-023-00448-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T19:02:39Z","timestamp":1708542159000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-023-00448-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,15]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["448"],"URL":"https:\/\/doi.org\/10.1007\/s00236-023-00448-2","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,15]]},"assertion":[{"value":"25 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}