建站
咨詢
售后
建站咨詢
新聞中心
查找
假設(shè)有如下這樣一個(gè)有序鏈表：
創(chuàng)新互聯(lián)是一家專注于成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),吳橋網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:吳橋等地區(qū)。吳橋做網(wǎng)站價(jià)格咨詢:13518219792
想要查找 24、43、59，按照順序遍歷，分別需要比較的次數(shù)為 2、4、6
目前查找的時(shí)間復(fù)雜度是 O(N)，如何提高查找效率？
很容易想到二分查找，將查找的時(shí)間復(fù)雜度降到 O(LogN)
具體來(lái)說(shuō)，我們把鏈表中的一些節(jié)點(diǎn)提取出來(lái)，作為索引，類似于二叉搜索樹(shù)，得到如下結(jié)構(gòu)：
這里我們把 10、30、50、80 提取出來(lái)作為一級(jí)索引，這樣搜索的時(shí)候就可以使用二分查找來(lái)減少比較次數(shù)了。
我們還可以再?gòu)囊患?jí)索引提取一些元素出來(lái)，作為二級(jí)索引，變成如下結(jié)構(gòu)：
比如如果想要查找 59，那么搜索路徑就是下面這樣的：
回顧下鏈表的定義：
class ListNode {
private int val;
private ListNode next;
public ListNode(int val){
this.val = val;
this.next = null;
}
}我們?cè)诿恳粋€(gè)節(jié)點(diǎn)的基礎(chǔ)上添加一個(gè) down 指針，用來(lái)指向下一層的節(jié)點(diǎn)
class Node {
private int val;
private ListNode next;
private ListNode down;
public ListNode(int val){
this.val = val;
this.next = null;
this.down = null;
}
}這樣，一個(gè)最簡(jiǎn)單的跳表節(jié)點(diǎn)就定義出來(lái)了。
我們這里說(shuō)的只是最簡(jiǎn)單的實(shí)現(xiàn)，像比如 Redis 的跳表實(shí)現(xiàn)和我們說(shuō)的還是有所不同的，當(dāng)然了，思想都是一致的
所以跳表是什么？簡(jiǎn)單來(lái)說(shuō)，跳表就是支持二分查找的有序鏈表
具體的搜索算法如下：
/* 如果存在 x, 返回 x 所在的節(jié)點(diǎn)， 否則返回 x 的后繼節(jié)點(diǎn) */
private Node find(x){
p = top;
while (true) {
while (p.next.val < x){
p = p.next;
}
if (p.down == null){
return p.next;
}
p = p.down;
}
return null;
}
插入
關(guān)于插入，大家可能很容易想到往最下面一層的有序鏈表中添加數(shù)據(jù)，但是索引該咋辦？索引要不要更新呢？
如果不更新索引，就可能出現(xiàn)兩個(gè)索引節(jié)點(diǎn)之間數(shù)據(jù)非常多的情況，極端情況下跳表就會(huì)退化為單鏈表，從而使得查找效率從 O(LogN) 退化為 O(N)。
所以，我們?cè)诓迦霐?shù)據(jù)的時(shí)候，索引節(jié)點(diǎn)也需要相應(yīng)的改變來(lái)避免查找效率的退化
比較容易想到的做法就是完全重建索引，我們每次插入數(shù)據(jù)后，都把這個(gè)跳表的索引刪掉全部重建。因?yàn)樗饕目臻g復(fù)雜度是 O(N)，即：索引節(jié)點(diǎn)的個(gè)數(shù)是 O(N) 級(jí)別，每次完全重新建一個(gè) O(N) 級(jí)別的索引，時(shí)間復(fù)雜度也是 O(N) 。造成的后果是：為了維護(hù)索引，導(dǎo)致每次插入數(shù)據(jù)的時(shí)間復(fù)雜度變成了 O(N)。
那有沒(méi)有其他效率比較高的方式來(lái)維護(hù)索引呢？
最理想的索引就是在原始鏈表中每隔一個(gè)元素抽取一個(gè)元素做為一級(jí)索引。換種說(shuō)法，我們?cè)谠兼湵碇小倦S機(jī)】的選 n/2 個(gè)元素做為一級(jí)索引是不是也能通過(guò)索引提高查找的效率呢？
當(dāng)然可以，因?yàn)橐话汶S機(jī)選的元素相對(duì)來(lái)說(shuō)都是比較均勻的。如下圖所示，隨機(jī)選擇了 n/2 個(gè)元素做為一級(jí)索引，雖然不是每隔一個(gè)元素抽取一個(gè)，但是對(duì)于查找效率來(lái)講，影響不大，比如我們想找元素 16，仍然可以通過(guò)一級(jí)索引，使得遍歷路徑較少了將近一半。
當(dāng)然了，如果抽取的一級(jí)索引的元素恰好是前一半的元素 1、3、4、5、7、8，那么查找效率確實(shí)沒(méi)有提升，但是這樣的概率太小了。所以我們可以認(rèn)為：當(dāng)原始鏈表中元素?cái)?shù)量足夠大，且抽取足夠隨機(jī)的話，我們得到的索引是均勻的。所以，我們可以維護(hù)一個(gè)這樣的索引：隨機(jī)選 n/2? 個(gè)元素做為一級(jí)索引、隨機(jī)選 n/4? 個(gè)元素做為二級(jí)索引、隨機(jī)選 n/8 個(gè)元素做為三級(jí)索引，依次類推，一直到最頂層索引。這里每層索引的元素個(gè)數(shù)已經(jīng)確定，且每層索引元素選取的足夠隨機(jī)，所以可以通過(guò)索引來(lái)提升跳表的查找效率。
那代碼具體該如何實(shí)現(xiàn)，使得在每次新插入元素的時(shí)候，盡量讓該元素有 1/2 的幾率建立一級(jí)索引、1/4 的幾率建立二級(jí)索引、1/8 的幾率建立三級(jí)索引....呢？
其實(shí)很簡(jiǎn)單啦，搞一個(gè)概率算法就行了（具體是怎么個(gè)概率法這里就不詳細(xì)解釋了），當(dāng)每次有數(shù)據(jù)要插入時(shí)，先通過(guò)概率算法告訴我們這個(gè)元素需要插入到幾級(jí)索引中，然后開(kāi)始維護(hù)索引并把數(shù)據(jù)插入到原始鏈表中。
如下所示，插入新元素 12，假設(shè)概率算法返回的結(jié)果是 4，表示新元素需要插入到 4 級(jí)索引中，同時(shí)，我們還需要建立 3 級(jí)索引、2 級(jí)索引和 1 級(jí)索引（也就是原始有序鏈表）
那插入數(shù)據(jù)時(shí)維護(hù)索引的時(shí)間復(fù)雜度是多少呢？
跳表中，每一層索引都是一個(gè)有序的單鏈表，元素插入到單鏈表的時(shí)間復(fù)雜度為 O(1)，我們索引的高度最多為 LogN，當(dāng)插入一個(gè)元素 x 時(shí)，最壞的情況就是元素 x 需要插入到每層索引中，所以插入數(shù)據(jù)的最壞時(shí)間復(fù)雜度是 O(LogN)，最好的時(shí)間復(fù)雜度是 O(1)。
刪除
跳表刪除數(shù)據(jù)時(shí)，要把索引中對(duì)應(yīng)節(jié)點(diǎn)也要?jiǎng)h掉。如下圖所示，如果要?jiǎng)h除元素 8，需要把原始鏈表中的 8 和第 2、3 級(jí)索引的 8 都刪除掉。
刪除元素的過(guò)程跟查找元素的過(guò)程類似，只不過(guò)在查找的路徑上如果發(fā)現(xiàn)了要?jiǎng)h除的元素 x，則執(zhí)行刪除操作。
跳表中，每一層索引都是一個(gè)有序的單鏈表，單鏈表刪除元素的時(shí)間復(fù)雜度為 O(1)，最多需要?jiǎng)h除 LogN 個(gè)元素（索引層數(shù)為 LogN），所以刪除元素的總時(shí)間包 = 查找元素的時(shí)間 + 刪除 LogN 個(gè)元素的時(shí)間 = O(LogN ) + O(LogN ) = 2O(LogN )，忽略常數(shù)部分，刪除元素的時(shí)間復(fù)雜度為 O(LogN)。
文章名稱：關(guān)于跳表，這么解釋你肯定能聽(tīng)懂
當(dāng)前地址：http://m.5511xx.com/article/cohdgoe.html
