Skip list without randomization?

Question

So I read a bit about skip lists and am currently implementing one. But there is one thing I didn't really got so far. Why are skip lists randomized? In all sources I found skip list used a random number to decide at what level the item will be inserted. Couldn't the optimum be calculated? Or couldn't you just say "every fourth item" should be inserted at the level above?

Answer 1

Skip lists can be constructed deterministically, for instance to minimize the amortized access cost. However, for any deterministic construction method the set of higher-level list entries is always known, so it's easy to construct a "hostile" set of delete operations that will degenerate performance back to O(n). With randomized construction there's still a set of worst-case deletes, but for any sizable list the likelihood of finding that worst-case delete sequence by sheer chance is vanishingly small.