跳跃表原理

Skip lists are a data structure that can be used in place of balanced trees.
Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

public class SkipList {
    private static class SkipListNode {
        int data;

        SkipListNode[] next;

        SkipListNode(int d, int level) {
            data = d;
            next = new SkipListNode[level + ];
        }
    }

    private int maxLevel;

    SkipListNode header;

    private static final int INFINITY = Integer.MAX_VALUE;

    SkipList(int maxLevel) {
        this.maxLevel = maxLevel;
        header = new SkipListNode(, maxLevel);
        SkipListNode sentinel = new SkipListNode(INFINITY, maxLevel);
        for (int i = ; i <= maxLevel; i++)
            header.next[i] = sentinel;
    }

    public boolean find(int key) {
        SkipListNode current = header;

        for (int i = maxLevel; i >= ; i--) {
            SkipListNode next = current.next[i];
            while (next.data < key) {
                current = next;
                next = current.next[i];
            }
        }
        current = current.next[];

        if (current.data == key)
            return true;
        else
            return false;
    }

    public void insert(int searchKey, int newValue) {
        SkipListNode[] update = new SkipListNode[maxLevel + ];
        SkipListNode current = header;

        for (int i = maxLevel; i >= ; i--) {
            SkipListNode next = current.next[i];
            while (next.data < searchKey) {
                current = next;
                next = current.next[i];
            }
            update[i] = current;
        }
        current = current.next[];
        if (current.data == searchKey)
            current.data = newValue;
        else {
            int v = generateRandomLevel();
            SkipListNode node = new SkipListNode(newValue, maxLevel);
            for (int i = ; i <= v; i++) {
                node.next[i] = update[i].next[i];
                update[i].next[i] = node;
            }
            update = null;
        }
    }

    private int generateRandomLevel() {
        int newLevel = ;
        while (newLevel < maxLevel && Math.random() < 0.5)
            newLevel++;
        return newLevel;
    }

    public boolean delete(int searchKey) {
        SkipListNode[] update = new SkipListNode[maxLevel + ];
        SkipListNode current = header;
        for (int i = maxLevel; i >= ; i--) {
            SkipListNode next = current.next[i];
            while (next.data < searchKey) {
                current = next;
                next = current.next[i];
            }
            update[i] = current;
        }
        current = current.next[];
        if (current.data == searchKey) {
            for (int i = ; i <= maxLevel; i++) {
                if (update[i].next[i] == current) {
                    update[i].next[i] = current.next[i];
                    current.next[i] = null;
                } else
                    current.next[i] = null;
            }

            return true;
        }

        return false;
    }

    public static void main(String[] args) {

    }
}