{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T16:25:21Z","timestamp":1776356721842,"version":"3.51.2"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4-5","license":[{"start":{"date-parts":[[1996,10,1]],"date-time":"1996-10-01T00:00:00Z","timestamp":844128000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,10]]},"DOI":"10.1007\/bf01940876","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T06:46:47Z","timestamp":1122792407000},"page":"464-497","source":"Crossref","is-referenced-by-count":145,"title":["Randomized search trees"],"prefix":"10.1007","volume":"16","author":[{"given":"R.","family":"Seidel","sequence":"first","affiliation":[]},{"given":"C. R.","family":"Aragon","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01940876_CR1","first-page":"1259","volume":"3","author":"G. M. Adel'son-Velskii","year":"1962","unstructured":"G. M. Adel'son-Velskii and Y. M. Landis, An algorithm for the organization of information,Soviet Math. Dokl,3 (1962), 1259\u20131262.","journal-title":"Soviet Math. Dokl"},{"key":"BF01940876_CR2","doi-asserted-by":"crossref","unstructured":"A. Andersson and T. Ottmann, Faster uniquely represented dictionaries,Proc. 32nd FOCS, 1991, pp. 642\u2013649.","DOI":"10.1109\/SFCS.1991.185430"},{"key":"BF01940876_CR3","unstructured":"H. Baumgarten, H. Jung, and K. Mehlhorn, Dynamic point location in general subdivision,Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms (SODA), 1992, pp. 250\u2013258."},{"key":"BF01940876_CR4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and E. McCreight, Organization and maintenance of large ordered indices,Act. Inf.,1 (1972), 173\u2013189.","journal-title":"Act. Inf."},{"key":"BF01940876_CR5","unstructured":"S. W. Bent and J. R. Driscoll, Randomly balanced search trees, Manuscript (1991)."},{"key":"BF01940876_CR6","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"S. W. Bent","year":"1985","unstructured":"S. W. Bent, D. D. Sleator, and R. E. Tarjan, Biased search trees,SIAM J. Comput.,14 (1985), 545\u2013568.","journal-title":"SIAM J. Comput."},{"key":"BF01940876_CR7","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1145\/321941.321944","volume":"23","author":"R. P. Brent","year":"1976","unstructured":"R. P. Brent, Fast multiple precision evaluation of elementary functions,J. Assoc. Comput. Mach.,23 (1976), 242\u2013251.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01940876_CR8","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0020-0190(79)90009-7","volume":"8","author":"M. Brown","year":"1979","unstructured":"M. Brown, Addendum to \u201cA Storage Scheme for Height-Balanced Trees,\u201dInform. Process. Lett.,8 (1979), 154\u2013156.","journal-title":"Inform. Process. Lett."},{"key":"BF01940876_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"K. L. Clarkson","year":"1993","unstructured":"K. L. Clarkson, K. Mehlhorn, and R. Seidel, Four results on randomized incremental construction,Comput. Geom. Theory Appl.,3 (1993), 185\u2013212.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF01940876_CR10","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1145\/5925.5930","volume":"33","author":"L. Devroye","year":"1986","unstructured":"L. Devroye, A note on the height of binary search trees,J. Assoc. Comput. Mach.,33 (1986), 489\u2013498.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01940876_CR11","unstructured":"M. Dietzfelbinger (private communication)."},{"key":"BF01940876_CR12","unstructured":"I. Galperin and R. L. Rivest, Scapegoat trees,Proc. 4th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1993, pp. 165\u2013174."},{"key":"BF01940876_CR13","doi-asserted-by":"crossref","unstructured":"L. J. Guibas and R. Sedgewick, A dichromatic framework for balanced trees,Proc. 19th FOCS, 1978, pp. 8\u201321.","DOI":"10.1109\/SFCS.1978.3"},{"key":"BF01940876_CR14","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1989\/90","unstructured":"T. Hagerup and C. R\u00fcb, A guided tour of Chernoff bounds,Inform. Process. Lett.,33 (1989\/90), 305\u2013308.","journal-title":"Inform. Process. Lett."},{"key":"BF01940876_CR15","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","volume":"68","author":"K. Hoffman","year":"1986","unstructured":"K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, Sorting Jordan sequences in linear time using level linked search trees,Inform. and Control,68 (1986), 170\u2013184.","journal-title":"Inform. and Control"},{"key":"BF01940876_CR16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E. McCreight","year":"1985","unstructured":"E. McCreight, Priority search trees,SIAM J. Comput.,14 (1985), 257\u2013276.","journal-title":"SIAM J. Comput."},{"key":"BF01940876_CR17","volume-title":"Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn,Sorting and Searching, Springer-Verlag, Berlin, 1984."},{"key":"BF01940876_CR18","volume-title":"Multi-Dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn,Multi-Dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984."},{"key":"BF01940876_CR19","unstructured":"K. Mehlhorn (private communication)."},{"key":"BF01940876_CR20","volume-title":"Algorithms, Software, Architectures, Information Processing 92, Vol. 1","author":"K. Mehlhorn","year":"1992","unstructured":"K. Mehlhorn and S. N\u00e4her, Algorithm design and software libraries: recent developments in the LEDA project, inAlgorithms, Software, Architectures, Information Processing 92, Vol. 1, Elsevier, Amsterdam, 1992."},{"key":"BF01940876_CR21","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/204865.204889","volume":"38","author":"K. Mehlhorn","year":"1995","unstructured":"K. Mehlhorn and S. N\u00e4her, LEDA, a platform for combinatorial and geometric computing.Commun. ACM,38 (1995), 95\u2013102.","journal-title":"Commun. ACM"},{"key":"BF01940876_CR22","unstructured":"K. Mehlhorn and R. Raman (private communication)."},{"key":"BF01940876_CR23","volume-title":"Computational Geometry: An Introduction through Randomized Algorithms","author":"K. Mulmuley","year":"1994","unstructured":"K. Mulmuley,Computational Geometry: An Introduction through Randomized Algorithms, Prentice-Hall, Englewood Cliffs, NJ, 1994."},{"key":"BF01940876_CR24","series-title":"Tech. Report MPI-I-93-109","volume-title":"LEDA User Manual Version 3.0","author":"S. N\u00e4her","year":"1993","unstructured":"S. N\u00e4her, LEDA User Manual Version 3.0. Tech. Report MPI-I-93-109, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, 1993."},{"key":"BF01940876_CR25","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"J. Nievergelt and E. M. Reingold, Binary search trees of bounded balance,SIAM J. Comput. 2 (1973), 33\u201343.","journal-title":"SIAM J. Comput."},{"key":"BF01940876_CR26","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"W. Pugh, Skip lists: a probabilistic alternative to balanced trees.Commun. ACM,33 (1990), 668\u2013676.","journal-title":"Commun. ACM"},{"key":"BF01940876_CR27","doi-asserted-by":"crossref","unstructured":"W. Pugh and T. Teitelbaum, Incremental computation via function caching,Proc. 16th ACM POPL, 1989, pp. 315\u2013328.","DOI":"10.1145\/75277.75305"},{"key":"BF01940876_CR28","unstructured":"D. D. Sleator (private communication)."},{"key":"BF01940876_CR29","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach.,32 (1985), 652\u2013686.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01940876_CR30","unstructured":"R. E. Tarjan (private communication)."},{"key":"BF01940876_CR31","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"J. Vuillemin, A unifying look at data structures,Comm. ACM,23 (1980), 229\u2013239.","journal-title":"Comm. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940876.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01940876\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940876","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T12:33:54Z","timestamp":1557750834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01940876"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":31,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["BF01940876"],"URL":"https:\/\/doi.org\/10.1007\/bf01940876","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}