【算法基礎(chǔ)】漫畫：什么是 “跳表” ？
—————? 第二天? —————
如何進(jìn)行二分查找呢？
首先根據(jù)數(shù)組下標(biāo)，定位到數(shù)組的中間元素：
由于要查找的元素20，大于中間元素12，再次定位到數(shù)組右半部分的中間元素：
這一次定位到的元素正好是20，查找成功。
如果數(shù)組的長度是n，二分查找的時間復(fù)雜度是O（logn），比起從左到右逐個遍歷元素進(jìn)行查找的方式，大大提升了查找性能。
如上圖所示，想要定位到鏈表的中間結(jié)點9，是無法直接定位的，需要從頭結(jié)點開始，順著next指針，逐個訪問下一個結(jié)點。
因此，鏈表這種數(shù)據(jù)結(jié)構(gòu)并不適用于二分查找。
————————————
常見的圖書目錄，就像下面這樣：
第5章對應(yīng)的頁碼是170，因此我們直接翻到書的第170頁，就是第5章的內(nèi)容。
如圖所示，在原始鏈表的基礎(chǔ)上，我們增加了一個索引鏈表。原始鏈表的每兩個結(jié)點，有一個結(jié)點也在索引鏈表當(dāng)中。
這樣做有什么好處呢？當(dāng)我們想要定位到結(jié)點20，我們不需要在原始鏈表中一個一個結(jié)點訪問，而是首先訪問索引鏈表：
在索引鏈表找到結(jié)點20之后，我們順著索引鏈表的結(jié)點向下，找到原始鏈表的結(jié)點20：
這個過程，就像是先查閱了圖書的目錄，再翻到章節(jié)所對應(yīng)的頁碼。
由于索引鏈表的結(jié)點個數(shù)是原始鏈表的一半，查找結(jié)點所需的訪問次數(shù)也相應(yīng)減少了一半。
多層次的圖書目錄，就像下面這樣：
如圖所示，我們基于原始鏈表的第1層索引，抽出了第2層更為稀疏的索引，結(jié)點數(shù)量是第1層索引的一半。
這樣的多層索引可以進(jìn)一步提升查詢效率，假如仍然要查找結(jié)點20，讓我們來演示一下過程：
首先，我們從最上層的索引開始查找，找到該層中僅小于結(jié)點20的前置索引結(jié)點12：
接下來，我們順著結(jié)點12訪問下一層索引，在該層中找到結(jié)點20：
最后，我們順著第1層索引的結(jié)點20向下，找到原始鏈表的結(jié)點20：
在這個例子中，由于原始鏈表的結(jié)點數(shù)量較少，僅僅需要2層索引。如果鏈表的結(jié)點數(shù)量非常多，我們就可以抽出更多的索引層級，每一層索引的結(jié)點數(shù)量都是低層索引的一半。
假設(shè)原始鏈表有n個結(jié)點，那么索引的層級就是log(n)-1，在每一層的訪問次數(shù)是常量，因此查找結(jié)點的平均時間復(fù)雜度是O（logn）。這比起常規(guī)的查找方式，也就是線性依次訪問鏈表節(jié)點的方式，效率要高得多。
但相應(yīng)的，這種基于鏈表的優(yōu)化增加了額外的空間開銷。假設(shè)原始鏈表有n個結(jié)點，那么各層索引的結(jié)點總數(shù)是n/2+n/4+n/8+n/16+......2，約等于n。
也就是說，優(yōu)化之后的數(shù)據(jù)結(jié)構(gòu)所占空間，是原來的2倍。這是典型的以空間換時間的做法。
假設(shè)我們要插入的結(jié)點是10，首先我們按照跳表查找結(jié)點的方法，找到待插入結(jié)點的前置結(jié)點（僅小于待插入結(jié)點）：
接下來，按照一般鏈表的插入方式，把結(jié)點10插入到結(jié)點9的下一個位置：
這樣是不是插入工作就完成了呢？并不是。隨著原始鏈表的新結(jié)點越來越多，索引會漸漸變得不夠用了，因此索引結(jié)點也需要相應(yīng)作出調(diào)整。
如何調(diào)整索引呢？我們讓新插入的結(jié)點隨機(jī)“晉升”，也就是成為索引結(jié)點。新結(jié)點晉升成功的幾率是50%。
假設(shè)第一次隨機(jī)的結(jié)果是晉升成功，那么我們把結(jié)點10作為索引結(jié)點，插入到第1層索引的對應(yīng)位置，并且向下指向原始鏈表的結(jié)點10：
新結(jié)點在成功晉升之后，仍然有機(jī)會繼續(xù)向上一層索引晉升。我們再進(jìn)行一次隨機(jī)，假設(shè)隨機(jī)的結(jié)果是晉升失敗，那么插入操作就告一段落了。
小灰說的是什么意思呢？讓我們看看下圖，新結(jié)點10已經(jīng)晉升到第2層索引，下一次隨機(jī)的結(jié)果仍然是晉升成功，這時候該怎么辦呢？
假設(shè)我們要從跳表中刪除結(jié)點10，首先我們按照跳表查找結(jié)點的方法，找到待刪除的結(jié)點：
接下來，按照一般鏈表的刪除方式，把結(jié)點10從原始鏈表當(dāng)中刪除：
這樣是不是刪除工作就完成了呢？并不是。我們需要順藤摸瓜，把索引當(dāng)中的對應(yīng)結(jié)點也一一刪除：
剛才的例子當(dāng)中，第3層索引的結(jié)點已經(jīng)沒有了，因此我們把整個第3層刪去：
最終的刪除結(jié)果如下：
1. 程序中跳表采用的是雙向鏈表，無論前后結(jié)點還是上下結(jié)點，都各有兩個指針相互指向彼此。
2.?程序中跳表的每一層首位各有一個空結(jié)點，左側(cè)的空節(jié)點是負(fù)無窮大，右側(cè)的空節(jié)點是正無窮大。
之所以這樣設(shè)計，是為了方便代碼實現(xiàn)。代碼中的跳表就像下圖這樣：
public?class?SkipList{
????//結(jié)點“晉升”的概率
????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;
????}
????//查找結(jié)點
????public?Node?search(int?data){
????????Node?p=?findNode(data);
????????if(p.data?==?data){
????????????System.out.println("找到結(jié)點："?+?data);
????????????return?p;
????????}
????????System.out.println("未找到結(jié)點："?+?data);
????????return?null;
????}
????//找到值對應(yīng)的前置結(jié)點
????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;
????}
????//插入結(jié)點
????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;
????????//隨機(jī)決定結(jié)點是否“晉升”
????????Random?random?=?new?Random();
????????while?(random.nextDouble()?????????????//如果當(dāng)前層已經(jīng)是最高層，需要增加一層
????????????if?(currentLevel?==?maxLevel)?{
????????????????addLevel();
????????????}
????????????//找到上一層的前置節(jié)點
????????????while?(preNode.up==null)?{
????????????????preNode=preNode.left;
????????????}
????????????preNode=preNode.up;
????????????//把“晉升”的新結(jié)點插入到上一層
????????????Node?upperNode?=?new?Node(data);
????????????appendNode(preNode,?upperNode);
????????????upperNode.down?=?node;
????????????node.up?=?upperNode;
????????????node?=?upperNode;
????????????currentLevel++;
????????}
????}
????//在前置結(jié)點后面添加新結(jié)點
????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;
????}
????//刪除結(jié)點
????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;
????????????//如果不是最底層，且只有無窮小和無窮大結(jié)點，刪除該層
????????????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();
????}
????//鏈表結(jié)點類
????public?class?Node?{
????????public?int?data;
????????//跳表結(jié)點的前后和上下都有指針
????????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—————
往期精彩回顧
獲取一折本站知識星球優(yōu)惠券，復(fù)制鏈接直接打開：
https://t.zsxq.com/662nyZF
本站qq群1003271085。
加入微信群請掃碼進(jìn)群（如果是博士或者準(zhǔn)備讀博士請說明）：