C++ 跳表简单实现

本文介绍了跳表（Skiplist）的简单实现，跳表是一种高效的数据结构，支持快速查找、插入和删除操作。文章详细展示了跳表的C++实现代码，包括节点结构定义、搜索、添加和删除操作的逻辑。通过随机层级生成和多层链表结构，跳表在保持简单性的同时，提供了接近平衡树的性能。本文为C++开发者提供了跳表的实用实现方法，适合需要高效数据管理的场景。

跳表简单实现

struct Node {
  Node(int i, Node *r, Node *d) : val(i), right(r), down(d) {}
  int val;
  Node *right;
  Node *down;
};
class Skiplist {
 public:
  Skiplist() {}

  bool search(int target) {
    auto cur = head;
    while (cur) {
      while (cur->right && cur->right->val < target) {
        cur = cur->right;
      }
      if (cur->right && cur->right->val == target) {
        return true;
      }
      cur = cur->down;
    }
    return false;
  }

  void add(int num) {
    int r_level = 1;
    while (r_level <= max_level && (rand() & 1 == 0)) {
      ++r_level;
    }
    if (r_level > max_level) {
      max_level = r_level;
      head = new Node(num, nullptr, head);
    }
    Node *cur = head;
    Node *last = nullptr;
    for (int l = max_level; l >= 1; --l) {
      while (cur->right && cur->right->val < num) {
        cur = cur->right;
      }
      if (l <= r_level) {
        cur->right = new Node(num, cur->right, nullptr);
        if (last) {
          last->down = cur->right;
        }
        last = cur->right;
      }
      cur = cur->down;
    }
  }

  bool erase(int num) {
    auto cur = head;
    bool seen = false;
    for (int l = max_level; l >= 1; --l) {
      while (cur->right && cur->right->val < num) {
        cur = cur->right;
      }
      if (cur->right && cur->right->val == num) {
        seen = true;
        Node *temp = cur->right;
        cur->right = cur->right->right;
        delete temp;
      }
      cur = cur->down;
    }
    return seen;
  }

 private:
  int max_level = 0;
  Node *head = nullptr;
};