資料結構

1const MAX_LEVEL = 16;
2 
3class SkipNode {
4  next: (SkipNode | null)[];
5  constructor(public key: number, height: number) {
6    this.next = new Array(height).fill(null);
7  }
8}
9 
10class SkipList {
11  private head = new SkipNode(-Infinity, MAX_LEVEL);
12  private level = 1;
13 
14  constructor(private random: () => number = Math.random) {}
15 
16  search(key: number): boolean {
17    let node = this.head;
18    for (let lv = this.level - 1; lv >= 0; lv--) {
19      while (node.next[lv] && node.next[lv]!.key < key) {
20        node = node.next[lv]!;
21      }
22    }
23    const next = node.next[0];
24    return next !== null && next.key === key;
25  }
26 
27  insert(key: number): void {
28    const update: SkipNode[] = new Array(MAX_LEVEL).fill(this.head);
29    let node = this.head;
30    for (let lv = this.level - 1; lv >= 0; lv--) {
31      while (node.next[lv] && node.next[lv]!.key < key) {
32        node = node.next[lv]!;
33      }
34      update[lv] = node;
35    }
36    if (node.next[0]?.key === key) return;
37    let height = 1;
38    while (height < MAX_LEVEL && this.random() < 0.5) height++;
39    this.level = Math.max(this.level, height);
40    const fresh = new SkipNode(key, height);
41    for (let i = 0; i < height; i++) {
42      fresh.next[i] = update[i].next[i];
43      update[i].next[i] = fresh;
44    }
45  }
46 
47  remove(key: number): boolean {
48    const update: SkipNode[] = new Array(MAX_LEVEL).fill(this.head);
49    let node = this.head;
50    for (let lv = this.level - 1; lv >= 0; lv--) {
51      while (node.next[lv] && node.next[lv]!.key < key) {
52        node = node.next[lv]!;
53      }
54      update[lv] = node;
55    }
56    const target = node.next[0];
57    if (!target || target.key !== key) return false;
58    for (let i = 0; i < target.next.length; i++) {
59      update[i].next[i] = target.next[i];
60    }
61    return true;
62  }
63}