作者 | 小灰

責編 | 王曉曼

來源 | 程序員小灰（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);

}

}