13.2.1. SkipList Ideal¶

13.2.2. SkipList Reality¶

13.2.3. Analysis¶

• Best-case behavior is “balanced”: \(\Theta(\log n)\) (like a BST).

• Worst-case behavior: All nodes at the same level (regardless of what level): Effectively degenerates to a linked list (like a BST).

• The Big Idea:

  • SkipList behavior is not dependent on order of inserts/delete as is a BST.

  • SkipList performance is dictated entirely by random chance.

  • It is similar to what the BST cost would be if we randomized the input order. A huge improvement in expected performance!

13.2.4. Programming Principles¶

1. All container classes should be general.

2. Any container class’s initial state should be identical to its empty state.