跳表是一种概率型数据结构，其目的是为了提高在链表上查找元素的速度。跳表通过在多个层级上存储元素的索引，使得查找、插入和删除操作的时间复杂度平均为 O(log n)。
跳表的基本概念
跳表由多层链表组成，每一层都是下面一层的“快捷方式”。最高层（最上面的一层）包含链表中的部分元素，而每一层下面一层都包含更多的元素，直到最低层（最下面的一层）包含了所有的元素。这种设计允许我们在查找过程中跳过大量的节点，从而大大提高查找效率。
节点结构
每个节点除了包含一个或多个元素外，还包含指向同一层其他节点的指针，以及指向下一层节点的指针。这些指针使得我们可以从顶层开始查找，如果目标值不在当前节点，则可以根据比较结果选择向左或向右移动，或者向下移动到下一层继续查找。
层级分配
跳表中的层级并不是固定的，而是根据一定的概率来决定的。通常情况下，新插入的节点会以一定概率被分配到更高层。例如，假设每次增加一层的概率是50%，那么大约一半的新节点会被分配到第二层，四分之一的节点会被分配到第三层，以此类推。这种随机分配的方式保证了跳表的高度是 O(log n) 级别的，从而确保了高效的查找性能。
跳表的实现
跳表的实现可以分为几个主要部分：节点的定义、初始化、插入、删除和查找操作。
节点定义
class SkipListNode {
constructor(key, level) {
this.key = key; // 存储的关键字
this.forward = new Array(level).fill(null); // 指向下一节点的指针数组
}
}初始化跳表
// www.javascriptcn.com code example
class SkipList {
constructor(maxLevel, p) {
this.MAX_LEVEL = maxLevel || 32; // 最大层数
this.P_FACTOR = p || 0.5; // 增加一层的概率
this.head = this.createNode(this.MAX_LEVEL, -1); // 头结点
this.level = 0; // 当前层数
}
createNode(level, key) {
return new SkipListNode(key, level);
}
randomLevel() {
let level = 1;
while (Math.random() < this.P_FACTOR && level < this.MAX_LEVEL) {
level++;
}
return level;
}
}插入操作
// www.javascriptcn.com code example
insert(key) {
const update = new Array(this.MAX_LEVEL).fill(null);
let current = this.head;
for (let i = this.level; i >= 0; i--) {
while (current.forward[i] !== null && current.forward[i].key < key) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current === null || current.key !== key) {
const level = this.randomLevel();
if (level > this.level) {
for (let i = this.level + 1; i <= level; i++) {
update[i] = this.head;
}
this.level = level;
}
current = this.createNode(level, key);
for (let i = 0; i <= level; i++) {
current.forward[i] = update[i].forward[i];
update[i].forward[i] = current;
}
}
}删除操作
// www.javascriptcn.com code example
delete(key) {
const update = new Array(this.MAX_LEVEL).fill(null);
let current = this.head;
for (let i = this.level; i >= 0; i--) {
while (current.forward[i] !== null && current.forward[i].key < key) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current !== null && current.key === key) {
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.head.forward[this.level] === null) {
this.level--;
}
}
}查找操作
// www.javascriptcn.com code example
find(key) {
let current = this.head;
for (let i = this.level; i >= 0; i--) {
while (current.forward[i] !== null && current.forward[i].key < key) {
current = current.forward[i];
}
}
current = current.forward[0];
if (current !== null && current.key === key) {
return true;
}
return false;
}总结
跳表通过在多个层级上存储元素的索引，使得查找、插入和删除操作的时间复杂度平均为 O(log n)。这种数据结构特别适用于需要频繁进行动态插入和删除操作的场景，并且相比于平衡二叉树等其他数据结构，跳表更容易实现和维护。