JavaScript 跳表的应用

跳表是一种基于链表的高效查找数据结构，它通过在多个层级上存储数据来提高查找效率。跳表的设计灵感来源于平衡树，但实现起来比平衡树更简单。跳表在许多场景下有着广泛的应用，特别是在需要频繁插入和删除操作的场景中。

跳表的基本概念

跳表由多层链表组成，最底层是一个普通的有序链表，上面每一层都是下面一层的“稀疏”版本。每一层的链表节点都包含一个向前的指针，用于快速跳过部分节点。最顶层的链表只有少数几个节点，可以用来快速定位到目标区间。

节点设计

每个节点除了存储数据外，还包含多个指向其他节点的指针。这些指针根据层级的不同而不同，最底层的节点包含一个向后的指针，而高层级的节点则包含向前的指针。这种设计使得跳表可以在查找时进行“跳跃”。

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

层级选择

在插入新节点时，需要决定该节点应该出现在哪些层级上。这通常通过随机函数来实现，例如抛硬币决定是否进入更高一级。这样可以保证跳表的高度是随机的，从而达到较好的性能。

function randomLevel() {
    let level = 1;
    while (Math.random() < 0.5 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

跳表的插入操作

插入操作包括三个步骤：找到正确的位置、更新索引、插入新节点。首先，通过从最高层开始遍历找到合适的位置；然后，在这一位置上插入新节点，并更新所有涉及的索引；最后，将新节点添加到最底层的链表中。

// www.javascriptcn.com code example
function insert(skipList, key) {
    let update = new Array(MAX_LEVEL + 1);
    let p = skipList.header;
    for (let i = skipList.level; i >= 0; i--) {
        while (p.forward[i] != null && p.forward[i].key < key) {
            p = p.forward[i];
        }
        update[i] = p;
    }

    let level = randomLevel();
    if (level > skipList.level) {
        for (let i = skipList.level + 1; i <= level; i++) {
            update[i] = skipList.header;
        }
        skipList.level = level;
    }

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

跳表的查找操作

查找操作也从最高层开始，逐步向下移动，直到找到目标值或确定目标值不存在为止。通过这种方式，查找操作的时间复杂度接近 O(log n)。

// www.javascriptcn.com code example
function search(skipList, key) {
    let p = skipList.header;
    for (let i = skipList.level; i >= 0; i--) {
        while (p.forward[i] != null && p.forward[i].key < key) {
            p = p.forward[i];
        }
    }
    p = p.forward[0];
    if (p != null && p.key === key) {
        return p;
    } else {
        return null;
    }
}

跳表的删除操作

删除操作与插入操作类似，也是从最高层开始，找到目标节点并删除之。需要注意的是，删除操作后可能需要调整跳表的高度。

// www.javascriptcn.com code example
function deleteNode(skipList, key) {
    let update = new Array(MAX_LEVEL + 1);
    let p = skipList.header;
    for (let i = skipList.level; i >= 0; i--) {
        while (p.forward[i] != null && p.forward[i].key < key) {
            p = p.forward[i];
        }
        update[i] = p;
    }

    p = p.forward[0];
    if (p != null && p.key === key) {
        for (let i = 0; i <= skipList.level; i++) {
            if (update[i].forward[i] != p) {
                break;
            }
            update[i].forward[i] = p.forward[i];
        }

        while (skipList.level > 0 && skipList.header.forward[skipList.level] == null) {
            skipList.level--;
        }
    }
}

总结

跳表作为一种高效的动态数据结构，适用于需要频繁进行插入、删除和查找操作的场景。通过合理的设计和实现，跳表能够在保持较好性能的同时，简化代码逻辑。在实际应用中，可以根据具体需求调整跳表的高度和层数，以达到最佳效果。