漫畫：什么是 “跳表” ？
掃描二維碼
隨時隨地手機看文章
————— 第二天 —————
如何進行二分查找呢？
首先根據(jù)數(shù)組下標，定位到數(shù)組的中間元素：
由于要查找的元素20，大于中間元素12，再次定位到數(shù)組右半部分的中間元素：
這一次定位到的元素正好是20，查找成功。
如果數(shù)組的長度是n，二分查找的時間復雜度是O（logn），比起從左到右逐個遍歷元素進行查找的方式，大大提升了查找性能。
如上圖所示，想要定位到鏈表的中間結點9，是無法直接定位的，需要從頭結點開始，順著next指針，逐個訪問下一個結點。
因此，鏈表這種數(shù)據(jù)結構并不適用于二分查找。
————————————
常見的圖書目錄，就像下面這樣：
第5章對應的頁碼是170，因此我們直接翻到書的第170頁，就是第5章的內(nèi)容。
如圖所示，在原始鏈表的基礎上，我們增加了一個索引鏈表。原始鏈表的每兩個結點，有一個結點也在索引鏈表當中。
這樣做有什么好處呢？當我們想要定位到結點20，我們不需要在原始鏈表中一個一個結點訪問，而是首先訪問索引鏈表：
在索引鏈表找到結點20之后，我們順著索引鏈表的結點向下，找到原始鏈表的結點20：
這個過程，就像是先查閱了圖書的目錄，再翻到章節(jié)所對應的頁碼。
由于索引鏈表的結點個數(shù)是原始鏈表的一半，查找結點所需的訪問次數(shù)也相應減少了一半。
多層次的圖書目錄，就像下面這樣：
如圖所示，我們基于原始鏈表的第1層索引，抽出了第2層更為稀疏的索引，結點數(shù)量是第1層索引的一半。
這樣的多層索引可以進一步提升查詢效率，假如仍然要查找結點20，讓我們來演示一下過程：
首先，我們從最上層的索引開始查找，找到該層中僅小于結點20的前置索引結點12：
接下來，我們順著結點12訪問下一層索引，在該層中找到結點20：
最后，我們順著第1層索引的結點20向下，找到原始鏈表的結點20：
在這個例子中，由于原始鏈表的結點數(shù)量較少，僅僅需要2層索引。如果鏈表的結點數(shù)量非常多，我們就可以抽出更多的索引層級，每一層索引的結點數(shù)量都是低層索引的一半。
假設原始鏈表有n個結點，那么索引的層級就是log(n)-1，在每一層的訪問次數(shù)是常量，因此查找結點的平均時間復雜度是O（logn）。這比起常規(guī)的查找方式，也就是線性依次訪問鏈表節(jié)點的方式，效率要高得多。
但相應的，這種基于鏈表的優(yōu)化增加了額外的空間開銷。假設原始鏈表有n個結點，那么各層索引的結點總數(shù)是n/2+n/4+n/8+n/16+......2，約等于n。
也就是說，優(yōu)化之后的數(shù)據(jù)結構所占空間，是原來的2倍。這是典型的以空間換時間的做法。
假設我們要插入的結點是10，首先我們按照跳表查找結點的方法，找到待插入結點的前置結點（僅小于待插入結點）：
接下來，按照一般鏈表的插入方式，把結點10插入到結點9的下一個位置：
這樣是不是插入工作就完成了呢？并不是。隨著原始鏈表的新結點越來越多，索引會漸漸變得不夠用了，因此索引結點也需要相應作出調(diào)整。
如何調(diào)整索引呢？我們讓新插入的結點隨機“晉升”，也就是成為索引結點。新結點晉升成功的幾率是50%。
假設第一次隨機的結果是晉升成功，那么我們把結點10作為索引結點，插入到第1層索引的對應位置，并且向下指向原始鏈表的結點10：
新結點在成功晉升之后，仍然有機會繼續(xù)向上一層索引晉升。我們再進行一次隨機，假設隨機的結果是晉升失敗，那么插入操作就告一段落了。
小灰說的是什么意思呢？讓我們看看下圖，新結點10已經(jīng)晉升到第2層索引，下一次隨機的結果仍然是晉升成功，這時候該怎么辦呢？
假設我們要從跳表中刪除結點10，首先我們按照跳表查找結點的方法，找到待刪除的結點：
接下來，按照一般鏈表的刪除方式，把結點10從原始鏈表當中刪除：
這樣是不是刪除工作就完成了呢？并不是。我們需要順藤摸瓜，把索引當中的對應結點也一一刪除：
剛才的例子當中，第3層索引的結點已經(jīng)沒有了，因此我們把整個第3層刪去：
最終的刪除結果如下：
1. 程序中跳表采用的是雙向鏈表，無論前后結點還是上下結點，都各有兩個指針相互指向彼此。
2. 程序中跳表的每一層首位各有一個空結點，左側的空節(jié)點是負無窮大，右側的空節(jié)點是正無窮大。
之所以這樣設計，是為了方便代碼實現(xiàn)。代碼中的跳表就像下圖這樣：
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) {
//如果當前層已經(jīng)是最高層，需要增加一層
if (currentLevel == maxLevel) {
addLevel();
}
//找到上一層的前置節(jié)點
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);
}
}—————END—————
喜歡本文的朋友，歡迎關注公眾號 程序員小灰，收看更多精彩內(nèi)容
點個[在看]，是對小灰最大的支持！
免責聲明：本文內(nèi)容由21ic獲得授權后發(fā)布，版權歸原作者所有，本平臺僅提供信息存儲服務。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
