当前位置：首页 > JavaScript

跳表js实现

2026-01-31 23:59:52JavaScript

跳表（Skip List）的 JavaScript 实现

跳表是一种概率性的数据结构，允许快速查找、插入和删除操作，时间复杂度接近平衡树（O(log n)）。以下是跳表的 JavaScript 实现。

跳表js实现

跳表节点类

跳表节点包含值、指向右侧节点的指针数组和指向下方节点的指针数组。

跳表js实现

class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.next = new Array(level).fill(null);
  }
}

跳表类

跳表类包含初始化、随机层数生成、插入、查找和删除等方法。

class SkipList {
  constructor() {
    this.maxLevel = 16; // 最大层数
    this.head = new SkipListNode(null, this.maxLevel);
    this.level = 1; // 当前层数
    this.probability = 0.5; // 层数增长概率
  }

  // 随机生成层数
  _randomLevel() {
    let level = 1;
    while (Math.random() < this.probability && level < this.maxLevel) {
      level++;
    }
    return level;
  }

  // 查找节点
  search(value) {
    let current = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (current.next[i] !== null && current.next[i].value < value) {
        current = current.next[i];
      }
    }
    current = current.next[0];
    return current !== null && current.value === value ? current : null;
  }

  // 插入节点
  insert(value) {
    const update = new Array(this.maxLevel).fill(null);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i--) {
      while (current.next[i] !== null && current.next[i].value < value) {
        current = current.next[i];
      }
      update[i] = current;
    }

    current = current.next[0];
    if (current === null || current.value !== value) {
      const newLevel = this._randomLevel();
      if (newLevel > this.level) {
        for (let i = this.level; i < newLevel; i++) {
          update[i] = this.head;
        }
        this.level = newLevel;
      }

      const newNode = new SkipListNode(value, newLevel);
      for (let i = 0; i < newLevel; i++) {
        newNode.next[i] = update[i].next[i];
        update[i].next[i] = newNode;
      }
      return true;
    }
    return false;
  }

  // 删除节点
  delete(value) {
    const update = new Array(this.maxLevel).fill(null);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i--) {
      while (current.next[i] !== null && current.next[i].value < value) {
        current = current.next[i];
      }
      update[i] = current;
    }

    current = current.next[0];
    if (current !== null && current.value === value) {
      for (let i = 0; i < this.level; i++) {
        if (update[i].next[i] !== current) {
          break;
        }
        update[i].next[i] = current.next[i];
      }

      while (this.level > 1 && this.head.next[this.level - 1] === null) {
        this.level--;
      }
      return true;
    }
    return false;
  }
}

使用示例

以下是如何使用跳表进行插入、查找和删除操作的示例。

const skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
skipList.insert(9);
skipList.insert(12);

console.log(skipList.search(6)); // 返回节点
console.log(skipList.search(10)); // 返回 null

skipList.delete(6);
console.log(skipList.search(6)); // 返回 null