{x}
blog image

Design Skiplist

Design a Skiplist without using any built-in libraries.

A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists.

For example, we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:


Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list

Implement the Skiplist class:

  • Skiplist() Initializes the object of the skiplist.
  • bool search(int target) Returns true if the integer target exists in the Skiplist or false otherwise.
  • void add(int num) Inserts the value num into the SkipList.
  • bool erase(int num) Removes the value num from the Skiplist and returns true. If num does not exist in the Skiplist, do nothing and return false. If there exist multiple num values, removing any one of them is fine.

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

 

Example 1:

Input
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
Output
[null, null, null, null, false, null, true, false, true, false]

Explanation
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // return False
skiplist.add(4);
skiplist.search(1); // return True
skiplist.erase(0);  // return False, 0 is not in skiplist.
skiplist.erase(1);  // return True
skiplist.search(1); // return False, 1 has already been erased.

 

Constraints:

  • 0 <= num, target <= 2 * 104
  • At most 5 * 104 calls will be made to search, add, and erase.

Solution Explanation for Design Skiplist

This problem requires designing a Skiplist data structure from scratch. A Skiplist is a probabilistic data structure that allows for efficient searching, insertion, and deletion of elements, with an average time complexity of O(log n) for each operation.

Core Concepts:

  • Levels: A Skiplist consists of multiple sorted linked lists layered on top of each other. The bottom-most layer contains all elements, while higher layers contain a progressively smaller subset of elements. This layered structure allows for faster search operations by skipping over large portions of the list.

  • Probabilistic Promotion: When inserting an element, its inclusion in higher layers is determined probabilistically. This ensures that, on average, the height of the Skiplist remains logarithmic with respect to the number of elements.

  • Node Structure: Each node in the Skiplist has a value and an array of pointers (next), one for each level it participates in. The pointers point to the next node in that level's linked list.

Algorithm:

  1. Skiplist(): The constructor initializes the Skiplist with a head node and sets the initial level to 0.

  2. search(target): This function iterates through the Skiplist levels from top to bottom. At each level, it finds the node with the largest value less than or equal to the target using findClosest(). If a node with the target value is found at any level, it returns true; otherwise, it returns false.

  3. add(num): This function first determines the random level for the new node using randomLevel(). Then, it iterates through the levels from top to bottom. At each level, it finds the appropriate insertion point using findClosest() and inserts the new node into the list at that point.

  4. erase(num): This function iterates through the levels from top to bottom, removing any instances of the num value from each level's linked list. If the number is not found, it returns false. After removal, it adjusts the level to reflect the updated structure of the Skiplist.

  5. findClosest(curr, level, target): This helper function finds the node in a given level that has the largest value less than or equal to the target.

  6. randomLevel(): This helper function determines the random level of a new node based on the probability p. It simulates a geometric distribution.

Time Complexity Analysis:

  • search(target): O(log n) on average. The number of levels is logarithmic in the number of elements, and the search at each level takes constant time on average.

  • add(num): O(log n) on average. Similar to searching, the number of levels and operations at each level are logarithmic.

  • erase(num): O(log n) on average. The removal process has a similar time complexity to insertion.

Space Complexity Analysis: O(n) - The space used is proportional to the number of nodes in the Skiplist.

Code Examples (Python, Java, C++, Go):

The code examples provided in the original response demonstrate the implementation of the Skiplist class in four different programming languages (Python, Java, C++, Go). Each implementation follows the algorithm described above and includes the necessary helper functions. The choice of language depends on personal preference and project requirements. The core logic remains consistent across all languages.