当前位置：首页 > JavaScript

跳表实现 js

2026-01-31 16:25:31JavaScript

跳表（Skip List）实现

跳表是一种概率性数据结构，允许快速查找、插入和删除操作，时间复杂度为O(log n)。以下是JavaScript实现跳表的基本代码框架：

跳表实现 js

节点类定义

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

跳表类定义

class SkipList {
  constructor(maxLevel, p) {
    this.maxLevel = maxLevel;
    this.p = p;
    this.level = 0;
    this.header = new SkipListNode(null, maxLevel);
  }

  randomLevel() {
    let level = 0;
    while (Math.random() < this.p && level < this.maxLevel) {
      level++;
    }
    return level;
  }
}

插入操作

insert(value) {
  const update = new Array(this.maxLevel + 1).fill(null);
  let current = this.header;

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

  current = current.forward[0];
  if (current === null || current.value !== value) {
    const newLevel = this.randomLevel();
    if (newLevel > this.level) {
      for (let i = this.level + 1; i <= newLevel; i++) {
        update[i] = this.header;
      }
      this.level = newLevel;
    }

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

搜索操作

search(value) {
  let current = this.header;
  for (let i = this.level; i >= 0; i--) {
    while (current.forward[i] !== null && current.forward[i].value < value) {
      current = current.forward[i];
    }
  }
  current = current.forward[0];
  return current !== null && current.value === value;
}

删除操作

delete(value) {
  const update = new Array(this.maxLevel + 1).fill(null);
  let current = this.header;

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

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

    while (this.level > 0 && this.header.forward[this.level] === null) {
      this.level--;
    }
    return true;
  }
  return false;
}

使用示例

const skipList = new SkipList(16, 0.5);
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
console.log(skipList.search(6)); // true
skipList.delete(6);
console.log(skipList.search(6)); // false