• 发文
  • 评论
  • 微博
  • 空间
  • 微信

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

程序媛驿站 2020-05-25 10:29 发文

一、简介

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

双向跳跃表实现与跳跃表基本类似,只是增加了反向指针,具体实现见双向跳跃表

作者:好吃懒做贪玩东

编辑:西瓜媛


声明:本文为OFweek维科号作者发布,不代表OFweek维科号立场。如有侵权或其他问题,请及时联系我们举报。
2
评论

评论

    相关阅读

    暂无数据

    程序媛驿站

    带你领略计算机学科之美。内容包括...

    举报文章问题

    ×
    • 营销广告
    • 重复、旧闻
    • 格式问题
    • 低俗
    • 标题夸张
    • 与事实不符
    • 疑似抄袭
    • 我有话要说
    确定 取消

    举报评论问题

    ×
    • 淫秽色情
    • 营销广告
    • 恶意攻击谩骂
    • 我要吐槽
    确定 取消

    用户登录×

    请输入用户名/手机/邮箱

    请输入密码