{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:23Z","timestamp":1787337503810,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We present lower and upper bounds on adaptive heuristics for maintaining binary search trees using a constant number of link or pointer changes for each operation (constant linkage cost (CLC)). We show that no adaptive heuristic with an amortized linkage cost of o(log n) can be competitive. In particular, we show that any heuristic that performs f(n)=o(log n) promotions (rotations) amortized over each access has a competitive ratio of at least $\\Omega(\\log n\/f(n))$ against an oblivious adversary, and any heuristic that performs f(n)=o(log n) pointer changes amortized over each access has a competitive ratio of at least $\\Omega(\\frac{\\log n}{f(n)\\log(\\log n\/f(n))})$ against an adaptive online adversary.<\/jats:p>\n                  <jats:p>In our investigation of upper bounds we present four adaptive heuristics: a randomized, worst-case-CLC heuristic randomized two-promotion (R2P) whose expected search time is within a constant factor of the search time using an optimal tree; that is, it is statically competitive against an oblivious adversary; a randomized, expected-CLC heuristic (locally optimized randomized partial splay (LORPS)) that has O(log n) expected-amortized update time and is statically competitive against an oblivious adversary; a deterministic, amortized-CLC heuristic (locally optimized partial splay (LOPS)) that has O(log n) amortized update time and is statically competitive against an adaptive adversary; a practical, randomized heuristic (randomized partial splay (RPS)) that is not CLC but has performance bounds comparable with those of the splay heuristic of Sleator and Tarjan; it is statically competitive against an adaptive adversary.<\/jats:p>\n                  <jats:p>The randomized heuristics use only constant extra space, whereas the deterministic heuristic uses O(n) extra space.<\/jats:p>","DOI":"10.1137\/s0097539793250329","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1564-1591","source":"Crossref","is-referenced-by-count":4,"title":["Adaptive Heuristics for Binary Search Trees and Constant Linkage Cost"],"prefix":"10.1137","volume":"27","author":[{"given":"Tony W.","family":"Lai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Derick","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","first-page":"1259","volume":"3","author":"Adel\u2019son\u2010Vel\u2019skii G. M.","year":"1962","journal-title":"Soviet Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322094"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"C. R. Aragon and R. G. Seidel,\n                      Randomized search trees\n                      , in Proc. 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 540\u2013545.","DOI":"10.1109\/SFCS.1989.63531"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230403"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Ben\u2010David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson,\n                      On the power of randomization in online algorithms\n                      , in Proc. 22th Annual ACM Symposium on Theory of Computing, 1990, pp. 379\u2013386.","DOI":"10.1145\/100216.100268"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/3341.3349"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0208007"},{"key":"R9","unstructured":"R. P. Cheetham, B. J. Oommen, and D. T. H. Ng,\n                      Adaptive structuring of binary search trees using conditional rotations\n                      , Tech. report SCS\u2010TR\u2010126, Carleton University, Ottawa, Canada, October 1987."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. Cole,\n                      On the dynamic finger conjecture for splay trees (extended abstract)\n                      , in Proc. 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 8\u201317.","DOI":"10.1145\/100216.100218"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Leo Guibas, Robert Sedgewick, A dichromatic framework for balanced trees, IEEE, Long Beach, Calif., 1978, 8\u20132180e:68168","DOI":"10.1109\/SFCS.1978.3"},{"key":"R12","unstructured":"T. W. H. Lai,\n                      Efficient Maintenance of Binary Search Trees\n                      , Ph.D. thesis, University of Waterloo, 1990."},{"key":"R13","unstructured":"Tony Lai, Derick Wood, Adaptive heuristics for binary search trees and constant linkage cost, ACM, New York, 1991, 72\u2013771095821"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0208014"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054192000243"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1147\/rd.386.0683"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. Sherk,\n                      Self\u2010adjusting k\u2010ary Search Trees and Self\u2010adjusting Balanced Search Trees\n                      , Tech. report 234\/90, University of Toronto, February 1990.","DOI":"10.1007\/3-540-51542-9_32"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675973"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0218004"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793250329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:12Z","timestamp":1787336052000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793250329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":22,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793250329"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793250329","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}