{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:12Z","timestamp":1787340552151,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>We consider the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. We describe two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. We present and analyze efficient update algorithms for biased search trees. We list several applications of such trees.<\/jats:p>","DOI":"10.1137\/0214041","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"545-568","source":"Crossref","is-referenced-by-count":92,"title":["Biased Search Trees"],"prefix":"10.1137","volume":"14","author":[{"given":"Samuel W.","family":"Bent","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel D.","family":"Sleator","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","volume-title":"Informantion theory and coding","author":"Abramson Norman","year":"1963"},{"key":"R2","first-page":"1259","volume":"3","author":"Adelson-Velskii G. M.","year":"1962","journal-title":"Soviet Math. Dokl."},{"key":"R3","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R4","first-page":"467","volume":"44","author":"Baer J. L.","year":"1975","journal-title":"Proc. AFIPS Nat. Comp. Conf."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289509"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"S. W. Bent, D. D. Sleator, R. E. Tarjan,  Biased  2- 3 trees,  Proc. Twenty-First Annual IEEE Symposium on Foundations of Computer Science,  1980,  248\u2013254","DOI":"10.1109\/SFCS.1980.15"},{"key":"R8","unstructured":"S. W. Bent, Ph.D. Thesis,  Dynamic weighted data structures, Computer Science Dept., Stanford Univ., Stanford, CA,  1982"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1983.tb03469.x"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Michael L. Fredman,  Two applications of a probabilistic search technique: sorting  $X+Y$ and building balanced search trees,  Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N. M., 1975), Assoc. Comput. Mach., New York,  1975,  240\u2013244 55:48120391.68035","DOI":"10.1145\/800116.803774"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0206045"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-67838-7_35"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017305"},{"key":"R15","volume-title":"Combinatorial algorithms","author":"Hu T. C.","year":"1982"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0137015"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0121057"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"},{"key":"R20","volume-title":"The Art of Computer Programming, Vol. 3, Sorting and Searching","author":"Knuth D. E.","year":"1975"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90143-5"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10856-4_108"},{"key":"R23","author":"Kriegel H. P.","year":"1981","journal-title":"Proc. CISS"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264563"},{"key":"R25","unstructured":"K. Mehlhorn,  Arbitrary weight changes in dynamic trees, Bericht, 78\/04, Angewandte Mathematik and Informatik, Universitat des Saarlandes,  1978"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0208014"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Daniel D. Sleator, Robert Endre Tarjan,  Self-adjusting binary trees,  Proc. Fifteenth Annual ACM Symposium on Theory of Computing,  1983,  235\u2013245","DOI":"10.1145\/800061.808752"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289093"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"F. F. Yao,  Efficient dynamic programming using quadrangle inequalities,  Proc. Twelfth Annual ACM Symposium on Theory of Computing,  1980,  429\u2013435","DOI":"10.1145\/800141.804691"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:05Z","timestamp":1787337545000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214041"],"URL":"https:\/\/doi.org\/10.1137\/0214041","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}