1206. Design Skiplist 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Skiplist {

    private static class Node {
        private final int val;
        private final Node[] levels;

        public Node(int val) {
            this.val = val;
            this.levels = new Node[LEVEL];
        }
    }

    private static final int LEVEL = 10; // 自底向上 level 递增

    private final Node SENTINEL;

    public Skiplist() {
        this.SENTINEL = new Node(-1);
    }

    public boolean search(int target) {
        Node[] nodes = new Node[LEVEL];
        find(target, nodes);

        return nodes[0].levels[0] != null && nodes[0].levels[0].val == target; // 注意此处需要取 levels[0] 的元素，因为 levels[0].val 才是大于等于 target 的首个元素
    }

    private void find(int target, Node[] nodes) {
        Node curr = SENTINEL;

        // 自顶向下一层一层找，越上层越稀疏，效率越高
        for (int i = LEVEL - 1; i >= 0; i--) {
            // 在每一层从左向右找
            while (curr.levels[i] != null && curr.levels[i].val < target) {
                curr = curr.levels[i]; // 向右前进
            }
            nodes[i] = curr;
        }
    }

    public void add(int num) {
        Node[] nodes = new Node[LEVEL];
        find(num, nodes);

        Node node = new Node(num); // 创建新节点

        // 自底向上插入
        for (int i = 0; i < LEVEL; i++) {
            node.levels[i] = nodes[i].levels[i];
            nodes[i].levels[i] = node;

            if (ThreadLocalRandom.current().nextInt(2) == 0) {
                break;
            }
        }
    }

    public boolean erase(int num) {
        Node[] nodes = new Node[LEVEL];
        find(num, nodes);

        Node node = nodes[0].levels[0];
        if (node == null || node.val != num) {
            return false;
        }

        // 自底向上删除
        for (int i = 0; i < LEVEL && nodes[i].levels[i] == node; i++) {
            nodes[i].levels[i] = nodes[i].levels[i].levels[i];
        }

        return true;
    }

}

References

1206. Design Skiplist
跳表──没听过但很犀利的数据结构 | 三点水