跳表

跳表：一种动态数据结构，支持快速插入、删除、查找操作。

const MAX_LEVEL = 16;

class Node {

    constructor({
        data = 0,
        level = 1
    } = {}) {
        this.data = data;
        this.level = level;
        this.refer = new Array(this.level);
    }
}

class SkipList {

    constructor() {
        this.head = new Node();
        this.maxLevel = 1;
    }

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

    insert(value) {
        let level = this.randomLevel();
        let p = this.head;
        let path = new Array(level);
        for (let i = level-1; i >= 0; i--) {
            while(p.refer[i] && p.refer[i].data < value) {
                p = p.refer[i];
            }
            path[i] = p;
        }
        let newNode = new Node({data: value, level});
        for (let i = 0; i < level; i++) {
            newNode.refer[i] = path[i].refer[i];
            path[i].refer[i] = newNode;
        }
        if (level > this.maxLevel) {
            this.maxLevel = level;
        }
    }

    find(value) {
        let p = this.head;
        for (let i = this.maxLevel-1; i >= 0; i--) {
            while(p.refer[i] && p.refer[i].data < value) {
                p = p.refer[i];
            }
        }
        if (p.refer[0] && p.refer[0].data === value) {
            return p.refer[0];
        } 
        return null;
    }

    remove(value) {
        let p = this.head;
        let path = new Array(this.maxLevel);
        for(let i = this.maxLevel-1; i >= 0; i--) {
            while(p.refer[i] && p.refer[i].data < value) {
                p = p.refer[i];
            }
            path[i] = p;
        }
        if (p.refer[0] && p.refer[0].data === value) {
            let node = p.refer[0];
            for (let i = 0; i < p.refer[0].level; i++) {
                if (path[i].refer[i] && path[i].refer[i].data === value) {
                    path[i].refer[i] = node.refer[i];
                }
            }
            return node;
        }
        return null;
    }

    printAll() {
        let p = this.head;
        while(p.refer[0]) {
            console.log(p.refer[0].data)
            p = p.refer[0];
        }
    }
}