4 ms·

Skip lists are randomized, right? Whereas B[-whatever] trees have guaranteed fast performance?

• adamansky 9y ago
  Yes. I suppose that probability to get such bad random distribution which makes SL search to be linear is similar to probability of moving all oxygen atoms to only one side of your room.
  • mehrdadn 9y ago
    Even against an adversary? (Asking because I don't know the data structure too well.)
    • hvidgaard 9y ago
      If the adversary find a bug in your system, such as not so random "random generator", then it can bring it down. But if the random generator is reasonable, then you can expect it to behave properly on all inputs.