间隙漫画又叫什么（漫画什么是跳表）

作者 | 小灰

责编 | 王晓曼

来源 | 程序员小灰（ID：chengxuyuanxiaohui）

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

如何进行二分查找呢？

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

由于要查找的元素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 ;

}

//找到值对应的前置结点

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 == ) {

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==) {

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 == ){

return false;

}

int currentLevel=0;

while (removedNode != ){

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 == ){

leftNode.down.up = ;

rightNode.down.up = ;

}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 != ) {

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);

}

}

,