c++如何实现跳表（skiplist）

跳表（skiplist）是一种随机化的数据结构，它允许快速查询一个有序序列中的元素，并且它的插入和删除操作具有相对较低的时间复杂度。下面我们将介绍如何使用C++实现跳表。

基本思路

跳表的基本思路是建立多层索引，即使用多级指针来跳过一些元素，在链表的基础上进行优化。第一层是原始链表，其他层则是链表的子集。每一层的元素数量越来越少，随着层数的增加，跳过元素的能力也增加，查询、插入、删除等操作的时间复杂度也得到了优化。

实现步骤

定义跳表结构体

struct SkipNode {
    int key;            
    int value;          
    vector<SkipNode*> forward;  // 前向指针数组
    SkipNode(int k, int v, int level): key(k), value(v) {
        forward.resize(level, nullptr);
    }
};

定义跳表类

class SkipList {
public:
    SkipList(double p, int maxLevel);
    ~SkipList();   
    bool find(int key, int& value);
    void insert(int key, int value);
    bool remove(int key);
    void print();
private:
    int randomLevel();
    SkipNode* createNode(int key, int value, int level);
    void deleteNode(SkipNode* node);
private:
    double probability_;   // 控制每一层索引出现的概率
    int maxLevel_;         // 跳表的最大层数
    SkipNode* head_;       // 头节点
};

实现跳表构造函数

SkipList::SkipList(double p, int maxLevel): probability_(p), maxLevel_(maxLevel) {
    head_ = createNode(-1, -1, maxLevel_);  // 初始化头节点
}

实现随机层数函数

int SkipList::randomLevel() {
    int level = 1;
    while (rand() % 2 == 0 && level < maxLevel_) {
        level++;
    }
    return level;
}

实现新节点创建函数

SkipNode* SkipList::createNode(int key, int value, int level) {
    return new SkipNode(key, value, level);
}

实现节点删除函数

void SkipList::deleteNode(SkipNode* node) {
    if (node != nullptr) {
        for (int i = 0; i < node->forward.size(); i++) {
            delete node->forward[i];
        }
        delete node;
    }
}

实现插入操作

void SkipList::insert(int key, int value) {
    SkipNode* cur = head_;
    vector<SkipNode*> update(maxLevel_, nullptr);
    for (int i = maxLevel_ - 1; i >= 0; i--) {
        while (cur->forward[i] != nullptr && cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
        update[i] = cur;
    }
    cur = cur->forward[0];
    if (cur == nullptr || cur->key != key) {
        int level = randomLevel();
        SkipNode* node = createNode(key, value, level);
        for (int i = 0; i < level; i++) {
            node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = node;
        }
    }
}

实现查找操作

bool SkipList::find(int key, int& value) {
    SkipNode* cur = head_;
    for (int i = maxLevel_ - 1; i >= 0; i--) {
        while (cur->forward[i] != nullptr && cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
    }
    cur = cur->forward[0];
    if (cur != nullptr && cur->key == key) {
        value = cur->value;
        return true;
    }
    return false;
}

实现删除操作

bool SkipList::remove(int key) {
    SkipNode* cur = head_;
    vector<SkipNode*> update(maxLevel_, nullptr);
    for (int i = maxLevel_ - 1; i >= 0; i--) {
        while (cur->forward[i] != nullptr && cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
        update[i] = cur;
    }
    cur = cur->forward[0];
    if (cur != nullptr && cur->key == key) {
        for (int i = 0; i < cur->forward.size(); i++) {
            update[i]->forward[i] = cur->forward[i];
        }
        deleteNode(cur);
        return true;
    }
    return false;
}

实现打印操作

void SkipList::print() {
    for (int i = maxLevel_ - 1; i >= 0; i--) {
        SkipNode* cur = head_;
        cout << "Level " << i << ": ";
        while (cur->forward[i] != nullptr) {
            cout << "(" << cur->forward[i]->key << "," << cur->forward[i]->value << ") ";
            cur = cur->forward[i];
        }
        cout << endl;
    }
}

示例说明

示例一：插入操作

SkipList sl(0.5, 5);
for (int i = 0; i < 20; i++) {
    sl.insert(i, i * i);
}
sl.print();

输出结果：

Level 4: (16,256) 
Level 3: (2,4) (4,16) (6,36) (7,49) (8,64) (9,81) (11,121) (12,144) (13,169) (15,225) (16,256) (17,289) (18,324) 
Level 2: (2,4) (4,16) (6,36) (7,49) (8,64) (9,81) (11,121) (12,144) (13,169) (15,225) (16,256) (17,289) (18,324) 
Level 1: (2,4) (4,16) (6,36) (7,49) (8,64) (9,81) (11,121) (12,144) (13,169) (15,225) (16,256) (17,289) (18,324) 
Level 0: (0,0) (2,4) (4,16) (6,36) (7,49) (8,64) (9,81) (10,100) (11,121) (12,144) (13,169) (14,196) (15,225) (16,256) (17,289) (18,324) (19,361)

其中，我们先创建了一个最大层数为5，索引出现概率为0.5的跳表对象sl，然后插入20个元素，最后调用print函数打印跳表的状态。可以看到，print函数打印出了跳表中每一层的所有元素。

示例二：删除操作

SkipList sl(0.5, 5);
for (int i = 0; i < 20; i++) {
    sl.insert(i, i * i);
}
sl.remove(8);
sl.remove(6);
sl.remove(12);
sl.print();