跳表

算法概述

【跳表】(Skip List)是一种随机化的数据结构，它使用多层链表实现，支持快速的查找、插入和删除操作，平均时间复杂度为O(log n)。跳表是有序链表的一种优化版本，通过随机建立"快速通道"，使得搜索过程可以跳过许多元素，从而达到对数级别的时间复杂度。

跳表的核心思想是：通过在有序链表的基础上添加多级索引，形成一种"多层链表"结构，从而在保持链表插入删除操作简单性的同时，也获得了类似二分查找的高效搜索能力。

基本结构

跳表由多层有序链表组成：

• 最底层（Level 0）是一个包含所有元素的有序链表
• 上层（Level 1, 2, 3, ...）是下层链表的子集，作为索引加速查找
• 每一层的元素个数大约是下一层的1/2（通过随机决定）

跳表的节点结构

struct SkipListNode {
    int key;               // 节点值
    int value;             // 关联值（如果需要）
    vector<SkipListNode*> forward;  // 指向各层的下一个节点

    SkipListNode(int k, int v, int level) : key(k), value(v) {
        forward.resize(level + 1, nullptr);
    }
};

跳表的基本操作

跳表构造与初始化

class SkipList {
private:
    int maxLevel;          // 最大层数
    float probability;     // 上升到下一层的概率
    SkipListNode* header;  // 头节点
    int level;             // 当前最高层数

public:
    SkipList(int maxLevel = 16, float p = 0.5) {
        this->maxLevel = maxLevel;
        probability = p;
        level = 0;
        // 头节点不存储实际元素，仅作为入口
        header = new SkipListNode(-1, -1, maxLevel);
    }

    // 其他方法...
};

随机层数生成

跳表的一个关键操作是决定新插入节点的层数，这通常使用随机化方法：

int SkipList::randomLevel() {
    int lvl = 0;
    // 以概率p(通常为0.5)向上生成层数，直到达到最大层数或随机数不满足条件
    while (rand() < probability * RAND_MAX && lvl < maxLevel) {
        lvl++;
    }
    return lvl;
}

查找操作

跳表的查找从最高层开始，当遇到大于目标的节点时下降一层，否则在当前层向前移动：

SkipListNode* SkipList::search(int key) {
    SkipListNode* current = header;

    // 从最高层开始查找
    for (int i = level; i >= 0; i--) {
        // 在当前层向前移动，直到下一个节点大于等于目标
        while (current->forward[i] && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }

    // 已经到达最底层，检查下一个节点是否为目标
    current = current->forward[0];

    // 如果找到目标节点，返回它
    if (current && current->key == key) {
        return current;
    }

    // 未找到目标节点
    return nullptr;
}

插入操作

插入操作需要先找到合适的位置，然后随机决定新节点的层数，并更新相应的指针：

void SkipList::insert(int key, int value) {
    // 记录每一层的前驱节点
    vector<SkipListNode*> update(maxLevel + 1, nullptr);
    SkipListNode* current = header;

    // 从最高层开始查找插入位置的前驱节点
    for (int i = level; i >= 0; i--) {
        while (current->forward[i] && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    // 移至最底层的下一个节点
    current = current->forward[0];

    // 键已存在，更新值
    if (current && current->key == key) {
        current->value = value;
        return;
    }

    // 生成随机层数
    int newLevel = randomLevel();

    // 如果新层数高于当前最高层，更新header的forward指针
    if (newLevel > level) {
        for (int i = level + 1; i <= newLevel; i++) {
            update[i] = header;
        }
        level = newLevel;
    }

    // 创建新节点
    SkipListNode* newNode = new SkipListNode(key, value, newLevel);

    // 插入新节点，更新指针
    for (int i = 0; i <= newLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

删除操作

删除操作先找到目标节点，然后更新所有指向它的指针：

bool SkipList::remove(int key) {
    // 记录每一层的前驱节点
    vector<SkipListNode*> update(maxLevel + 1, nullptr);
    SkipListNode* current = header;

    // 从最高层开始查找删除位置的前驱节点
    for (int i = level; i >= 0; i--) {
        while (current->forward[i] && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    // 移至最底层的下一个节点
    current = current->forward[0];

    // 键不存在，无法删除
    if (!current || current->key != key) {
        return false;
    }

    // 更新指针，跳过要删除的节点
    for (int i = 0; i <= level; i++) {
        if (update[i]->forward[i] != current) {
            break;
        }
        update[i]->forward[i] = current->forward[i];
    }

    // 删除节点
    delete current;

    // 更新跳表的最高层数（如果需要）
    while (level > 0 && header->forward[level] == nullptr) {
        level--;
    }

    return true;
}

跳表的复杂度分析

时间复杂度

• 查找：平均O(log n)，最坏O(n)
• 插入：平均O(log n)，最坏O(n)
• 删除：平均O(log n)，最坏O(n)

空间复杂度

跳表的空间复杂度为O(n)，但常数因子比平衡树大，因为每个节点需要存储指向不同层的指针。平均而言，一个n个元素的跳表需要约2n个指针。

与平衡树的比较

跳表在ACM竞赛中的应用

在ACM竞赛中，跳表主要用于以下场景：

1. 有序数据集合维护：当需要一个支持高效查找、插入和删除的有序集合时
2. 排名查询：可以扩展跳表支持查找第k小元素或确定元素排名
3. 区间操作：跳表的有序特性使其适合处理区间查询和修改
4. 替代平衡树：当红黑树实现复杂度过高时，跳表是一个简单的替代选择

跳表的优化与扩展

1. 跳表的内存优化

在ACM竞赛环境中，可以使用数组池代替动态内存分配来提高效率：

// 节点池优化
const int MAXN = 100005;
SkipListNode nodePool[MAXN];
int nodeCount = 0;

SkipListNode* createNode(int key, int value, int level) {
    nodePool[nodeCount].key = key;
    nodePool[nodeCount].value = value;
    nodePool[nodeCount].forward.resize(level + 1, nullptr);
    return &nodePool[nodeCount++];
}

2. 支持排名查询的跳表

可以在节点中添加span字段来记录跨度，用于支持排名查询：

struct RankedSkipListNode {
    int key;
    int value;
    vector<RankedSkipListNode*> forward;
    vector<int> span;  // 在每一层，到forward[i]的跨度

    RankedSkipListNode(int k, int v, int level) : key(k), value(v) {
        forward.resize(level + 1, nullptr);
        span.resize(level + 1, 0);
    }
};

// 查找排名为rank的元素
RankedSkipListNode* findByRank(int rank) {
    if (rank <= 0) return nullptr;

    RankedSkipListNode* current = header;
    int accumulated = 0;

    for (int i = level; i >= 0; i--) {
        while (current->forward[i] && accumulated + current->span[i] < rank) {
            accumulated += current->span[i];
            current = current->forward[i];
        }
    }

    // 现在accumulated + current->span[0]应该等于rank
    if (current->forward[0]) {
        return current->forward[0];
    }

    return nullptr;  // rank超出范围
}

3. 支持区间查询的跳表

跳表的有序特性使其自然支持区间查询：

// 查询区间[minKey, maxKey]内的所有元素
vector<SkipListNode*> rangeQuery(int minKey, int maxKey) {
    vector<SkipListNode*> result;

    // 找到大于等于minKey的第一个节点
    SkipListNode* current = header;
    for (int i = level; i >= 0; i--) {
        while (current->forward[i] && current->forward[i]->key < minKey) {
            current = current->forward[i];
        }
    }

    // 移至第一个符合条件的节点
    current = current->forward[0];

    // 收集区间内的所有节点
    while (current && current->key <= maxKey) {
        result.push_back(current);
        current = current->forward[0];
    }

    return result;
}

跳表的典型应用例题

例题：多重集合维护

问题描述： 实现一个数据结构支持以下操作：

1. 插入一个数x
2. 删除一个数x（如果有多个，只删除一个）
3. 查询数x的排名（即集合中严格小于x的元素个数+1）
4. 查询排名为k的数
5. 查询x的前驱（小于x的最大元素）
6. 查询x的后继（大于x的最小元素）

解决思路： 这个问题可以使用跳表解决，实现如下：

class MultiskipList {
private:
    // 基础跳表实现...

    // 查询元素排名
    int getRank(int x) {
        SkipListNode* current = header;
        int rank = 0;

        for (int i = level; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->key < x) {
                rank += current->span[i];
                current = current->forward[i];
            }
        }

        return rank + 1;  // +1因为排名从1开始
    }

    // 查询第k小的元素
    SkipListNode* getElementByRank(int k) {
        if (k <= 0) return nullptr;

        SkipListNode* current = header;
        int accumulated = 0;

        for (int i = level; i >= 0; i--) {
            while (current->forward[i] && accumulated + current->span[i] < k) {
                accumulated += current->span[i];
                current = current->forward[i];
            }
        }

        if (current->forward[0]) {
            return current->forward[0];
        }

        return nullptr;
    }

    // 查询前驱
    SkipListNode* getPredecessor(int x) {
        SkipListNode* current = header;
        SkipListNode* predecessor = nullptr;

        for (int i = level; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->key < x) {
                current = current->forward[i];
            }

            if (current != header) {
                predecessor = current;
            }
        }

        return predecessor;
    }

    // 查询后继
    SkipListNode* getSuccessor(int x) {
        SkipListNode* current = header;

        for (int i = level; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->key <= x) {
                current = current->forward[i];
            }
        }

        if (current->forward[0]) {
            return current->forward[0];
        }

        return nullptr;
    }
};

跳表的实现技巧

1. 边界处理

在跳表的所有操作中，需要仔细处理边界情况：

• 空跳表
• 目标键不存在
• 操作第一个或最后一个元素

2. 随机化策略

跳表的性能很大程度上依赖于随机层数生成策略，常见方法有：

• 固定概率（如0.5或0.25）
• 基于节点数量动态调整概率
• 限制最大层数（通常取log₂n或更小）

// 一种常用的层数生成策略
int randomLevel() {
    int level = 0;
    while (rand() < RAND_MAX / 4 && level < maxLevel) {  // 概率0.25
        level++;
    }
    return level;
}

3. 避免使用STL

在ACM竞赛中，为了最大化性能，可以避免使用STL vector，而是使用固定大小的数组：

struct OptimizedNode {
    int key;
    int value;
    OptimizedNode* forward[MAX_LEVEL + 1];
    int span[MAX_LEVEL + 1];

    OptimizedNode(int k, int v) : key(k), value(v) {
        memset(forward, 0, sizeof(forward));
        memset(span, 0, sizeof(span));
    }
};

总结

跳表是一种随机化的数据结构，它提供了与平衡树相近的性能，但实现更为简单。通过多层链表结构和随机化技术，跳表在保持链表操作简单性的同时，实现了对数级别的查找时间复杂度。

跳表的主要优势在于：

1. 实现简单，代码量小于平衡树
2. 插入和删除操作较为局部化，不需要全局重平衡
3. 空间利用效率相对较高
4. 随机化特性使其在大多数情况下表现良好

在ACM竞赛中，当需要一个有序数据结构但不想实现复杂的平衡树时，跳表是一个非常好的选择。同时，跳表也可以扩展以支持排名查询、区间操作等高级功能，适用于各种复杂的问题场景。