经典算法实现之跳表

定义

是一种可以代替平衡树的数据结构，可以看做是并联的有序链表。跳跃表通过概率保证平衡，而平衡树采用严格的旋转来保证平衡，因此跳跃表比较容易实现，而且相比平衡树有着较高的运行效率。下面实现的最大level为16.

操作

• 插入

  

• 查找

  

• 删除

  

这里是一个单向链表，其实也可以维护一个双向的链表

实现

#include <iostream>
#include <vector>
#include <random>
#include <climits>

const int MAX_LEVEL = 16; // 最大层数

// 跳表节点
struct SkipListNode {
    int value;
    std::vector<SkipListNode*> next;

    SkipListNode(int val, int level) : value(val), next(level, nullptr) {}
};

class SkipList {
public:
    SkipList() {
        head = new SkipListNode(INT_MIN, MAX_LEVEL);
        tail = new SkipListNode(INT_MAX, MAX_LEVEL);
        for (int i = 0; i < MAX_LEVEL; ++i) {
            head->next[i] = tail;
        }
    }

    ~SkipList() {
        SkipListNode* curr = head;
        while (curr != nullptr) {
            SkipListNode* temp = curr;
            curr = curr->next[0];
            delete temp;
        }
    }

    // 插入节点
    void insert(int value) {
        std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);
        SkipListNode* curr = head;
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (curr->next[i]->value < value) {
                curr = curr->next[i];
            }
            update[i] = curr;
        }
        curr = curr->next[0];
        if (curr->value == value) {
            return; // 节点已存在
        }
        int level = randomLevel();
        SkipListNode* newNode = new SkipListNode(value, level);
        for (int i = 0; i < level; ++i) {
            newNode->next[i] = update[i]->next[i];
            update[i]->next[i] = newNode;
        }
    }

    // 删除节点
    void remove(int value) {
        std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);
        SkipListNode* curr = head;
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (curr->next[i]->value < value) {
                curr = curr->next[i];
            }
            update[i] = curr;
        }
        curr = curr->next[0];
        if (curr->value != value) {
            return; // 节点不存在
        }
        for (int i = 0; i < curr->next.size()&& i < update.size(); ++i) {
            if (update[i]->next[i] != curr) {
                break;
            }
            update[i]->next[i] = curr->next[i];
        }
        delete curr;
    }

    // 查找节点
    bool search(int value) {
        SkipListNode* curr = head;
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            while (curr->next[i]->value < value) {
                curr = curr->next[i];
            }
        }
        curr = curr->next[0];
        return curr->value == value;
    }

    // 打印跳表
    void print() {
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            SkipListNode* curr = head->next[i];
            std::cout << "Level " << i << ": ";
            while (curr != tail) {
                std::cout << curr->value << " ";
                curr = curr->next[i];
            }
            std::cout << std::endl;
        }
    }

private:
    SkipListNode* head;
    SkipListNode* tail;

    // 随机生成节点层数
    int randomLevel() {
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, MAX_LEVEL);
        return dis(gen);
    }
};

int main() {
    SkipList skipList;
    skipList.insert(3);
    skipList.insert(1);
    skipList.insert(5);
    skipList.insert(2);
    skipList.insert(4);
    skipList.print();

    std::cout << "Search 3: " << (skipList.search(3) ? "Found" : "Not Found") << std::endl;
    std::cout << "Search 6: " << (skipList.search(6) ? "Found" : "Not Found") << std::endl;

    skipList.remove(2);
    skipList.remove(4);
    skipList.print();

    return 0;
}