一、简介
有序集合通常采用红黑树实现，但是红黑树结构复杂，涉及到节点的旋转等操作，而且删除节点也会变得很复杂。在著名的nosql数据库redis中，采用跳表的方式代替红黑树实现了有序集合
从有序链表入手
一个简单的链表
class node｛
   node next；
   int val；
｝
其结构如图：
由于链表的顺序结构，从链表中查找一个值必须
遍历整个链表，时间复杂度为o（n），例如我们向查找7，即node4，需要4次查找
再加几个指针，更快的查找
如何避免每次查找数据都从表头按顺序遍历？我们可以设想，如果node1有一个直接指向node3，那么我们对7的查找就只需要3次
最终的结构，跳跃表
我们将原有的next指针变更为一个指针数组，这样就允许一个节点有多个节点指向后面的节点，注意这里每一个节点的next［0］指针始终指向null，原因在稍后说明。这个新的结构就是跳跃表了，跳跃表中的操作始终从head节点的最高指针开始
例如查找7：
跳跃表节结构代码为：
／＊＊ ＊ 跳跃表 ＊ 查找，插入，删除 都为 o（logn） ＊ 空间复杂度为o（n） ＊／public class skiplist ｛    ／／头节点    private node head；    ／／记录节点leve的最大值    private int maxlevel；    ／／节点数量    private int size；    ／／抛硬币实验的概率    private static final double probability ＝ 0．5；    ／／节点代码    private static class node｛        int val；        ／／相比链表，这里next指针为一组，而不是一个        arraylist＜node＞ nextnodes ＝ null；／／arraylist与c＋＋中vector相似        public node（int val）｛            this．val ＝ val；            nextnodes ＝ new arraylist＜＞（）；        ｝    ｝    public skiplist（）｛        this．head ＝ new node（integer．min＿value）；        ／／初始化跳表的0层始终为null        this．head．nextnodes．add（null）；／／add（）与c＋＋中push＿back（）相似        this．maxlevel ＝ 0；        this．size ＝ 0；    ｝    ／／添加    public void add（int val）｛    ｝    ／／查找    public boolean contains（int val）｛    ｝    ／／删除    public void remove（int val）｛    ｝｝
那么还有最后一个问题，如何决定每一个节点next数组的大小才能保证olog（n）的时间复杂度？答案是建立每个节点时，都进行抛硬币实验，如果硬币是反面，next数组就“增高”，直到抛出正面的硬币，用代码实现就是：
／／确定新节点的层数int level ＝ 1；／／next指针数组的大小用level表示while（math．random（） ＜ probability）｛    level ＋＋；｝二、实现
查找
结合两个例子分析查找相关的代码
查找7：
再例如查找5：
public boolean contains（int val）｛        if（size ＝＝ 0）｛            return false；        ｝        ／／level表示当前遍历到的层数        ／／每次查找都从头节点的最高层开始        int level ＝ maxlevel；        node curr ＝ head；        while（level ＞ 0）｛            if（curr．nextnodes．get（level） ！＝ null）｛                ／／同一层下个节点值小于目标值，向右遍历                if（curr．nextnodes．get（level）．val ＜ val）｛                    curr ＝ curr．nextnodes．get（level）；                ／／同一层下个节点值大于目标值，向下遍历（层数减一）                ｝else if（curr．nextnodes．get（level）．val ＞ val）｛                    level －－；                ｝else if（curr．nextnodes．get（level）．val ＝＝ val）｛                    return true；                ｝            ／／本层遍历到了末尾（指向null），向下遍历（层数减一）            ｝else｛                level －－；            ｝        ｝        return false；    ｝添加
添加过程相对复杂，大概分为一下几个步骤：
进行抛硬币实验，确定新节点的层数，如果层数比头节点层数大，则还需要加高头节点
从头节点最高层开始，寻找新节点最高层插入的位置
层数降低，因为新节点每一层都需要与前后节点相连
public void add（int val）｛        if（contains（val））｛            return；        ｝        ／／1． 确定新节点的层数        int level ＝ 1；        while（math．random（） ＜ probability）｛            level ＋＋；        ｝        ／／如果新节点的层数大于最高层数，先将头节点增高        if（level ＞ maxlevel）｛            int increment ＝ level － maxlevel；            while（increment－－ ＞ 0）｛                head．nextnodes．add（null）；            ｝            maxlevel ＝ level；        ｝        ／／创建新节点        node newnode ＝ new node（val）；        ／／2． 寻找新节点最高层的插入位置        node curr ＝ findinsertionoftoplevel（val， level）；        while （level ＞ 0）｛            ／／新节点与后边的节点连接            if（curr．nextnodes．get（level） ！＝ null）｛                newnode．nextnodes．add（0， curr．nextnodes．get（level））；            ｝else｛                newnode．nextnodes．add（0， null）；            ｝            ／／当前节点的next指向新节点            curr．nextnodes．set（level， newnode）；            ／／3． 层数降低，新节点的每层都要与前后节点相连            level －－；            ／／寻找下一层需要连接的地方            while（curr．nextnodes．get（level） ！＝ null ＆＆ curr．nextnodes．get（level）．val ＜ val）｛                curr ＝ curr．nextnodes．get（level）；            ｝        ｝        ／／最后，保证节点的0层始终为null        newnode．nextnodes．add（0， null）；        size ＋＋；    ｝    private node findinsertionoftoplevel（int newval， int level）｛        int currlevel ＝ maxlevel；        node curr ＝ head；        while（currlevel ＞＝ level）｛            ／／尝试向右寻找            if（curr．nextnodes．get（currlevel） ！＝ null ＆＆ curr．nextnodes．get（currlevel）．val ＜ newval）｛                curr ＝ curr．nextnodes．get（currlevel）；            ｝else｛                ／／向下寻找                currlevel －－；            ｝        ｝        return curr；    ｝删除
删除就是插入的逆过程，分为两个步骤：
从最高层开始，寻找需要删除的节点
找到要删除的节点的前驱节点，断开被删节点每一层与前后节点连接的指针
public void remove（int val）｛        if（contains（val））｛            ／／一定存在，每次都从head的最高层开始遍历            node curr ＝ head；            int level ＝ maxlevel；            ／／1． 寻找要删除的节点            while （level ＞ 0）｛                if（curr．nextnodes．get（level） ！＝ null）｛                    ／／向右寻找                    if（curr．nextnodes．get（level）．val ＜ val） ｛                        curr ＝ curr．nextnodes．get（level）；                    ｝else if（curr．nextnodes．get（level）．val ＝＝ val）｛ ／／找到了                        curr ＝ curr．nextnodes．get（level）；                        break；                    ｝else｛                        ／／本层没有找到，到下一层找                        level －－；                    ｝                ｝else｛                    ／／本层没有找到，到下一层找                    level －－；                ｝            ｝            ／／2． 寻找要删除的节点的前驱节点，每一层都要断开与被删除节点的连接            while（level ＞ 0）｛                node pre ＝ head；                ／／向右寻找                while（pre．nextnodes．get（level）．val ！＝ val）｛                    pre ＝ pre．nextnodes．get（level）；                ｝                pre．nextnodes．set（level， curr．nextnodes．get（level））；                level －－；            ｝            size －－；        ｝    ｝遍历
我们注意到，跳表的节点至少为一层，next［1］指针始终指向比它大的下一个节点，所以遍历跳跃表和遍历链表一样简单，如图：
代码与遍历链表相同，这里不在赘述。
同时，还可以结合查找的相关代码，轻松找出比某个值大的所有节点
三、双向跳跃表
还记得始终指向null的next［0］指针吗？如果上述实现的跳跃表的基础上，将每一个next［0］指针指向前驱节点，并添加一个尾节点，就是双向跳表了，方便做反向遍历，例如找出比某个值小的所有节点
注意尾节点始终只有第0层
双向跳跃表实现与跳跃表基本类似，只是增加了反向指针，具体实现见双向跳跃表
作者：好吃懒做贪玩东
编辑：西瓜媛

---