Question

Recall that a skiplist is a probabilistic data structure. Although the expected performance of a contains() call is O(log n), where n is the number of items in the list, the worst-case performance could be O(n). Draw a picture of an 8-element skiplist with worst-case performance, and explain how it got that way.

Answer 1

The deterministic skip list is a data structure which implements a dynamic ordered dictionary. From now on we shall abbreviate the deterministic skip list as a skip list. The truncated skip list is a skip list in which the height of the skip list is bounded from above by a constant.Let n∈N be the number of stored elements, m∈N be the number of unique stored elements, and Δ∈N be the link-distance, along unique elements, between a given stored element and the searched element. Let h∈N∪{∞} be the maximum height of the skip-list. The implementation of the deterministic skip-list in Pastel has the following properties: