跳跃表

Skip List是一种随机化的数据结构,基于并联的链表,其效率可比拟于二叉查找树.
基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。

时间复杂度O(logn)
空间复杂度o(2n)

跳跃表性质
由很多层构成
每一层是一个有序链表
最底层链表包含所有元素
如果一个元素出现在某一层链表中,那么它在其以下的链表中都会出现
每个节点包含两个指针,一个指向下一个元素,一个指向下一层元素

跳跃表的搜索

insert.jpg

跳跃表的插入

bb72be16-6162-3fee-b680-311f25dd7c3a.jpg

插入时是否上浮由概率决定,1/2概率效率最高

Node的定义

/**
 * Created by zhuxinquan on 17-3-11.
 */
public class SkipListNode implements Comparable {

    private int value;
    private SkipListNode next = null;
    private SkipListNode downNext = null;

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.printf("123");
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public SkipListNode getNext() {
        return next;
    }

    public void setNext(SkipListNode next) {
        this.next = next;
    }

    public SkipListNode getDownNext() {
        return downNext;
    }

    public void setDownNext(SkipListNode downNext) {
        this.downNext = downNext;
    }

    @Override
    public int compareTo(Object o) {
        return this.value > ((SkipListNode)o).value ? 1 : -1;
    }
}

实现

package skiplist;

import java.util.Random;

/**
 * Created by zhuxinquan on 17-3-11.
 */
public class SkipList {

    public int level = 0;
    public SkipListNode top = null;

    public SkipList() {
        this(4);
    }

    //跳跃表的初始化
    public SkipList(int level) {
        this.level = level;
        SkipListNode skipListNode = null;
        SkipListNode temp = top;
        SkipListNode tempDown = null;
        SkipListNode tempNextDown = null;
        int tempLevel = level;
        while(tempLevel -- != 0){
            skipListNode = createNode(Integer.MIN_VALUE);
            temp = skipListNode;
            skipListNode = createNode(Integer.MAX_VALUE);
            temp.setNext(skipListNode);
            temp.setDownNext(tempDown);
            temp.getNext().setDownNext(tempNextDown);
            tempDown = temp;
            tempNextDown = temp.getNext();
        }
        top = temp;
    }

    //随机产生数k，k层下的都需要将值插入
    public int randomLevel(){
        int k = 1;
        while(new Random().nextInt()%2 == 0){
            k ++;
        }
        return k > level ? level : k;
    }

    //查找
    public SkipListNode find(int value){
        SkipListNode node = top;
        while(true){
            while(node.getNext().getValue() < value){
                node = node.getNext();
            }
            if(node.getDownNext() == null){
                //返回要查找的节点的前一个节点
                return node;
            }
            node = node.getDownNext();
        }
    }

    //删除一个节点
    public boolean delete(int value){
        int tempLevel = level;
        SkipListNode skipListNode = top;
        SkipListNode temp = skipListNode;
        boolean flag = false;
        while(tempLevel -- != 0){
            while(temp.getNext().getValue() < value){
                temp = temp.getNext();
            }
            if(temp.getNext().getValue() == value){
                temp.setNext(temp.getNext().getNext());
                flag = true;
            }
            temp = skipListNode.getDownNext();
        }
        return flag;
    }

    //插入一个节点
    public void insert(int value){
        SkipListNode skipListNode = null;
        int k = randomLevel();
        SkipListNode temp = top;
        int tempLevel = level;
        SkipListNode tempNode = null;
        //当在第n行插入后，在第n - 1行插入时需要将第n行backTempNode的DownNext域指向第n - 1的域
        SkipListNode backTempNode = null;
        int flag = 1;
        while(tempLevel-- != k){
            temp = temp.getDownNext();
        }

        tempLevel++;
        tempNode = temp;
        //小于k层的都需要进行插入
        while(tempLevel-- != 0){
            //在第k层寻找要插入的位置
            while(tempNode.getNext().getValue() < value){
                tempNode = tempNode.getNext();
            }
            skipListNode = createNode(value);
            //如果是顶层
            if(flag != 1){
                backTempNode.setDownNext(skipListNode);
            }
            backTempNode = skipListNode;
            skipListNode.setNext(tempNode.getNext());
            tempNode.setNext(skipListNode);
            flag = 0;
            tempNode = tempNode.getDownNext();
        }
    }

    //创建一个节点
    private SkipListNode createNode(int value){
        SkipListNode node =  new SkipListNode();
        node.setValue(value);
        return node;
    }
}