跳跃表特点
1、按照 score 来排序，如果 score 相等，那么则按照 ele 来排序。
2、平均查询时间复杂度 O(logn)。
跳跃表实现
跳跃表是由 server.h/zskiplistNode 和 server.h/zskiplist 两个结构定义其中
zskiplistNode 结构用于订阅跳跃表的节点，而 zskiplist 结构用于保存跳跃表相关的信息，比如节点的数量，以及想表头节点和表尾节点的指针等
跳跃表实现 server.h/zskiplistNode 结构定义：
/* ZSETs use a specialized version of Skiplists */ typedef struct zskiplistNode { //数据 sds ele; //分值 double score; //后退指针 struct zskiplistNode *backward; //层 struct zskiplistLevel { //前进指针 struct zskiplistNode *forward; //跨度 unsigned long span; } level[]; } zskiplistNode;
zskiplist 结构定义如下：
typedef struct zskiplist { //头节点和尾节点 struct zskiplistNode *header, *tail; //表中节点的数量 unsigned long length; //表中层数最大的节点层数 int level; } zskiplist;
以 zskiplist 为基础的数据结构图如下：
运用场景
- 跳跃表是有序集合（zset）的底层实现之一
typedef struct zset { dict *dict; zskiplist *zsl; } zset;
设计跳表
力扣题目（1206）:
不使用任何库函数，设计一个 跳表 。
跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。
了解更多 : https://en.wikipedia.org/wiki/Skip_list
在本题中，你的设计应该要包含这些函数：
bool search(int target): 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
示例 1:
输入 ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] 输出 [null, null, null, null, false, null, true, false, true, false] 解释 Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // 返回 false skiplist.add(4); skiplist.search(1); // 返回 true skiplist.erase(0); // 返回 false，0 不在跳表中 skiplist.erase(1); // 返回 true skiplist.search(1); // 返回 false，1 已被擦除
提示:
0 <= num, target <= 2 * 104
- 调用
search,add,erase操作次数不大于5 * 104
解题代码
下面是参考 redis 的 skiplist 的实现。代码如下：
public class Skiplist { private static final float SKIPLIST_P = 0.5f; private static final int MAX_LEVEL = 16; // 头节点 Node head; // 节点对象 class Node { int val; Node bw; // 后退指针 Node[] fw; // 前进指针 // 构造函数 public Node(int val) { this.val = val; fw = new Node[randomLevel()]; } public Node(int val, int size) { this.val = val; fw = new Node[size + 1]; } // 生成随机 level public int randomLevel() { int level = 1; while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) { level++; } return level; } } // 生成默认的头节点 public Skiplist() { head = new Node(-1, MAX_LEVEL); } // 查询 public boolean search(int target) { Node p = searchNode(target); boolean b = p.val == target; //System.out.println(b); return b; } // 添加 public void add(int num) { Node p = searchNode(num); Node n = new Node(num); n.bw = p; for (int i = 0; i < n.fw.length; i++) { Node f = p; while (f.bw != null && f.fw.length < i + 1) { f = f.bw; } if (i == 0 && f.fw[i] != null) { f.fw[i].bw = n; } n.fw[i] = f.fw[i]; f.fw[i] = n; } } // 移除 public boolean erase(int num) { if (isEmpty()) { //System.out.println(false); return false; } Node p = searchNode(num); if (p.val != num) { //System.out.println(false); return false; } for (int i = 0; i < p.fw.length; i++) { Node f = p.bw; while (f.bw != null && f.fw.length < i + 1) { f = f.bw; } if (i == 0 && f.fw[i].fw[i] != null) { f.fw[i].fw[i].bw = f; } f.fw[i] = f.fw[i].fw[i]; } //System.out.println(true); return true; } // 查询节点 private Node searchNode(int target) { if (isEmpty()) { return head; } Node p = head; for (int i = MAX_LEVEL; i >= 0; i--) { while (p.fw[i] != null && p.fw[i].val <= target) { p = p.fw[i]; } } return p; } // 是否为空 private boolean isEmpty() { return head.fw[0] == null; } }
执行示例（执行结果）：
