跳表数据结构原理和应用如何深入解析？

跳表SKIPLIST 本文是新学习的内容 跳表是对有序链表的一种改进 有序链表随机访问很慢，不能像数组一样二分 （有序链表是默认从小到大排序，跳表这里也一样） 跳表支持的操作：插入一个\((key,val)\)元素 删除\(key\)的元素，查找元素\(key\)的\(val\)，查找\(key\)第\(k\)小的元素的\((key,val)\) 这里面是\(key\)有序 对于有序链表只有一层 跳表是间隔一些节点就向上增加一层然后上一层同理 这样子查找时候就可以先根据上层确定一个大概的范围再往下跳，次数大大减少了 具体来说，最底下一层每个元素都有，相当于原始有序链表，标记为第\(0\)层 每往上一层层数编号就\(+1\) 然后每个节点是否在上一层出现，是由一个概率\(p\)决定的，也就是说p的概率会出现在上一层，那么上一层到再上一层还是一个道理，\((1-p)\)的概率到这一层为止 然后每一层的节点还是按照顺序连接起来组成有序链表 每个节点只需要记录，他的\(key\)，\(val\)，以及后继\(nexts\) 我们不妨给最底下一层的节点开一个\(nexts[i]\)数组，因为每一层除了\(nexts[i]\)不一样，剩下都是一样的，这样就相当于共用一个节点，不同的\(nexts[i]\)代表不同的层 然后需要一个\(heads\)作为每一层链表的头部，头部的\(key\)取一个极小值比如-INT_MAX 这样的话插入任何元素都插入在\(heads\)后面 然后需要记录一个全局变量\(lv\)，是当前的最上面一层的编号，那么第\(lv\)层就是最上面一层，这样子插入时候增加层数只需要往后放而不是往前插入 层数： 然后这个层数有多少层呢，我们希望是把有\(1/p\)个节点的这一层作为最上面一层 这样期望的层数\(L\)有多少呢？ 最底下一层有\(n\)个，第\(1\)层有\(np\)个，第\(2\)层有\(np^2\)个…第\(L-1\)层有\(np^{(L-1)}\)个 \(np^{(L-1)}=p^{(-1)}\) \(np^L=1\) \(L=log(p,1/n)\) \(=log(1/p,n)\) 空间复杂度： 虽然说层数到了\(logn\)级别，但是每个点不是都每个层都有，有些节点层数高，有些节点层数低，所以均摊起来应该算每个节点的期望层数，所以就是问每个点的期望层数： 那么设期望层数是\(x\)，\(p\)的概率有上一层，那么此时层数是\(x+1\),\((1-p)\)的概率就只有这一层 所以\(x=p(x+1)+1-p\) \((1-p)x=1\) \(x=1/(1-p)\) 所以每个点的期望层数是常数 所以说期望空间复杂度\(O(n)\) 当然最坏每个点都到最上层\(O(nlogn)\) 但是现实是我们不同层的共用一个节点只是\(nexts[i]\)不同，所以说要提前开好最大层数来算的空间所以就\(O(nlogn)\)了 查询操作： 假如要查询\(num\)这个\(key\)值的\(val\) 从第\(lv\)层开始，首先确定\(num\)处在哪两个节点之间，然后才能往下找，这里面就有一个边界问题，就是区间端点问题，所以我们规定在点\(x\)和点\(y\)（相邻）之间的元素是\((x->key,y->key]\),左开右闭，所以说查找时候我们一直往右找 直到这个点右边\((nexts[i])\)的\(key >=num\)，那么\(num\)就落在这个点和这个点的\(nexts[i]\)的区间里，那么就要从这个点往下一层找了 然后就去下一层同一个点开始找，还是同样的道理 一直到第\(0\)层，最后循环结束假如在\(p\)点，那么\(num\)在\(p\)和\(p->nexts[0]\)之间，也就是说如果\(num\)存在，那么\(num\)和\(p->nexts[0]->key\)相等，直接返回对应的\(val\)即可 然后有一个边界问题，如果说给出的\(num\)比这一层最大的\(key\)都大，那么到这一层最后一个元素时候\(p->nexts[i]\)是空的,所以相当于没有上界，直接跳到下一层。如果到最后一层了，然后走到头\(p->nexts[0]\)是空的，那么实际上这个\(num\)就不存在。