跳跃表(skiplists)

跳跃表是一种增强版的链表,他能在O(lgn)的时间内完成搜索。

首先,我们熟知的链表本身具有的特性就是容易删除与增加,但是在搜索的时候会使用O(n)的时间。主要的原因就是链表本身访问起来必须的连续的,也许我们可能在某个节点上打出更多的锚点以链接到更远的节点,但是这样整个链表将会变得非常复杂,所以我们今天将要学习一种简单,但十分有效的数据结构,跳跃表。

结构

首先盗个图看看,懒得画了

跳跃表是一个多层相互链接的链表组,其中,L1 是基础链表,他将拥有链表中的所有元素,越向上的层级会拥有更少的元素,并且最优情况是每层元素数量是上一层二分之一。当然其分布绝对是越平均越好。

搜索

跳跃表的搜索从最高层开始不断往右搜索,直到发现过了头,接着回到上一个节点 向下一个层级 继续往右知道做过头,如此反复。就像是不断的坐车坐过站,然后坐车回去,并切换线路。

其实这个东西和 AVL 非常类似,很明显带有树的一些特性,或者说就是一个棵树,跳跃的过程其实就是类似二分查找的一个过程,每次的向下切换线路都会滤过一部分的节点。

插入

插入的过程会比搜索复杂一些,首先,最底层肯定的必定插入,接下来我们使用一个 50%概率的随机数比较,如果正面,提升,去往上一级,到了上一级继续投硬币,如果正面,再次提升,如此反复,如果上层链表还不存在,生成他。

要注意的是,每一层链表的起始点都必须是一个负无穷的数。这可以避免搜索从右上角开始的问题。

实现

自己也依靠公开课中的描述以及自己的理解实现了一个跳跃表,书里好像没这章节,所以走了不少弯路,如果你们发现错误的话还请纠正一下。实际用代码实现的时候还是有些复杂的。

class Node {
  constructor(val) {
    this.val = val
    this.low = null
    this.high = null
    this.left = null
    this.right = null
    this.lr = null // left root 该节点的最左边 负无限节点
  }
}

class SkipList {
  constructor() {
    this.root = new Node(-Infinity) // 初始化 一层最左边的负无限节点
  }
  insert(val) {
    let x = this.root
    let lr = this.root
    let tmp = {} // 虚体 吃时候为了让while第一次跑起来
    while (x !== null && tmp !== null) {
      // 注意插入判断的顺序 首先判断 当前是否已经到了最后一个值 代表直接插入到最后
      // 接下来就是普通的判断 前面比目标小 后面比目标大
      if (x.right === null || (val >= x.val && val <= x.right.val)) {
        let node = new Node(val)
        // 在这一层的插入
        node.right = x.right
        x.right = node
        node.left = x
        node.lr = lr
        if (tmp.val) {
          // 如果tmp存在 并且是实体 互相链接
          node.low = tmp
          tmp.high = node
        }
        // 如果这个节点 属于是当前层级的最右节点,并且上层已经建立 无条件升级
        // 或者 投硬币成功
        if ((node.right === null && lr.high !== null) || Math.random() > 0.5) {
          // tmp会被下一层用来连接
          tmp = node
          // 如果没有上层 去往left-root 建立一层
          if (lr.high === null) {
            lr.high = new Node(-Infinity)
            lr.high.low = lr
          }
          x = lr.high
          lr = lr.high
        } else {
          tmp = null
        }
      } else {
        x = x.right
      }
    }
  }
  search(val) {
    let x = this.root
    // 首先找到左上角定点
    while (x.high !== null) {
      x = x.high
    }
    // 如果都为如果都为false就代表已经到了右下角的节点
    while (x.right !== null || x.low !== null) {
      if (x.val === val) {
        return 'yes i find'
      }
      if (x.val > val) {
        // 其实这时候已经可以返回false了 因为接下来x的val只可能越来越大
        return 'no result'
      }
      // 要找节点还在右边 继续
      if (x.right.val <= val) {
        x = x.right
      } else if (x.right.val > val) {
        // 已经坐过头了 向下一层
        x = x.low
      }
    }
    return 'no result'
  }
}

图片版

我只想说 太酷了 这些创造数据结构的人真是太帅了啊