1206. Design Skiplist Hard

1/**
2 * [1206] Design Skiplist
3 *
4 * Design a Skiplist without using any built-in libraries.
5 * 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.
6 * 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:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2019/09/27/1506_skiplist.gif" style="width: 500px; height: 173px;" /><br />
8 * <small>Artyom Kalinin [CC BY-SA 3.0], via <a href="https://commons.wikimedia.org/wiki/File:Skip_list_add_element-en.gif" target="_blank" title="Artyom Kalinin [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons">Wikimedia Commons</a></small>
9 * 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).
10 * See more about Skiplist: <a href="https://en.wikipedia.org/wiki/Skip_list" target="_blank">https://en.wikipedia.org/wiki/Skip_list</a>
11 * Implement the Skiplist class:
12 * 
13 * 	Skiplist() Initializes the object of the skiplist.
14 * 	bool search(int target) Returns true if the integer target exists in the Skiplist or false otherwise.
15 * 	void add(int num) Inserts the value num into the SkipList.
16 * 	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.
17 * 
18 * Note that duplicates may exist in the Skiplist, your code needs to handle this situation.
19 *  
20 * Example 1:
21 * 
22 * Input
23 * ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
24 * [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
25 * Output
26 * [null, null, null, null, false, null, true, false, true, false]
27 * Explanation
28 * Skiplist skiplist = new Skiplist();
29 * skiplist.add(1);
30 * skiplist.add(2);
31 * skiplist.add(3);
32 * skiplist.search(0); // return False
33 * skiplist.add(4);
34 * skiplist.search(1); // return True
35 * skiplist.erase(0);  // return False, 0 is not in skiplist.
36 * skiplist.erase(1);  // return True
37 * skiplist.search(1); // return False, 1 has already been erased.
38 *  
39 * Constraints:
40 * 
41 * 	0 <= num, target <= 2 * 10^4
42 * 	At most 5 * 10^4 calls will be made to search, add, and erase.
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/design-skiplist/
48// discuss: https://leetcode.com/problems/design-skiplist/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52struct Skiplist {
53        false
54    }
55
56
57/** 
58 * `&self` means the method takes an immutable reference.
59 * If you need a mutable reference, change it to `&mut self` instead.
60 */
61impl Skiplist {
62
63    fn new() -> Self {
64        
65    }
66    
67    fn search(&self, target: i32) -> bool {
68        
69    }
70    
71    fn add(&self, num: i32) {
72        
73    }
74    
75    fn erase(&self, num: i32) -> bool {
76        
77    }
78}
79
80/**
81 * Your Skiplist object will be instantiated and called as such:
82 * let obj = Skiplist::new();
83 * let ret_1: bool = obj.search(target);
84 * obj.add(num);
85 * let ret_3: bool = obj.erase(num);
86 */
87
88// submission codes end
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn test_1206() {
96    }
97}
98