Biased Skip Lists
We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight wi, 1 Â¿ i Â¿ n, the time to access item i is O(1 + log W/wi), where W = Â¿i = 1nwi; the data structure is dynamic. We present deterministic and randomized variations, which are nearly identical; the deterministic one simply ensures the balance condition that the randomized one achieves probabilistically. We use the same method to analyze both.