个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》《C++》《Linux》《网络》 《redis学习笔记》
文章目录
- 前言
- 跳表
- 跳表的优化思路
- skiplist，平衡搜索树，哈希表的对比
- 实现思路
- SkiplistNode
- search 搜索
- add 增加
- earse 删除
- 整体代码
- 总结
前言
本文使用C++实现跳表的增删查。
铁蕾大佬关于跳表的博客
跳表
跳表(SkipList)是一种用于有序数据的高效数据结构，由 William Pugh 在1989年提出。
跳表本质是一个查找结构，通过在原有的有序链表上面增加多级索引来实现快速查找；跳表可以看作是一种可以进行二分查找的有序链表。
跳表的优化思路
跳表的优化思路
假如我们每相邻两个节点增加一个指针，让这个指针指向下下个节点。
这样所有新增加的指针连成一个新链表，但它包含的节点个数只有原来的一半。此时，我们再查找特定元素时，需要比较的节点数量大概只有原来的一半。
跳表就是采用多层链表的思路。
skiplist，平衡搜索树，哈希表的对比
SkipList(跳表)：
查找效率：跳表的平均时间复杂度为O(logN)，其中N是节点的数量。这是因为跳表通过多层链表结构，使得查找过程能够跳过部分节点，从而加快查找速度；
特点：跳表是一种概率平衡的数据结构，其实现相对简单，且支持快速的插入，删除和查找操作。同时，跳表在内存中的占用也相对较低
平衡搜索树
查找效率：平衡搜索树的查找时间复杂度通常我O(logN)，其中N是节点的数量。这是因为平衡搜索树通过旋转，分裂等操作来保持树的平衡性，从而确保每次查找都能快速定位到目标节点
特定：平衡搜索树具有严格的平衡性要求，使其插入，删除和查找操作都能保持较高的效率。同时，平衡搜索树还支持范围查询等复杂操作。然而，其实现相对复杂，且需要额外的空间来维护树的平衡性
哈希表
查找效率：哈希表的查找效率时间复杂度平均为O(1)，但在最坏情况下可能退化为O(N)。因此，哈希表的查找效率取决于哈希函数的优劣和装填因子的设置
特点：哈希表具有极高的查找效率，特别适用于需要频繁查找的场景。同时，哈希表的插入和删除操作也相对简单。然而，哈希表不支持范围查询等复杂操作，且哈希冲突较多时，其性能可能会受到影响。此外，哈希表还需要额外的空间来存储哈希函数和链表等结构
实现思路
SkiplistNode
struct SkiplistNode {int _val;vector<SkiplistNode*> _nexts;SkiplistNode(int val, int level) :_val(val), _nexts(level, nullptr) {}
};
search 搜索
假如我们要查找 17 这个节点
先定义 cur 指向头节点，从最顶层开始查找；发现 9 小于 17(要查找元素在该元素后面)，改变cur指向，使cur 指向 9节点。
再从9节点开始查找，发现 21 大于 17(要查找元素在该元素前面)，去下面一层查找，发现 17 == 17，找到要查找的元素。
bool search(int target) {int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (cur->_nexts[level] && cur->_nexts[level]->_val < target) {// 向右走，更新 cur 和 level，target 只能在 cur->_nexts[level]->_val 后面cur = cur->_nexts[level];}else if (!cur->_nexts[level] || cur->_nexts[level]->_val > target) {// 向下走，target 只能在 cur->_nexts[level]->_val 前面level--;}else {// 找到了return true;}}return false;}
add 增加
假如我们要增加 18 。
那我们需要分三步完成，1.寻找到新增节点要插入的位置。2.构造新节点。3.链接节点；其实与单链表的新增节点相似，只不过寻找到新增节点要插入的位置由一点不同
寻找新增节点要插入的位置
我们需要一个数组(大小为最大层数)，来记录新节点前面的节点。此时 cur 指向头结点，从顶层开始查找，发现 6 < 18(新增节点在6的后面)，改变cur，使cur指向6
cur指向6，从顶层查找，发现6指向nullptr，向下走，prevs在第4层记录6(如果新增节点有4层，6可能是新增节点的前一个节点)。发现 25 > 18(新增节点在25之前)，向下走，prevs在第三层记录6(如果新增节点有3层，6可能是新增节点的前一个节点)。发现 9 < 18(新增节点在9后面)，cur 指向9。
cur指向9，从第二层查找，发现 17 < 18(新增节点在17之后)，cur指向17。 
cur指向17，从第二层查找，发现 25 > 18(新增节点在25前面)，向下走，prevs在第二层记录17(如果新增节点有2层，17可能是新增节点的前一个节点)。从第一次查找，发现 19 > 18(新增节点在19前面)，向下走，prevs在第一层记录19(如果新增节点有1层，19可能是新增节点的前一个节点)。此时层数 小于 0，查找结束。17的后面就是新增节点的位置。
vector<SkiplistNode*> searchPrevs(int num) {vector<SkiplistNode*> prevs(_maxLevel, &_head);int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (!cur->_nexts[level] || cur->_nexts[level]->_val >= num) {// 要插入节点，一定在cur->_nexts[level]的前面// 向下走，并更新节点prevs[level] = cur;level--;}else if (cur->_nexts[level] && cur->_nexts[level]->_val < num) {// 要插入节点，一定在cur->_nexts[level]的后面// 向右走cur = cur->_nexts[level];}}return prevs;}void add(int num) {// 寻找插入位置，并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 构造新节点，随机层数int newlevel = RandomLevel();SkiplistNode* newnode = new SkiplistNode(num, newlevel);// 连接节点newlevel--;while (newlevel >= 0) {newnode->_nexts[newlevel] = prevs[newlevel]->_nexts[newlevel];prevs[newlevel]->_nexts[newlevel] = newnode;newlevel--;}}
earse 删除
假如我们要删除 19。
我们需要4步完成，1.寻找删除节点，并记录前面节点。2.判断是否存在要删除的节点。3.链接节点。4.删除节点
与新增节点操作类似。
经过第一步寻找删除节点，并记录前面节点后，我们只需判断prevs数组中第0层节点的第0层指向的节点是否等于要删除节点即可。
vector<SkiplistNode*> searchPrevs(int num) {vector<SkiplistNode*> prevs(_maxLevel, &_head);int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (!cur->_nexts[level] || cur->_nexts[level]->_val >= num) {// 要插入节点，一定在cur->_nexts[level]的前面// 向下走，并更新节点prevs[level] = cur;level--;}else if (cur->_nexts[level] && cur->_nexts[level]->_val < num) {// 要插入节点，一定在cur->_nexts[level]的后面// 向右走cur = cur->_nexts[level];}}return prevs;}bool erase(int num) {// 寻找删除节点，并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 判断是否存在要删除的节点if (!prevs[0]->_nexts[0] || prevs[0]->_nexts[0]->_val != num)return false;// 连接节点SkiplistNode* del = prevs[0]->_nexts[0];int level = del->_nexts.size() - 1;while (level >= 0) {prevs[level]->_nexts[level] = del->_nexts[level];level--;}// 删除节点delete del;return true;}
整体代码
leetcode上设计跳表的题
1206.设计跳表
struct SkiplistNode {int _val;vector<SkiplistNode*> _nexts;SkiplistNode(int val, int level) :_val(val), _nexts(level, nullptr) {}
};class Skiplist {// 本质是一个有序链表
public:Skiplist() :_head(-1, _maxLevel) {srand((unsigned int)time(nullptr));}bool search(int target) {int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (cur->_nexts[level] && cur->_nexts[level]->_val < target) {// 向右走，更新 cur 和 level，target 只能在 cur->_nexts[level]->_val 后面cur = cur->_nexts[level];}else if (!cur->_nexts[level] || cur->_nexts[level]->_val > target) {// 向下走，target 只能在 cur->_nexts[level]->_val 前面level--;}else {// 找到了return true;}}return false;}void add(int num) {// 寻找插入位置，并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 构造新节点，随机层数int newlevel = RandomLevel();SkiplistNode* newnode = new SkiplistNode(num, newlevel);// 连接节点newlevel--;while (newlevel >= 0) {newnode->_nexts[newlevel] = prevs[newlevel]->_nexts[newlevel];prevs[newlevel]->_nexts[newlevel] = newnode;newlevel--;}}bool erase(int num) {// 寻找删除节点，并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 判断是否存在要删除的节点if (!prevs[0]->_nexts[0] || prevs[0]->_nexts[0]->_val != num)return false;// 连接节点SkiplistNode* del = prevs[0]->_nexts[0];int level = del->_nexts.size() - 1;while (level >= 0) {prevs[level]->_nexts[level] = del->_nexts[level];level--;}// 删除节点delete del;return true;}private:int RandomLevel() {int level = 1;while (rand() <= RAND_MAX * _p && level < _maxLevel)level++;return level;}vector<SkiplistNode*> searchPrevs(int num) {vector<SkiplistNode*> prevs(_maxLevel, &_head);int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (!cur->_nexts[level] || cur->_nexts[level]->_val >= num) {// 要插入节点，一定在cur->_nexts[level]的前面// 向下走，并更新节点prevs[level] = cur;level--;}else if (cur->_nexts[level] && cur->_nexts[level]->_val < num) {// 要插入节点，一定在cur->_nexts[level]的后面// 向右走cur = cur->_nexts[level];}}return prevs;}private:double _p = 0.5;int _maxLevel = 32;SkiplistNode _head;
};
总结
以上就是跳表的实现
