当前位置：首页 > JavaScript

跳表实现 js

2026-04-05 08:37:15JavaScript

跳表（Skip List）实现（JavaScript）

跳表是一种概率性的数据结构，允许快速搜索、插入和删除操作，时间复杂度为O(log n)。以下是JavaScript实现跳表的核心代码和解释：

跳表节点类

每个节点包含值、层级和指向下一个节点的指针数组。

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

跳表类

初始化时设置最大层级和概率因子（通常为0.5）。

跳表实现 js

class SkipList {
  constructor() {
    this.maxLevel = 16; // 最大层级
    this.p = 0.5;      // 节点晋升概率
    this.head = new SkipListNode(null, this.maxLevel);
    this.level = 1;    // 当前有效层级
  }
}

随机层级生成

决定新节点应该出现在哪些层级。

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

搜索操作

从最高层开始查找，逐步降层直到找到目标值。

跳表实现 js

search(value) {
  let current = this.head;
  for (let i = this.level - 1; i >= 0; i--) {
    while (current.next[i] && current.next[i].value < value) {
      current = current.next[i];
    }
  }
  current = current.next[0];
  return current && 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] && current.next[i].value < value) { current = current.next[i]; } update[i] = current; }

const level = this._randomLevel(); if (level > this.level) { for (let i = this.level; i < level; i++) { update[i] = this.head; } this.level = level; }

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


### 删除操作
1. 查找需要更新的节点
2. 逐层解除目标节点的链接
3. 必要时降低跳表层数
```javascript
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] && current.next[i].value < value) {
      current = current.next[i];
    }
    update[i] = current;
  }

  current = current.next[0];
  if (!current || current.value !== value) return false;

  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]) {
    this.level--;
  }
  return true;
}

复杂度分析

空间复杂度：O(n)
时间复杂度：
- 搜索：平均O(log n)，最坏O(n)
- 插入：平均O(log n)，最坏O(n)
- 删除：平均O(log n)，最坏O(n)

使用示例

const list = new SkipList();
list.insert(3);
list.insert(6);
list.insert(7);
list.insert(9);
console.log(list.search(6)); // 返回节点
list.delete(6);
console.log(list.search(6)); // null

这个实现包含了跳表的核心功能，可以根据需要扩展更多方法如范围查询等。注意跳表的性能依赖于随机层级生成，保持合理的晋升概率是关键。

标签: js