A skip list

Build a skip list (lesson 6) of different keys, with these methods:

• add(key): put the key in. If it is already there, do nothing.
• contains(key): True if the key is there.
• remove(key): take the key out and return True; return False if it was not there.
• first_at_least(key): the smallest key that is at least key, or None if there is none.

s = SkipList()
s.add(10); s.add(20); s.add(30)
s.first_at_least(15)    # 20
s.first_at_least(31)    # None
s.remove(20)            # True

Keep the shape from the starter code: self.head is a node whose list next has one link per level, and each key’s node has a list next as long as its tower. One test walks your levels through head.next[0], head.next[1] and head.next[2]: level 0 must hold every key in order. Give each new key a tower: start at level 0, then flip a fair coin (random.random() < 0.5 means heads). Each heads adds one level, and the first tails stops. So about half the keys reach level 1, and about a quarter reach level 2. The bisect module is switched off.

Limits

• Up to 30,000 keys and about 50,000 operations; each should take O(log n) time on average.