JS如何实现跳表？跳表的插入和删除

next

class SkipListNode {
    constructor(value, level) {
        this.value = value;
        // next是一个数组，存储指向不同层级下一个节点的引用
        this.next = new Array(level + 1).fill(null);
    }
}

class SkipList {
    constructor(maxLevel = 16, probability = 0.5) {
        this.maxLevel = maxLevel; // 跳表的最大层级
        this.probability = probability; // 决定节点层级的概率因子
        this.level = 0; // 当前跳表的最高层级
        // 头节点，其值通常为null或-Infinity，用于简化边界处理
        this.head = new SkipListNode(null, maxLevel); 
    }

    // 随机生成新节点的层级
    // 这是一个核心机制，决定了跳表的性能
    randomLevel() {
        let lvl = 0;
        while (Math.random() < this.probability && lvl < this.maxLevel) {
            lvl++;
        }
        return lvl;
    }

    // 插入操作
    insert(value) {
        // update数组用来存储每一层需要更新的节点
        // update[i] 表示在第i层，新节点应该插入到update[i]的后面
        const update = new Array(this.maxLevel + 1).fill(null);
        let current = this.head;

        // 从最高层开始向下查找，找到插入位置
        for (let i = this.level; i >= 0; i--) {
            while (current.next[i] && current.next[i].value < value) {
                current = current.next[i];
            }
            update[i] = current; // 记录下当前层的前一个节点
        }

        // 如果值已经存在，通常选择不插入或更新，这里选择不插入
        if (current.next[0] && current.next[0].value === value) {
            // console.log(`Value ${value} already exists.`);
            return false;
        }

        // 确定新节点的层级
        const newLevel = this.randomLevel();

        // 如果新节点的层级高于当前跳表的最高层级，需要更新head的next指针
        // 并且update数组中超出当前level的部分，其前驱节点就是head
        if (newLevel > this.level) {
            for (let i = this.level + 1; i <= newLevel; i++) {
                update[i] = this.head;
            }
            this.level = newLevel; // 更新跳表的最高层级
        }

        // 创建新节点
        const newNode = new SkipListNode(value, newLevel);

        // 调整指针，将新节点插入到相应的位置
        for (let i = 0; i <= newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
        return true;
    }

    // 删除操作
    delete(value) {
        const update = new Array(this.maxLevel + 1).fill(null);
        let current = this.head;

        // 从最高层开始向下查找，找到要删除的节点
        for (let i = this.level; 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) {
            // console.log(`Value ${value} not found.`);
            return false;
        }

        // 调整指针，跳过要删除的节点
        for (let i = 0; i <= this.level; i++) {
            // 如果update[i]的下一个节点是要删除的节点，就跳过它
            if (update[i].next[i] === current) {
                update[i].next[i] = current.next[i];
            }
        }

        // 删除后，检查是否需要降低跳表的最高层级
        // 从最高层开始检查，如果head的next指针指向null，说明该层已空
        while (this.level > 0 && this.head.next[this.level] === null) {
            this.level--;
        }
        return true;
    }

    // 查找操作（通常也会实现，但这里不作为重点）
    search(value) {
        let current = this.head;
        for (let i = this.level; 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;
    }

    // 打印跳表（辅助调试）
    print() {
        console.log("Skip List:");
        for (let i = this.level; i >= 0; i--) {
            let current = this.head.next[i];
            let levelStr = `Level ${i}: Head -> `;
            while (current) {
                levelStr += `${current.value} -> `;
                current = current.next[i];
            }
            levelStr += "NULL";
            console.log(levelStr);
        }
    }
}

// 示例用法：
// const skipList = new SkipList();
// skipList.insert(3);
// skipList.insert(6);
// skipList.insert(7);
// skipList.insert(9);
// skipList.insert(12);
// skipList.insert(1);
// skipList.print();
// console.log("Searching for 7:", skipList.search(7)); // true
// console.log("Searching for 5:", skipList.search(5)); // false
// skipList.delete(7);
// skipList.print();
// console.log("Searching for 7 after deletion:", skipList.search(7)); // false
// skipList.delete(1);
// skipList.print();
// skipList.delete(100); // Value 100 not found.

Math.random() < probability

probability

update

update[i]

update[i].next[i]

update[i].next[i]

update

level

head

head

null

-Infinity

maxLevel

next

head.next[this.level]

null

this.level