1. SkipLists

1.1. SkipList Ideal

1.2. SkipList Reality

1.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!

1.4. Programming Principles

1. All container classes should be general.

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