漫画:什么是 “跳表” ?


https://mp.weixin.qq.com/s/Ok0laJMn4_OzL-LxPTHawQ
https://www.toutiao.com/a6864412652467126798/

————— 第二天 —————

如何进行二分查找呢?

首先根据数组下标,定位到数组的中间元素:

由于要查找的元素20,大于中间元素12,再次定位到数组右半部分的中间元素:

这一次定位到的元素正好是20,查找成功。

如果数组的长度是n,二分查找的时间复杂度是O(logn),比起从左到右逐个遍历元素进行查找的方式,大大提升了查找性能。

如上图所示,想要定位到链表的中间结点9,是无法直接定位的,需要从头结点开始,顺着next指针,逐个访问下一个结点。

因此,链表这种数据结构并不适用于二分查找。

————————————

常见的图书目录,就像下面这样:

第5章对应的页码是170,因此我们直接翻到书的第170页,就是第5章的内容。

如图所示,在原始链表的基础上,我们增加了一个索引链表。原始链表的每两个结点,有一个结点也在索引链表当中。

这样做有什么好处呢?当我们想要定位到结点20,我们不需要在原始链表中一个一个结点访问,而是首先访问索引链表:

在索引链表找到结点20之后,我们顺着索引链表的结点向下,找到原始链表的结点20:

这个过程,就像是先查阅了图书的目录,再翻到章节所对应的页码。

由于索引链表的结点个数是原始链表的一半,查找结点所需的访问次数也相应减少了一半。

多层次的图书目录,就像下面这样:

如图所示,我们基于原始链表的第1层索引,抽出了第2层更为稀疏的索引,结点数量是第1层索引的一半。

这样的多层索引可以进一步提升查询效率,假如仍然要查找结点20,让我们来演示一下过程:

首先,我们从最上层的索引开始查找,找到该层中仅小于结点20的前置索引结点12:

接下来,我们顺着结点12访问下一层索引,在该层中找到结点20:

最后,我们顺着第1层索引的结点20向下,找到原始链表的结点20:

在这个例子中,由于原始链表的结点数量较少,仅仅需要2层索引。如果链表的结点数量非常多,我们就可以抽出更多的索引层级,每一层索引的结点数量都是低层索引的一半。

假设原始链表有n个结点,那么索引的层级就是log(n)-1,在每一层的访问次数是常量,因此查找结点的平均时间复杂度是O(logn)。这比起常规的查找方式,也就是线性依次访问链表节点的方式,效率要高得多。

但相应的,这种基于链表的优化增加了额外的空间开销。假设原始链表有n个结点,那么各层索引的结点总数是n/2+n/4+n/8+n/16+……2,约等于n。

也就是说,优化之后的数据结构所占空间,是原来的2倍。这是典型的以空间换时间的做法。

假设我们要插入的结点是10,首先我们按照跳表查找结点的方法,找到待插入结点的前置结点(仅小于待插入结点):

接下来,按照一般链表的插入方式,把结点10插入到结点9的下一个位置:

这样是不是插入工作就完成了呢?并不是。随着原始链表的新结点越来越多,索引会渐渐变得不够用了,因此索引结点也需要相应作出调整。

如何调整索引呢?我们让新插入的结点随机“晋升”,也就是成为索引结点。新结点晋升成功的几率是50%。

假设第一次随机的结果是晋升成功,那么我们把结点10作为索引结点,插入到第1层索引的对应位置,并且向下指向原始链表的结点10:

新结点在成功晋升之后,仍然有机会继续向上一层索引晋升。我们再进行一次随机,假设随机的结果是晋升失败,那么插入操作就告一段落了。

小灰说的是什么意思呢?让我们看看下图,新结点10已经晋升到第2层索引,下一次随机的结果仍然是晋升成功,这时候该怎么办呢?

假设我们要从跳表中删除结点10,首先我们按照跳表查找结点的方法,找到待删除的结点:

接下来,按照一般链表的删除方式,把结点10从原始链表当中删除:

这样是不是删除工作就完成了呢?并不是。我们需要顺藤摸瓜,把索引当中的对应结点也一一删除:

刚才的例子当中,第3层索引的结点已经没有了,因此我们把整个第3层删去:

最终的删除结果如下:

  1. 程序中跳表采用的是双向链表,无论前后结点还是上下结点,都各有两个指针相互指向彼此。

  2. 程序中跳表的每一层首位各有一个空结点,左侧的空节点是负无穷大,右侧的空节点是正无穷大。

之所以这样设计,是为了方便代码实现。代码中的跳表就像下图这样:

public class SkipList{

//结点“晋升”的概率
private static final double PROMOTE_RATE = 0.5;
private Node head,tail;
private int maxLevel;

public SkipList() {
    head = new Node(Integer.MIN_VALUE);
    tail = new Node(Integer.MAX_VALUE);
    head.right = tail;
    tail.left = head;
}

//查找结点
public Node search(int data){
    Node p= findNode(data);
    if(p.data == data){
        System.out.println("找到结点:" + data);
        return p;
    }
    System.out.println("未找到结点:" + data);
    return null;
}

//找到值对应的前置结点
private Node findNode(int data){
    Node node = head;
    while(true){
        while (node.right.data!=Integer.MAX_VALUE && node.right.data<=data) {
            node = node.right;
        }
        if (node.down == null) {
            break;
        }
        node = node.down;
    }
    return node;
}

//插入结点
public void insert(int data){
    Node preNode= findNode(data);
    //如果data相同,直接返回
    if (preNode.data == data) {
        return;
    }
    Node node=new Node(data);
    appendNode(preNode, node);
    int currentLevel=0;
    //随机决定结点是否“晋升”
    Random random = new Random();
    while (random.nextDouble() < PROMOTE_RATE) {
        //如果当前层已经是最高层,需要增加一层
        if (currentLevel == maxLevel) {
            addLevel();
        }
        //找到上一层的前置节点
        while (preNode.up==null) {
            preNode=preNode.left;
        }
        preNode=preNode.up;
        //把“晋升”的新结点插入到上一层
        Node upperNode = new Node(data);
        appendNode(preNode, upperNode);
        upperNode.down = node;
        node.up = upperNode;
        node = upperNode;
        currentLevel++;
    }
}

//在前置结点后面添加新结点
private void appendNode(Node preNode, Node newNode){
    newNode.left=preNode;
    newNode.right=preNode.right;
    preNode.right.left=newNode;
    preNode.right=newNode;
}

//增加一层
private void addLevel(){
    maxLevel++;
    Node p1=new Node(Integer.MIN_VALUE);
    Node p2=new Node(Integer.MAX_VALUE);
    p1.right=p2;
    p2.left=p1;
    p1.down=head;
    head.up=p1;
    p2.down=tail;
    tail.up=p2;
    head=p1;
    tail=p2;
}

//删除结点
public boolean remove(int data){
    Node removedNode = search(data);
    if(removedNode == null){
        return false;
    }

    int currentLevel=0;
    while (removedNode != null){
        removedNode.right.left = removedNode.left;
        removedNode.left.right = removedNode.right;
        //如果不是最底层,且只有无穷小和无穷大结点,删除该层
        if(currentLevel != 0 && removedNode.left.data == Integer.MIN_VALUE && removedNode.right.data == Integer.MAX_VALUE){
            removeLevel(removedNode.left);
        }else {
            currentLevel ++;
        }
        removedNode = removedNode.up;
    }

    return true;
}

//删除一层
private void removeLevel(Node leftNode){
    Node rightNode = leftNode.right;
    //如果删除层是最高层
    if(leftNode.up == null){
        leftNode.down.up = null;
        rightNode.down.up = null;
    }else {
        leftNode.up.down = leftNode.down;
        leftNode.down.up = leftNode.up;
        rightNode.up.down = rightNode.down;
        rightNode.down.up = rightNode.up;
    }
    maxLevel --;
}

//输出底层链表
public void printList() {
    Node node=head;
    while (node.down != null) {
        node = node.down;
    }
    while (node.right.data != Integer.MAX_VALUE) {
        System.out.print(node.right.data + " ");
        node = node.right;
    }
    System.out.println();
}

//链表结点类
public class Node {
    public int data;
    //跳表结点的前后和上下都有指针
    public Node up, down, left, right;

    public Node(int data) {
        this.data = data;
    }
}

public static void main(String[] args) {
    SkipList list=new SkipList();
    list.insert(50);
    list.insert(15);
    list.insert(13);
    list.insert(20);
    list.insert(100);
    list.insert(75);
    list.insert(99);
    list.insert(76);
    list.insert(83);
    list.insert(65);
    list.printList();
    list.search(50);
    list.remove(50);
    list.search(50);
}

}

原文作者: 程序员小灰


文章作者: Bob
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Bob !
  目录