Codelet Keep code simple stupid

跳表

06 Oct 2016

跳表又叫跳跃链表，它是除了搜索树以外的，另一种用于快速查找元素的数据结构，跳表是一种单向多链表， 它以多层次的链接作为索引，实现对元素的快速查找

跳表的原理和单链表类似，元素按顺序存放，且链接都指向后继结点，不同之处在于跳表结点具有多个链接， 不同层次的链接跨度不同，因此在查找时可以跳过许多元素，避免了低效的逐一比较

表结点

跳表的结点具有多个链接，链接的数目（结点的度）最小为1，因此结点的第一层链接一定会指向结点的直接 后继（不跳过任何结点），第二层链接会跳过度为 1 的结点，第 n 层链接会跳过所有度小于 n 的结点， 以下是表结点的定义

struct Node {
  Node** forward;
  const int level;
  int value;

  Node(int value, int level)
  : level(level),
    value(value) {
    forward = new Node*[level]();
  }

  ~Node() {
    delete[] forward;
  }
};

查找

和单链表类似，跳表通过两个指针实现查找，一个用于比较元素大小，另一个用于保存前驱结点

Node* SkipList::search(int key) const {
  Node* prev = head_;
  Node* node;
  for (int l = kMaxLevel - 1; l >= 0; l--) {
    node = prev->forward[l];
    while (node != nullptr && node->value < key) {
      prev = node;
      node = prev->forward[l];
    }
  }
  // check value
  if (node != nullptr && node->value == key) {
    return node;
  } else {
    return nullptr;
  }
}

插入/删除

下面贴出跳表的完整实现

class SkipList {
public:
  SkipList();
  ~SkipList();

  size_t size() const { return size_; }
  Node* search(int key) const;
  void insert(int key);
  Node* remove(int key);

private:
  void seekFor(int key, Node* update[]) const;
  int randomLevel() const;

  static const int kMaxLevel = 6;

  Node* head_;
  size_t size_;
};

SkipList::SkipList()
  : size_(0) {
  head_ = new Node(INT32_MIN, kMaxLevel);
}

SkipList::~SkipList() {
  Node* node = head_;
  Node* next;
  while (node != nullptr) {
    next = node->forward[0];
    delete node;
    node = next;
  }
}

void SkipList::seekFor(int key, Node* update[]) const {
  Node* prev = head_;
  Node* node;
  for (int l = kMaxLevel - 1; l >= 0; l--) {
    node = prev->forward[l];
    while (node != nullptr && node->value < key) {
      prev = node;
      node = prev->forward[l];
    }
    update[l] = prev;
  }
}

int SkipList::randomLevel() const {...}

void SkipList::insert(int key) {
  Node* update[kMaxLevel];
  seekFor(key, update);
  // create node
  Node* newNode = new Node(key, randomLevel());
  // link node
  for (int i = 0; i < newNode->level; i++) {
    newNode->forward[i] = update[i]->forward[i];
    update[i]->forward[i] = newNode;
  }
  size_++;
}

Node* SkipList::remove(int key) {
  Node* update[kMaxLevel];
  seekFor(key, update);
  // get target node
  Node* node = update[0]->forward[0];
  // check value
  if (node != nullptr && node->value == key) {
    // unlink node
    for (int i = 0; i < node->level; i++) {
      update[i]->forward[i] = node->forward[i];
      node->forward[i] = nullptr;
    }
    size_--;
    return node;
  } else {
    return nullptr;
  }
}

结点的度

跳表的实现还是比较简单的，最关键的地方在于结点度数的确定，下面简单介绍两种方法

  • 二分法 最容易想到的方法是二分法，最上层跳过一半的元素，下一层跳过1/4的元素，第一层不跳过元素，二分法的 优点在于确定性强，查找的时间复杂度不超过\(O(n / 2 ^ m)\)，m 是链表的层数，如果 m 足够大， 则时间复杂度为\(O(log_2(n))\)

这种方法的缺点在于插入删除操作，如果表经过多次插入或删除操作，则无法继续保持二分特性，而重新计算 索引是十分昂贵的，因此只适合元素相对固定的情况

  • 随机化 另一种更常见的是随机化算法，这种方法创建的结点的链接数目是随机的，因此不需要专门的维护表的索引， 只要层数足够，最好情况下的时间复杂度为\(O(log(n))\)，但在最坏情况下，查找会退化为逐一比较， 时间复杂度会达到\(O(n)\)

结点度数的分布律决定了跳表的平均性能，如果度数在[1, m]内平均分布，则上层的链接偏多，加大了查找 元素所需的比较次数，总体的平均时间复杂度为\(O(n / log_2(n))\)

为了使查找尽量的接近于二分查找，应该让度为 1 的结点占一半，度为 2 的结点占1/4，度为 m 的结点占 \(1/2^m\)，代码如下

int SkipList::randomLevel() const {
  int bit = rand() & 1;
  int level = 1;
  while (bit == 0 && level < kMaxLevel) {
    bit = rand() & 1;
    level++;
  }
  return level;
}

参考资料：
[1] wikipedia - Skip list

Related Posts