跳表(skip list)

我们知道二叉搜索算法能够高效的查询数据，但是需要一块连续的内存，而且增删改效率很低。
跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查操作。
我们先来看一下单向链表如何实现查找

image.png

当我们要在该单链表中查找某个数据的时候需要的时间复杂度为O(n).
怎么提高查询效率呢？如果我们给该单链表加一级索引，将会改善查询效率。

image.png
如图所示，当我们每隔一个节点就提取出来一个元素到上一层，把这一层称作索引，其中的down指针指向原始链表。
当我们查找元素16的时候，单链表需要比较10次，而加过索引的两级链表只需要比较7次。当数据量增大到一定程度的时候，效率将会有显著的提升。
如果我们再加多几级索引的话，效率将会进一步提升。这种链表加多级索引的结构，就叫做跳表。
image.png
跳表的查询时间复杂度可以达到O(logn)

高效的动态插入和删除

跳表也可以实现高效的动态更新，定位到要插入或者删除数据的位置需要的时间复杂度为O(logn).
在插入的时候，我们需要考虑将要插入的数据也插入到索引中去。在这里使用的策略是通过随机函数生成一个随机数K,然后将要插入的数据同时插入到k级以下的每级索引中。

下面是跳表的java代码实现

package structs;

import java.util.Random;

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private int levelCount = 1;
    private Node head = new Node();
    private Random random = new Random();

    public Node find(int value){
        Node p = head;
        for(int i = levelCount - 1; i >= 0; i--){
            while(p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
        }
        if(p.forwards[0] != null && p.forwards[0].data == value) return p.forwards[0];
        return null;
    }

    public void insert(int value){
        Node p = head;
        int level = randomLevel();
        Node node = new Node();
        node.data = value;
        node.maxLevel = level;
        Node update[] = new Node[level];
        for(int i = level; i >= 0; i--){
            while(p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
            update[i] = p;
        }
        for(int i = 0; i < level; i++){
            node.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = node;
        }
        if(levelCount < level) levelCount = level;
    }

    public void delete(int value){
        Node[] deleteNode = new Node[MAX_LEVEL];
        Node p = head;
        for(int i = levelCount - 1; i >=0; i--){
            while(p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
            deleteNode[i] = p;
        }
        if(p.forwards[0] != null && p.forwards[0].data == value){
            for(int i = levelCount - 1; i >= 0; i--){
                if(deleteNode[i] != null && deleteNode[i].forwards[i].data == value){
                    deleteNode[i].forwards[i] = deleteNode[i].forwards[i].forwards[i];
                }
            }
        }
    }

    public void printAll(){
        Node p = head;
        while(p.forwards[0] != null){
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }
    private int randomLevel() {
        int level = 0;
        for(int i = 0; i < MAX_LEVEL; i++){
            if(random.nextInt()%2 == 1){
                level++;
            }
        }
        return level;
    }

    class Node{
        private int data;
        private Node[] forwards = new Node[MAX_LEVEL];
        private int maxLevel;

        public String toString(){
            StringBuilder sb = new StringBuilder();
            sb.append("{data: ");
            sb.append(data);
            sb.append("; level: ");
            sb.append(maxLevel);
            sb.append(" }");
            return sb.toString();
        }
    }


}

其中理解了Node节点的结构，代码就会很好理解了。
Node节点中forwards存储的是该节点在各个level索引的下一个数据节点；