Solution: Skiplists

Task

Here is the solution that implements the find(x) method in a SkiplistSSet sometimes performs redundant comparisons; these occur when x is compared to the same value more than once. They can occur when, for some node, u, u.next[r] = u.next[r − 1]. Modify the find(x) so that these redundant comparisons are avoided.

Solution

The find_pred_node(self, x) method in the SkiplistSSet() class is a helper function used by the find() and add() methods. It searches for the node that precedes the value x in the skiplist.