我們知道二叉搜索算法能夠高效的查詢數(shù)據(jù)，但是需要一塊連續(xù)的內(nèi)存，而且增刪改效率很低。
跳表，是基于鏈表實(shí)現(xiàn)的一種類似“二分”的算法。它可以快速的實(shí)現(xiàn)增，刪，改，查操作。
我們先來(lái)看一下單向鏈表如何實(shí)現(xiàn)查找
image.png
當(dāng)我們要在該單鏈表中查找某個(gè)數(shù)據(jù)的時(shí)候需要的時(shí)間復(fù)雜度為O(n).
怎么提高查詢效率呢？如果我們給該單鏈表加一級(jí)索引，將會(huì)改善查詢效率。
image.png
如圖所示，當(dāng)我們每隔一個(gè)節(jié)點(diǎn)就提取出來(lái)一個(gè)元素到上一層，把這一層稱作索引，其中的down指針指向原始鏈表。
當(dāng)我們查找元素16的時(shí)候，單鏈表需要比較10次，而加過(guò)索引的兩級(jí)鏈表只需要比較7次。當(dāng)數(shù)據(jù)量增大到一定程度的時(shí)候，效率將會(huì)有顯著的提升。
如果我們?cè)偌佣鄮准?jí)索引的話，效率將會(huì)進(jìn)一步提升。這種鏈表加多級(jí)索引的結(jié)構(gòu)，就叫做跳表。
image.png
跳表的查詢時(shí)間復(fù)雜度可以達(dá)到O(logn)
高效的動(dòng)態(tài)插入和刪除
跳表也可以實(shí)現(xiàn)高效的動(dòng)態(tài)更新，定位到要插入或者刪除數(shù)據(jù)的位置需要的時(shí)間復(fù)雜度為O(logn).
在插入的時(shí)候，我們需要考慮將要插入的數(shù)據(jù)也插入到索引中去。在這里使用的策略是通過(guò)隨機(jī)函數(shù)生成一個(gè)隨機(jī)數(shù)K,然后將要插入的數(shù)據(jù)同時(shí)插入到k級(jí)以下的每級(jí)索引中。
下面是跳表的java代碼實(shí)現(xiàn)
package structs;
import java.util.Random;
public class SkipList {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node();
private Random random = new Random();
public Node find(int value){
Node p = head;
for(int i = levelCount - 1; i >= 0; i--){
while(p.forwards[i] != null && p.forwards[i].data < value){
p = p.forwards[i];
}
}
if(p.forwards[0] != null && p.forwards[0].data == value) return p.forwards[0];
return null;
}
public void insert(int value){
Node p = head;
int level = randomLevel();
Node node = new Node();
node.data = value;
node.maxLevel = level;
Node update[] = new Node[level];
for(int i = level; i >= 0; i--){
while(p.forwards[i] != null && p.forwards[i].data < value){
p = p.forwards[i];
}
update[i] = p;
}
for(int i = 0; i < level; i++){
node.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = node;
}
if(levelCount < level) levelCount = level;
}
public void delete(int value){
Node[] deleteNode = new Node[MAX_LEVEL];
Node p = head;
for(int i = levelCount - 1; i >=0; i--){
while(p.forwards[i] != null && p.forwards[i].data < value){
p = p.forwards[i];
}
deleteNode[i] = p;
}
if(p.forwards[0] != null && p.forwards[0].data == value){
for(int i = levelCount - 1; i >= 0; i--){
if(deleteNode[i] != null && deleteNode[i].forwards[i].data == value){
deleteNode[i].forwards[i] = deleteNode[i].forwards[i].forwards[i];
}
}
}
}
public void printAll(){
Node p = head;
while(p.forwards[0] != null){
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
private int randomLevel() {
int level = 0;
for(int i = 0; i < MAX_LEVEL; i++){
if(random.nextInt()%2 == 1){
level++;
}
}
return level;
}
class Node{
private int data;
private Node[] forwards = new Node[MAX_LEVEL];
private int maxLevel;
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("{data: ");
sb.append(data);
sb.append("; level: ");
sb.append(maxLevel);
sb.append(" }");
return sb.toString();
}
}
}
其中理解了Node節(jié)點(diǎn)的結(jié)構(gòu)，代碼就會(huì)很好理解了。
Node節(jié)點(diǎn)中forwards存儲(chǔ)的是該節(jié)點(diǎn)在各個(gè)level索引的下一個(gè)數(shù)據(jù)節(jié)點(diǎn)；
