C++跳表的实现

一、跳表的介绍

跳表(skiplist)和哈希表、平衡搜索树一样，也是一种查找结构。跳表多使用在 kv 型数据库中, Redis 中就会使用跳表

平常有序的单链表，查找时间复杂度为O(N)。我们该如何考虑优化它呢？

跳表中的思想就是将中间节点升高，直接和高层节点比较，大于它就向后，小于就向左，提高了查找效率。

一般的链表：

跳表：

如果每一层的上层是下层的一半，那么就等同于二分查找。但是在插入和删除的过程中很难维护这个条件(如果要维护，时间复杂的很可能降回O(N) )。

因此，跳表选择了随机层数，每一个节点的层数都是随机的。

二、跳表的平均层数计算

假设跳表多增加一层的概率为 p，一层的概率为 (1-p)，二层的概率为 p*(1-p)，三层的概率为 p^2\*(1-p) ...... 由此类推，n 层的概率为 p^(n-1)*(1-p)

一个节点的平均层数：

概率论知识：用概率乘以层数，相加，得到的就是层数的期望值。(可以反映随机变量平均取值大小)

由此可以得出，平均层数为 1/(1-p) 。

当 p 为 0.5 时，平均层数为 2
当 p 为 0.25 时，平均层数为 1.33 (redis 中 p 就选择为 0.25)

三、跳表的实现

1、跳表的结构设计

// 跳表节点
struct SkiplistNode
{int _val; // 该节点的值vector<SkiplistNode*> _nextV; // 下标+1 为层数，指向每一层的下一个节点SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};class Skiplist {
public:typedef SkiplistNode node;Skiplist() {// 初始化当前层数为 1_head = new node(-1, 1);srand(time(0)); // 随机数种子，新节点获取随机层数用的}node* _head; // 头结点double _p = 0.25; // 新增一层的概率int _maxLevel = 32; // 最大层数
};

在 Redis 实现的跳表中，两个参数取值为

p = 0.25

maxLevel = 32

2、获取随机层数

跳表多增加一层的概率为 p

// 给新节点一个随机层数
int GetLevel()
{// 开始为 1 层，每次 随机数/最大随机数 < p ，多加一层// 也就是多加一层的概率为 p，不能超过最大层int level = 1;while (rand() < _p * RAND_MAX && level < _maxLevel){++level;}return level;
}

3、跳表的查找

跟cur->next[level]->val 比较，比他小或下一个为空，向下走；比他大，向右走。

当走到层数 < 0，说明没找到该值。

bool search(int target) 
{node* cur = _head; // 当前节点int cur_level = _head->_nextV.size() - 1;// 当前节点层数// 如果层数 < 0，那么说明查找失败while (cur_level >= 0){// 如果当前层的下一个为空，或者当前层的下一个比 target 大，向下层找if (cur->_nextV[cur_level] == nullptr || cur->_nextV[cur_level]->_val > target)cur_level--;// 如果下一个节点比 target 小，向右查找else if (cur->_nextV[cur_level]->_val < target)cur = cur->_nextV[cur_level];elsereturn true;}return false;
}

4、跳表的插入

1、找到每一层的前一个节点

2、逐层插入

// 查找值为 num 的前一个节点(每一层)
vector<node*> FindPrevNode(int num)
{// 拿到所有层的前一个节点，层数超过默认就为 headvector<node*> prevV(_maxLevel, _head);// 当前节点 与 当前节点层数node* cur = _head;int cur_level = _head->_nextV.size() - 1;// 当前层数 < 0 退出while (cur_level >= 0){// 如果下一个为空 或 下一个大于 num，说明 cur 为 num 在当前层的前一个节点if (cur->_nextV[cur_level] == nullptr || cur->_nextV[cur_level]->_val >= num){prevV[cur_level] = cur;cur_level--;}// 如果当前层下一个节点 < num，向右继续查找else if (cur->_nextV[cur_level]->_val < num)cur = cur->_nextV[cur_level];}return prevV;
}void add(int num) {// 得到每一层的前节点集合vector<node*> prevV = FindPrevNode(num);// 得到一个随机层数，创建节点int newlevel = GetLevel();node* newnode = new node(num, newlevel);// 我们是用头结点的层数查找的// 如果头结点的层数 < 当前层数，更新头结点层数if (_head->_nextV.size() < newlevel)_head->_nextV.resize(newlevel);// 头结点 head 的新增层默认必须为空，新节点插入后才会指向空// 每一层插入for (int i = 0; i < newlevel; ++i){newnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode;}
}

5、跳表的删除

1、找到每一层的前一个节点

2、逐层删除

bool erase(int num) 
{// 得到每一层的前节点集合，具体实现放在(4)插入中vector<node*> prevV = FindPrevNode(num);// 因为第一层是一定有的，因此用第一层做判断// 第一层前节点的下一个为空 或 值不为 num，说明没有值为 num 的节点，返回 falseif (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)return false;node* del = prevV[0]->_nextV[0];// 要删除的节点int levelNum = del->_nextV.size();// 要删除的节点的层数// 遍历删除每一层for (int i = 0; i < levelNum; ++i){prevV[i]->_nextV[i] = del->_nextV[i];}// 释放节点delete del;return true;
}

6、完整代码

struct SkiplistNode
{int _val;vector<SkiplistNode*> _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};class Skiplist {
public:typedef SkiplistNode node;Skiplist() {// 初始化当前层数为 1_head = new node(-1, 1);srand(time(0));}bool search(int target) {node* cur = _head; // 当前节点int cur_level = _head->_nextV.size() - 1;// 当前节点层数// 如果层数 < 0，那么说明查找失败while (cur_level >= 0){// 如果当前层的下一个为空，或者当前层的下一个比 target 大，向下层找if (cur->_nextV[cur_level] == nullptr || cur->_nextV[cur_level]->_val > target)cur_level--;// 如果下一个节点比 target 小，向右查找else if (cur->_nextV[cur_level]->_val < target)cur = cur->_nextV[cur_level];elsereturn true;}return false;}// 查找值为 num 的前一个节点(每一层)vector<node*> FindPrevNode(int num){// 拿到所有层的前一个节点，层数超过默认就为 headvector<node*> prevV(_maxLevel, _head);// 当前节点 与 当前节点层数node* cur = _head;int cur_level = _head->_nextV.size() - 1;// 当前层数 < 0 退出while (cur_level >= 0){// 如果下一个为空 或 下一个大于 num，说明 cur 为 num 在当前层的前一个节点if (cur->_nextV[cur_level] == nullptr || cur->_nextV[cur_level]->_val >= num){prevV[cur_level] = cur;cur_level--;}// 如果当前层下一个节点 < num，向右继续查找else if (cur->_nextV[cur_level]->_val < num)cur = cur->_nextV[cur_level];}return prevV;}void add(int num) {// 得到每一层的前节点集合vector<node*> prevV = FindPrevNode(num);// 得到一个随机层数，创建节点int newlevel = GetLevel();node* newnode = new node(num, newlevel);// 我们是用头结点的层数查找的// 如果头结点的层数 < 当前层数，更新头结点层数if (_head->_nextV.size() < newlevel)_head->_nextV.resize(newlevel);// 每一层插入for (int i = 0; i < newlevel; ++i){newnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode;}}bool erase(int num) {// 得到每一层的前节点集合vector<node*> prevV = FindPrevNode(num);// 因为第一层是一定有的，因此用第一层做判断// 第一层前节点的下一个为空 或 值不为 num，说明没有值为 num 的节点，返回 falseif (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)return false;node* del = prevV[0]->_nextV[0];// 要删除的节点int levelNum = del->_nextV.size();// 要删除的节点的层数// 遍历删除每一层for (int i = 0; i < levelNum; ++i){prevV[i]->_nextV[i] = del->_nextV[i];}// 释放节点delete del;return true;}// 给新节点一个随机层数int GetLevel(){// 开始为 1 层，每次 随机数/最大随机数 < p ，多加一层// 也就是多加一层的概率为 p，不能超过最大层int level = 1;while (rand() < _p * RAND_MAX && level < _maxLevel){++level;}return level;}void Print(){int level = _head->_nextV.size();for (int i = level - 1; i >= 0; --i){node* cur = _head->_nextV[i];while (cur){printf("%d -> ", cur->_val);cur = cur->_nextV[i];}printf("\n");}}node* _head;double _p = 0.25;int _maxLevel = 32;
};