Adaptive heuristics for binary search trees and constant linkage cost
Tony W. Lai, Derick Wood · 1991
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\\Gammaast 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\\Gamma log n f(n) log(log n=f(n)) ) against an adaptive online adversary. In our investigation of upper bounds we present four adaptive heuristics: ffl A randomized, worst-case-CLC heuristic (R2P) whose expected search time is within a constant factor of the search time using an optimal tree; that is, it is statically competitive ffl A randomized, expecte...