我們知道二叉搜索算法能夠高效的查詢數(shù)據(jù)稀颁，但是需要一塊連續(xù)的內(nèi)存芬失，而且增刪改效率很低。
跳表匾灶，是基于鏈表實現(xiàn)的一種類似“二分”的算法棱烂。它可以快速的實現(xiàn)增，刪阶女，改颊糜，查操作。
我們先來看一下單向鏈表如何實現(xiàn)查找
image.png
當我們要在該單鏈表中查找某個數(shù)據(jù)的時候需要的時間復雜度為O(n).
怎么提高查詢效率呢秃踩？如果我們給該單鏈表加一級索引衬鱼，將會改善查詢效率。
image.png
如圖所示憔杨，當我們每隔一個節(jié)點就提取出來一個元素到上一層鸟赫，把這一層稱作索引，其中的down指針指向原始鏈表消别。
當我們查找元素16的時候惯疙，單鏈表需要比較10次，而加過索引的兩級鏈表只需要比較7次妖啥。當數(shù)據(jù)量增大到一定程度的時候霉颠，效率將會有顯著的提升。
如果我們再加多幾級索引的話荆虱，效率將會進一步提升蒿偎。這種鏈表加多級索引的結(jié)構，就叫做跳表怀读。
image.png
跳表的查詢時間復雜度可以達到O(logn)
高效的動態(tài)插入和刪除
跳表也可以實現(xiàn)高效的動態(tài)更新诉位，定位到要插入或者刪除數(shù)據(jù)的位置需要的時間復雜度為O(logn).
在插入的時候，我們需要考慮將要插入的數(shù)據(jù)也插入到索引中去菜枷。在這里使用的策略是通過隨機函數(shù)生成一個隨機數(shù)K,然后將要插入的數(shù)據(jù)同時插入到k級以下的每級索引中苍糠。
下面是跳表的java代碼實現(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é)點的結(jié)構，代碼就會很好理解了啤誊。
Node節(jié)點中forwards存儲的是該節(jié)點在各個level索引的下一個數(shù)據(jù)節(jié)點岳瞭；
