数据结构和算法之美-第十二篇-跳表

什么是跳表？

跳表是一种改造之后的链表。具体的改造过程就是加索引，加多级索引。如何加索引?请看下图，存储数据为：1 3 4 6 8 9 10 14 15 18每两个数建立一级索引

我们知道访问单链表中的数据只能一个一个的访问，所以单链表的查询时间复杂度是O(n)。建立了索引之后的跳表的时间复杂度是O(logn)。比如这个例子，我们建立了二级索引，如果我们要查询有序数组中的数据9，可以直接通过二级索引直接找到8，然后在下行到一级索引发现下一个数10已经比9大，所以再下行到初始链表，向前查询直接就能找到数据9。

仔细想想，跳表的查询过程很接近二分查找，二分查找通过循环或递归计算中间下标缩小区间，跳表通过索引下行不断锁定给定数据的区间。可以说跳表已经可以支持‘二分’查找算法。

跳表的性能

跳表的查询的时间复杂度是O(logn)，单链表本身的插入、删除操作的时间复杂度是O(1)，但是插入和删除操作的前提是先要找到指定节点或者指定节点的前驱或者后继节点，也就是先要进行查询操作，所以跳表的插入、删除操作的时间复杂度也是O(logn)。

跳表需要建立索引，空间复杂度是O(n)。以上面两个数据建立一个索引为例，第一级索引有 n/2 个，第二级索引有 n/4 个，以此类推，最终占据空间 n/2 + n/4 + ….+ 8 + 4 + 2。最有一级的索引数量为 2 。其实这就是个等比数列。计算结果为 n-2，所以跳表的空间复杂度为 O(n)
这是间隔为 2 建立索引的情况，若是间隔为 3 或者为 5，空间复杂度相对会小一点，不过依然是 O(n)
跳表索引的建立不是完全的复制节点的数据建立新的节点。只是扩展指针，建立索引的节点不仅指向下一个节点，也同时指向多个更远的节点。所以即使每个节点存储的数据很大，建立索引真实占用的额外空间其实很小。

说到索引的问题，跳表的插入和删除难道不需要维护索引吗？这个确实是需要一些手段来维护数据多次改变之后整体索引的平衡。比如链表中的节点增多了，相应的就需要增加索引。就像红黑树通过左右旋的方式保持左右子树的大小平衡。这里不去过多的讨论。

跳表的是一中各方面性能都挺优秀的数据结构，甚至可以代替红黑树。

跳表的实现

跳表没有现成的实现，如果要使用需要自我实现，参考链接使用JavaScript实现SkipList这种数据结构

const MAX_LEVEL = 16;
class Node {
  constructor({ data = -1, maxLevel = 0, refer = new Array(MAX_LEVEL) } = {}) {
    this.data = data;
    this.maxLevel = maxLevel;
    this.refer = refer;
  }
}

class SkipList {
  constructor() {
    this.head = new Node();
    this.levelCount = 1;
  }
  randomLevel() {
    let level = 1;
    for (let i = 1; i < MAX_LEVEL; i++) {
      if (Math.random() < 0.5) {
        level++;
      }
    }
    return level;
  }
  insert(value) {
    const level = this.randomLevel();
    const newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    const update = new Array(level).fill(new Node());
    let p = this.head;
    for (let i = level - 1; i >= 0; i--) {
      while (p.refer[i] !== undefined && p.refer[i].data < value) {
        p = p.refer[i];
      }
      update[i] = p;
    }
    for (let i = 0; i < level; i++) {
      newNode.refer[i] = update[i].refer[i];
      update[i].refer[i] = newNode;
    }
    if (this.levelCount < level) {
      this.levelCount = level;
    }
  }

  find(value) {
    if (!value) {
      return null;
    }
    let p = this.head;
    for (let i = this.levelCount - 1; i >= 0; i--) {
      while (p.refer[i] !== undefined && p.refer[i].data < value) {
        p = p.refer[i];
      }
    }

    if (p.refer[0] !== undefined && p.refer[0].data === value) {
      return p.refer[0];
    }
    return null;
  }

  remove(value) {
    let _node;
    let p = this.head;
    const update = new Array(new Node());
    for (let i = this.levelCount - 1; i >= 0; i--) {
      while (p.refer[i] !== undefined && p.refer[i].data < value) {
        p = p.refer[i];
      }
      update[i] = p;
    }

    if (p.refer[0] !== undefined && p.refer[0].data === value) {
      _node = p.refer[0];
      for (let i = 0; i <= this.levelCount - 1; i++) {
        if (
          update[i].refer[i] !== undefined &&
          update[i].refer[i].data === value
        ) {
          update[i].refer[i] = update[i].refer[i].refer[i];
        }
      }
      return _node;
    }
    return null;
  }

  printAll() {
    let p = this.head;
    while (p.refer[0] !== undefined) {
      console.log(p.refer[0].data);
      p = p.refer[0];
    }
  }
}

test();
function test() {
  let list = new SkipList();
  let length = 20000;
  //顺序插入
  for (let i = 1; i <= 10; i++) {
    list.insert(i);
  }
  //输出一次
  list.printAll();
  console.time("create length-10");
  //插入剩下的
  for (let i = 11; i <= length - 10; i++) {
    list.insert(i);
  }
  console.timeEnd("create length-10");
  //搜索 10次
  for (let j = 0; j < 10; j++) {
    let key = Math.floor(Math.random() * length + 1);
    console.log(key, list.find(key));
  }
  //搜索不存在的值
  console.log("null:", list.find(length + 1));
  //搜索5000次统计时间
  console.time("search 5000");
  for (let j = 0; j < 5000; j++) {
    let key = Math.floor(Math.random() * length + 1);
  }
  console.timeEnd("search 5000");
}

什么是跳表？

跳表的性能

跳表的实现

FEATURED TAGS

FRIENDS