数据结构-跳表

SkipList

跳表的原理

什么是跳表

链表，相信大家都不陌生，维护一个有序的链表是一件非常简单的事情，我们都知道，在一个有序的链表里面，查询跟插入的算法复杂度都是O(n)。

对上述有序列表建立一层索引
这样就可以加速查询效率和插入效率
比如查找 11，不加索引的需要查找 6次
加了一层索引以后，只需要查找 4次
查找速度为 O(n/2) +1

如果再加一层索引就变成是 O(n/4) + 2

跳表就是这样的一种数据结构，结点是跳过一部分的，
从而加快了查询的速度。跳表跟红黑树又有什么差别呢？

既然两者的算法复杂度差不多，为什么Redis要使用跳表而不使用红黑树呢？
跳表相对于红黑树，主要有这几个优点：

代码相对简单
如果我们要查询一个区间里面的值，用平衡树可能会麻烦。
这里的麻烦指的是实现和理解上，平衡二叉树查询一段区间也是可以做到的。
删除一段区间，这个如果是平衡二叉树，就会相当困难，
毕竟设计到树的平衡问题，而跳表则没有这种烦恼。

跳表查询元素

假如我们要查询11，那么我们从最上层出发，
发现下一个是5，再下一个是13，已经大于11，所以进入下一层，
下一层的一个是9，查找下一个，下一个又是13，再次进入下一层。
最终找到11。

最终一定查找会进入最底层

跳表插入元素

插入

插入的时候，首先要进行查询，然后从最底层开始，插入被插入的元素。
然后看看从下而上，是否需要逐层插入。

这里不需要完全平衡

最底层往上获取一个随机值[0,1]，判断小于0.5不插入结束，
否则将元素插入到当前层，并向上找一层，获取随机值[0,1]判断是否小于0.5
来确定当前层是否需要插入，除非到到最上层了，否则继续向上找上一层

插入 8

查询插入位置

底层插入，判断其上一层是否需要插入

继续判断直到条件不成立，或者到达最大层

跳表删除元素

首先需要查询最底层，然后对其他层做相同操作
删除需要删除每一层的对应节点

实现

设计图

测试

static void Main(string[] args)
{
    TestSkipList();
}
static void TestSkipList()
{
    //测试 调表结构
    SkipList<string, int> skipList = new DataStructLib.SkipList<string, int>();
    skipList.Add("1", 32);
    Console.WriteLine(skipList);
    skipList.Add("2", 12);
    Console.WriteLine(skipList);
    skipList.Add("4", 36);
    Console.WriteLine(skipList);
    skipList.Add("22", 3222);
    Console.WriteLine(skipList);
    skipList.Add("12", 1122);
    Console.WriteLine(skipList);
    skipList.Add("6", 31);
    Console.WriteLine(skipList);
    skipList.Remove("12");
    Console.WriteLine(skipList);
    skipList.Remove("6");
    Console.WriteLine(skipList);
}