Dynamic binary search

We consider search trees under time-varying access probabi-t lities. Let S = {B 1,...,Bn} and let Pi be the number of accesses to object Bi up to time t, wt = L pi. We intro-duce D-trees with the following properties. 1) A search for X = Bi at time t takes time O(log wt/pi). 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.-1-I