{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T01:27:36Z","timestamp":1633397256168},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1998,3]]},"abstract":"\n In this paper, we present randomized algorithms over binary search trees such that: (a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tree; (b) the deletion of any key from a random binary search tree results in a random binary search tree; (c) the random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we can support accesses by rank without additional storage requirements or modification of the data structures; and (d) the cost of any elementary operation, measured as the number of visited nodes, is the same as the expected cost of its standard deterministic counterpart; hence, all search and update operations have guaranteed expected cost O(log\n n<\/jats:italic>\n ), but now irrespective of any assumption on the input distribution.\n <\/jats:p>","DOI":"10.1145\/274787.274812","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"288-323","source":"Crossref","is-referenced-by-count":45,"title":["Randomized binary search trees"],"prefix":"10.1145","volume":"45","author":[{"given":"Conrado","family":"Mart\u00ednez","sequence":"first","affiliation":[{"name":"Univ. Polit\u00e9cnica de Catalunya, Barcelona, Spain"}]},{"given":"Salvador","family":"Roura","sequence":"additional","affiliation":[{"name":"Univ. Polit\u00e9cnica de Catalunya, Barcelona, Spain"}]}],"member":"320","reference":[{"issue":"2","key":"e_1_2_1_1_1","first-page":"263","article-title":"An algorithm for the organization of information","volume":"146","author":"ADEL'SON-VEL'SKII G.","year":"1962","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322094"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"540","volume-title":"Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE","author":"ARAGON C. R.","year":"1989","DOI":"10.1109\/SFCS.1989.63531"},{"key":"e_1_2_1_5_1","first-page":"205","volume-title":"Proceedings of the 17th ACM Symposium on the Theory of Computing (STOC) (Providence, R.I., May 6-8). ACM","author":"CULBERSON J.","year":"1985"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"EPPINGER J. L. 1983. An empirical study of insertion and deletion in binary search trees. Commun. ACM 26 9 (Sept.) 663-669. 10.1145\/358172.358183 EPPINGER J. L. 1983. An empirical study of insertion and deletion in binary search trees. Commun. ACM 26 9 (Sept.) 663-669. 10.1145\/358172.358183","DOI":"10.1145\/358172.358183"},{"key":"e_1_2_1_7_1","volume-title":"An Introduction to Probability Theory and its Applications","author":"FELLER W."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1093\/comjnl\/26.2.106","article-title":"Height-ratio-balanced trees","volume":"26","author":"GONNET G.","year":"1983","journal-title":"Comput. J."},{"key":"e_1_2_1_9_1","volume-title":"Handbook of Algorithms and Data Structures-In Pascal and C","author":"GONNET G. H.","edition":"2"},{"key":"e_1_2_1_10_1","first-page":"8","volume-title":"Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (Oct.). IEEE","author":"GUIBAS L.","year":"1978"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321108"},{"issue":"3","key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0022-0000(78)90020-X","article-title":"A trivial algorithm whose analysis isn't","volume":"16","author":"JONASSEN A.","year":"1978","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"KNUTH D.E.","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1109\/TSE.1977.231160","article-title":"Deletions that preserve randomness","volume":"3","author":"KNUTH D.","year":"1977","journal-title":"IEEE Trans. Softw. Eng."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","volume-title":"The Design and Analysis of Algorithms","author":"KOZEN D.C.","DOI":"10.1007\/978-1-4612-4400-4"},{"key":"e_1_2_1_17_1","volume-title":"Evolution of Random Search Trees","author":"MAHMOUD H.M."},{"issue":"1","key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0202005","article-title":"Binary search trees of bounded balance","volume":"2","author":"NIEVERGELT J.","year":"1973","journal-title":"SIAM J. Cornput."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_21_1","volume-title":"Randomized Algorithms","author":"RAGHAVAN P."},{"key":"e_1_2_1_22_1","first-page":"91","volume-title":"Proceedings of the 4th European Symposium on Algorithms (ESA), J. Dfaz and M. Serna, eds. Lecture Notes in Computer Science","volume":"1136","author":"ROURA S.","year":"1996"},{"key":"e_1_2_1_23_1","volume-title":"Algorithms","author":"SEDOEWICK R.","edition":"2"},{"key":"e_1_2_1_24_1","volume-title":"An Introduction to the Analysis of Algorithms","author":"SEDGEWICK R."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/BF01940876","article-title":"Randomized search trees","volume":"16","author":"SEIDEL R.","year":"1996","journal-title":"Algorithmica"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"STEPHENSON C.J. 1980. A method for constructing binary search trees by making insertions at the root. Int. J. Comput. Inf. Sci. 9 1. STEPHENSON C.J. 1980. A method for constructing binary search trees by making insertions at the root. Int. J. Comput. Inf. Sci. 9 1.","DOI":"10.1007\/BF00995807"},{"key":"e_1_2_1_27_1","volume-title":"Handbook of Theoretical Computer Science, chap. 9","author":"VITTER J. S."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/274787.274812","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T11:03:34Z","timestamp":1614596614000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,3]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,3]]}},"alternative-id":["10.1145\/274787.274812"],"URL":"http:\/\/dx.doi.org\/10.1145\/274787.274812","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1998,3]]}}}