[AlgoGo]跳表SkipList

跳表是什么

跳表的实现基于链表，弥补了链表不便于查找的缺点，所以跳表其实不是表(table)而是链(list)。跳表的查找时间复杂度是O(logn)，但是空间复杂度为O(n)。
跳表实现的思想与二分查找类似，通过建立逐级的索引，每一级索引的节点个数为原来的1/2（自定义），在查询时先从最后一级开始逐级向下查找，等价于实现了二分查找的过程。

跳表的结构

  SkipList
  {
    int count_level;
    Node* head; // 数据为空的头节点
  }
  Node
  {
    int data;
    int max_level; //每个节点的层数随机生成
    Node* forward[max_level]; //存储每一层的下一个节点信息
  }

跳表支持的操作

• 插入

  1. 新建节点。
  2. 从最后一层开始遍历每个层，找到每层新节点插入位置（最后一个值小于插入值的位置） ，缓存下来。
  3. 将新节点逐层插入到缓存节点后边。
  4. 若层数有增加则维护count_level。

• 删除

  1. 从最后一层开始遍历每层，找到每层最后一个值小于要删除节点的位置，缓存下来。
  2. 如果找到值等于删除节点的位置，逐层删除缓存节点。
  3. 如果有层节点个数为0，删除该层，维护count_level。

• 查找

  1. 从最后一层开始遍历，每一层找到最后一个值小于目标值的节点就进入下一层查找，直到第0层。
  2. 如果第0层对应的数据等于目标值，返回该节点，否则找不到。