跳表
C++模板
cpp
class Skiplist {
private:
static constexpr int MAX_LEVEL = 32; // 最大层数
static constexpr double P_FACTOR = 0.25; // 概率因子
struct Node {
int val; // 节点值
vector<Node*> forward; // 每个节点在每一层的next节点
vector<int> span; // 每层的跨度
Node(int _val, int _maxlevel = MAX_LEVEL) : val(_val), forward(_maxlevel, nullptr), span(_maxlevel, 0) {}
};
Node* head;
int level,length;
mt19937 gen{random_device{}()};
uniform_real_distribution<double> dis;
int randomLevel() {
int lv = 1;
while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {
lv++;
}
return lv;
}
public:
Skiplist() : head(new Node(-1)), level(0), dis(0, 1) {}
Node* find_prev(int target) {
Node* cur = this->head;
for (int i = level - 1; i >= 0; i--) {
while (cur->forward[i] && cur->forward[i]->val < target) {
cur = cur->forward[i];
}
}
return cur;
}
Node* find_next(int target) {
Node* cur = this->head;
for (int i = level - 1; i >= 0; i--) {
while (cur->forward[i] && cur->forward[i]->val <= target) {
cur = cur->forward[i];
}
}
return cur->forward[0];
}
bool contains(int target) {
auto cur = find_prev(target);
cur = cur->forward[0];
if (cur && cur->val == target) return true;
return false;
}
void insert(int num) {
vector<Node*> update(MAX_LEVEL, head); // 存储每一层最接近num的节点
vector<int> rank(MAX_LEVEL, 0); // 存储每一层的排名
Node* cur = this->head;
for (int i = level - 1; i >= 0; i--) {
rank[i] = i == level - 1 ? 0 : rank[i + 1];
while (cur->forward[i] && cur->forward[i]->val < num) {
rank[i] += cur->span[i];
cur = cur->forward[i];
}
update[i] = cur;
}
int lv = randomLevel();
if(lv > level){
for(int i = level; i < lv; i++){
update[i]->span[i] = length;
}
level = lv;
}
Node* newNode = new Node(num, lv);
for (int i = 0; i < lv; i++) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
newNode->span[i] = rank[i] + update[i]->span[i] - rank[0];
update[i]->span[i] = rank[0] - rank[i] + 1;
}
for (int i = lv; i < level; i++) {
update[i]->span[i]++;
}
length++;
}
bool erase(int num) {
vector<Node*> update(MAX_LEVEL, nullptr);
Node* cur = this->head;
for (int i = level - 1; i >= 0; i--) {
while (cur->forward[i] && cur->forward[i]->val < num) {
cur = cur->forward[i];
}
update[i] = cur;
}
cur = cur->forward[0];
if (!cur || cur->val != num) return false;
for (int i = 0; i < level; i++) {
if (update[i]->forward[i] != cur) {
update[i]->span[i]--;
continue;
}
update[i]->span[i] += cur->span[i] - 1;
update[i]->forward[i] = cur->forward[i];
}
delete cur;
while (level > 1 && head->forward[level - 1] == nullptr) level--;
length--;
return true;
}
bool empty() {
return this->head->forward[0] == nullptr;
}
Node* kth(int k) {
Node* cur = this->head;
int rk = 0;
for (int i = level - 1; i >= 0; i--) {
while (cur->forward[i] && rk + cur->span[i] <= k) {
rk += cur->span[i];
cur = cur->forward[i];
}
}
return rk == k ? cur : nullptr;
}
int find_rank(int x){
Node* cur = this->head;
int rk = 0;
for(int i = level - 1; i >= 0; i--) {
while (cur->forward[i] && cur->forward[i]->val < x) {
rk += cur->span[i];
cur = cur->forward[i];
}
}
return rk + 1;
}
void print(){
if(empty()){
cout<<"[]\n";
return;
}
cout<<"[";
for(auto it=head->forward[0];it;it=it->forward[0]){
cout<<it->val;
if(it->forward[0])cout<<", ";
else cout<<"]\n";
}
}
};Python模板
py
MAX_LEVEL = 32
P_FACTOR = 0.25
def random_level() -> int:
lv = 1
while lv < MAX_LEVEL and random.random() < P_FACTOR:
lv += 1
return lv
class SkiplistNode:
__slots__ = 'val', 'forward'
def __init__(self, val: int, max_level=MAX_LEVEL):
self.val = val
self.forward = [None] * max_level
class Skiplist:
def __init__(self):
self.head = SkiplistNode(-1)
self.level = 0
def search(self, target: int) -> bool:
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 target 的元素
while curr.forward[i] and curr.forward[i].val < target:
curr = curr.forward[i]
curr = curr.forward[0]
# 检测当前元素的值是否等于 target
return curr is not None and curr.val == target
def add(self, num: int) -> None:
update = [self.head] * MAX_LEVEL
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 num 的元素
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
lv = random_level()
self.level = max(self.level, lv)
new_node = SkiplistNode(num, lv)
for i in range(lv):
# 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def erase(self, num: int) -> bool:
update = [None] * MAX_LEVEL
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 num 的元素
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
curr = curr.forward[0]
if curr is None or curr.val != num: # 值不存在
return False
for i in range(self.level):
if update[i].forward[i] != curr:
break
# 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳
update[i].forward[i] = curr.forward[i]
# 更新当前的 level
while self.level > 1 and self.head.forward[self.level - 1] is None:
self.level -= 1
return True