跳跃表---用简单的方式实现有序集合

用户3946442

发布于 2022-04-11 18:52:59

3960

发布于 2022-04-11 18:52:59

文章被收录于专栏：程序媛驿站程序媛驿站

一、简介

有序集合通常采用红黑树实现，但是红黑树结构复杂，涉及到节点的旋转等操作，而且删除节点也会变得很复杂。在著名的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层

双向跳跃表实现与跳跃表基本类似，只是增加了反向指针，具体实现见双向跳跃表（https://github.com/wdw87/repoZ/blob/master/src/wdw/classic/structures/SkipList/DoubleSkipList.java）

作者：好吃懒做贪玩东

编辑：西瓜媛

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-05-24，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js

编程算法

本文分享自程序媛驿站微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

node.js

编程算法

登录后参与评论

0 条评论

热度