The Design Skiplist problem asks you to implement a data structure called a Skiplist. A skiplist is a probabilistic data structure that allows for efficient search, insertion, and deletion—similar to a balanced tree, but using multiple linked lists layered on top of each other.
You must implement the following methods:
Skiplist(): Initializes the object.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 one occurrence of the value num from the Skiplist. Returns true if num existed and was removed, or false otherwise.Constraints:
5 * 10^4 calls to search, add, and erase combined.[-10^5, 10^5].When first approaching this problem, you might think to use a regular linked list or a balanced tree. A normal linked list would allow easy insertion and removal but searching would be slow (O(n)). A balanced tree (like AVL or Red-Black) is efficient but complex to implement.
The skiplist offers a clever compromise: it uses multiple levels of linked lists, each skipping more elements than the one below. This way, you can "skip" large portions of the list, making search, insert, and delete operations much faster on average. The skiplist achieves this efficiency through randomness, which keeps the structure balanced without complex rotations or rebalancing.
Our challenge is to design these layers, handle randomness, and ensure that all operations remain efficient, even with possible duplicates.
Let's break down how to build a skiplist step by step:
This approach ensures that all operations run in expected O(log n) time.
Let's walk through an example:
add(3), add(6), add(7), add(9), add(12).search(7):
true.erase(6):
true since 6 was found and erased.search(6) again, we will not find it, so we return false.Brute-force Approach:
The skiplist is efficient because the probability distribution of node levels ensures that most nodes appear in only a few levels, and only a few nodes appear at the highest levels.
The skiplist is a clever data structure that combines the simplicity of linked lists with the efficiency of balanced trees, using randomness to maintain balance. By layering linked lists and using probabilistic promotion, we achieve fast search, insert, and delete operations. This makes the skiplist both elegant and practical for scenarios where balanced trees are too complex or heavyweight.
import random
class Node:
def __init__(self, val, level):
self.val = val
self.forward = [None] * (level + 1)
class Skiplist:
MAX_LEVEL = 16
P = 0.5
def __init__(self):
self.head = Node(-1, Skiplist.MAX_LEVEL)
self.level = 0
def random_level(self):
lvl = 0
while random.random() < Skiplist.P and lvl < Skiplist.MAX_LEVEL:
lvl += 1
return lvl
def search(self, target: int) -> bool:
curr = self.head
for i in reversed(range(self.level + 1)):
while curr.forward[i] and curr.forward[i].val < target:
curr = curr.forward[i]
curr = curr.forward[0]
return curr is not None and curr.val == target
def add(self, num: int) -> None:
update = [None] * (Skiplist.MAX_LEVEL + 1)
curr = self.head
for i in reversed(range(self.level + 1)):
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
lvl = self.random_level()
if lvl > self.level:
for i in range(self.level + 1, lvl + 1):
update[i] = self.head
self.level = lvl
new_node = Node(num, lvl)
for i in range(lvl + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def erase(self, num: int) -> bool:
update = [None] * (Skiplist.MAX_LEVEL + 1)
curr = self.head
found = False
for i in reversed(range(self.level + 1)):
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
curr = curr.forward[0]
if curr and curr.val == num:
found = True
for i in range(self.level + 1):
if update[i].forward[i] != curr:
continue
update[i].forward[i] = curr.forward[i]
while self.level > 0 and self.head.forward[self.level] is None:
self.level -= 1
return found
#include <vector>
#include <cstdlib>
class Node {
public:
int val;
std::vector<Node*> forward;
Node(int v, int level) : val(v), forward(level + 1, nullptr) {}
};
class Skiplist {
static const int MAX_LEVEL = 16;
static constexpr float P = 0.5;
Node* head;
int level;
int randomLevel() {
int lvl = 0;
while ((rand() / double(RAND_MAX)) < P && lvl < MAX_LEVEL)
++lvl;
return lvl;
}
public:
Skiplist() {
head = new Node(-1, MAX_LEVEL);
level = 0;
}
bool search(int target) {
Node* curr = head;
for (int i = level; i >= 0; --i) {
while (curr->forward[i] && curr->forward[i]->val < target)
curr = curr->forward[i];
}
curr = curr->forward[0];
return curr && curr->val == target;
}
void add(int num) {
std::vector<Node*> update(MAX_LEVEL + 1, nullptr);
Node* curr = head;
for (int i = level; i >= 0; --i) {
while (curr->forward[i] && curr->forward[i]->val < num)
curr = curr->forward[i];
update[i] = curr;
}
int lvl = randomLevel();
if (lvl > level) {
for (int i = level + 1; i <= lvl; ++i)
update[i] = head;
level = lvl;
}
Node* newNode = new Node(num, lvl);
for (int i = 0; i <= lvl; ++i) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
bool erase(int num) {
std::vector<Node*> update(MAX_LEVEL + 1, nullptr);
Node* curr = head;
bool found = false;
for (int i = level; i >= 0; --i) {
while (curr->forward[i] && curr->forward[i]->val < num)
curr = curr->forward[i];
update[i] = curr;
}
curr = curr->forward[0];
if (curr && curr->val == num) {
found = true;
for (int i = 0; i <= level; ++i) {
if (update[i]->forward[i] != curr)
continue;
update[i]->forward[i] = curr->forward[i];
}
while (level > 0 && head->forward[level] == nullptr)
--level;
delete curr;
}
return found;
}
};
import java.util.*;
class Node {
int val;
Node[] forward;
Node(int val, int level) {
this.val = val;
this.forward = new Node[level + 1];
}
}
class Skiplist {
static final int MAX_LEVEL = 16;
static final double P = 0.5;
Node head;
int level;
Random rand;
public Skiplist() {
head = new Node(-1, MAX_LEVEL);
level = 0;
rand = new Random();
}
private int randomLevel() {
int lvl = 0;
while (rand.nextDouble() < P && lvl < MAX_LEVEL)
lvl++;
return lvl;
}
public boolean search(int target) {
Node curr = head;
for (int i = level; i >= 0; i--) {
while (curr.forward[i] != null && curr.forward[i].val < target) {
curr = curr.forward[i];
}
}
curr = curr.forward[0];
return curr != null && curr.val == target;
}
public void add(int num) {
Node[] update = new Node[MAX_LEVEL + 1];
Node curr = head;
for (int i = level; i >= 0; i--) {
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
int lvl = randomLevel();
if (lvl > level) {
for (int i = level + 1; i <= lvl; i++)
update[i] = head;
level = lvl;
}
Node newNode = new Node(num, lvl);
for (int i = 0; i <= lvl; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
public boolean erase(int num) {
Node[] update = new Node[MAX_LEVEL + 1];
Node curr = head;
boolean found = false;
for (int i = level; i >= 0; i--) {
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
curr = curr.forward[0];
if (curr != null && curr.val == num) {
found = true;
for (int i = 0; i <= level; i++) {
if (update[i].forward[i] != curr)
continue;
update[i].forward[i] = curr.forward[i];
}
while (level > 0 && head.forward[level] == null)
level--;
}
return found;
}
}
class Node {
constructor(val, level) {
this.val = val;
this.forward = new Array(level + 1).fill(null);
}
}
class Skiplist {
constructor() {
this.MAX_LEVEL = 16;
this.P = 0.5;
this.head = new Node(-1, this.MAX_LEVEL);
this.level = 0;
}
randomLevel() {
let lvl = 0;
while (Math.random() < this.P && lvl < this.MAX_LEVEL)
lvl++;
return lvl;
}
search(target) {
let curr = this.head;
for (let i = this.level; i >= 0; i--) {
while (curr.forward[i] && curr.forward[i].val < target) {
curr = curr.forward[i];
}
}
curr = curr.forward[0];
return curr !== null && curr.val === target;
}
add(num) {
let update = new Array(this.MAX_LEVEL + 1);
let curr = this.head;
for (let i = this.level; i >= 0; i--) {
while (curr.forward[i] && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
let lvl = this.randomLevel();
if (lvl > this.level) {
for (let i = this.level + 1; i <= lvl; i++)
update[i] = this.head;
this.level = lvl;
}
let newNode = new Node(num, lvl);
for (let i = 0; i <= lvl; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
erase(num) {
let update = new Array(this.MAX_LEVEL + 1);
let curr = this.head;
let found = false;
for (let i = this.level; i >= 0; i--) {
while (curr.forward[i] && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
curr = curr.forward[0];
if (curr && curr.val === num) {
found = true;
for (let i = 0; i <= this.level; i++) {
if (update[i].forward[i] !== curr)
continue;
update[i].forward[i] = curr.forward[i];
}
while (this.level > 0 && this.head.forward[this.level] === null)
this.level--;
}
return found;
}
}