Dynamic Binary Search
Kurt Mehlhorn · Lecture notes in computer science · 1977
We consider search trees under time-varying access probabilities. Let $S = \{ B_1 , \cdots ,B_n \} $ and let $p_i^t $ be the number of accesses to object $B_i $ up to time t, $W^t = \sum {p_i^t } $. We introduce D-trees with the following properties. 1) A search for $X = B_i $ at time t takes time $O(\log W^t /p_i^t )$. This is nearly optimal. 2) Update time after a search is at most proportional to search time, i.e. the overhead for administration is small.