跳表#

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。 跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

class Skiplist {
    int level = 10;
    class Node {
        int value;  // 结点的值
        // 该节点所指向的每层的下一个结点 一共有level个
        Node[] nextNodes = new Node[level];
        public Node (int _value) {
            value = _value;
        }
    }

    // 哨兵
    Node minNode = new Node(-1);
    Random random = new Random();

    /**
     * 工具方法，寻找每层严格小于target的那个结点
     */
    void find(int target, Node[] lastNodes) {
        Node cur = minNode;     // cur指针先指向哨兵
        // 从最顶层开始向下找
        for(int i=level-1; i>=0; i--) { // i代表当前层数
            // 如果指针的该层下一个结点也小于target，则按该层向右移动指针
            while(cur.nextNodes[i] != null && cur.nextNodes[i].value < target) 
                cur = cur.nextNodes[i];
            // 此时cur指向第i层严格小于target的那个结点(也可能是哨兵)
            lastNodes[i] = cur;
        }
    }

    public Skiplist() {}
    
    /**
     * 寻找跳表中是否有值为target的结点
     */
    public boolean search(int target) {
        Node[] lastNodes = new Node[level];
        find(target, lastNodes);
        // 从最底层（完整数据的那一层）来看 严格小于target的结点的下一个结点是存在的 并且值为target
        return lastNodes[0].nextNodes[0] != null && lastNodes[0].nextNodes[0].value == target;
    }
    
    /**
     * 添加结点
     */
    public void add(int num) {
        Node insert = new Node(num);
        Node[] lastNodes = new Node[level];

        find(num, lastNodes);
        // 从底层向上插入数据
        for (int i=0; i<level; i++) {
            // 第0层一定会插入一次数据
            insert.nextNodes[i] = lastNodes[i].nextNodes[i];
            lastNodes[i].nextNodes[i] = insert;
            if(random.nextInt(2) == 0) break;   // 概率终止插入数据
        }
    }
    
    /**
     * 删除结点 成功返回true，失败返回false
     */
    public boolean erase(int num) {
        Node[] lastNodes = new Node[level];
        find(num, lastNodes);
        Node node = lastNodes[0].nextNodes[0];
        if (node == null || node.value != num) return false;
        for (int i = 0; i < level && lastNodes[i].nextNodes[i] == node; i++)  // 从最底层开始删除，判断条件中要比较内存地址而不是值
            lastNodes[i].nextNodes[i] = lastNodes[i].nextNodes[i].nextNodes[i];
        return true;
    }
}