基本算法连载（6）－Skip List（上）

Skip List号称性能与BST（Binary Sort Tree）树有得一拼，于是把它翻了个底朝天。代码是阐述其思想的最好方式，那我们还是看看它的具体实现（采用Java语言）
public class SkipList {

public static final int NOT_FOUND = -1;
public static final int HEADER_KEY = -2;
public static final int NIL_KEY = Integer.MAX_VALUE;

// optimum probability
public static final float OPT_PROB = 0.25f;
private float myProbability;
// probability to increase level
private int myMaxLevel;
// upper bound of levels
private int myLevel;
// greatest level so far
private SkipListElement
myHeader; // the header element of list

/*
* Constructs a new skip list optimized for the given
* expected upper bound for the number of nodes.
*/

public SkipList(long maxNodes) {
// probability set to 0.25 and maximum level
// of list is depending on expected number of nodes
// (see paper for mathematical background)
this(OPT_PROB,(int)Math.ceil(Math.log(maxNodes)/Math.log(1/OPT_PROB))-1);
}

public SkipList(float probability, int maxLevel) {
myLevel = 0;
myProbability = probability;
myMaxLevel = maxLevel;
// generate the header of the list
myHeader = new SkipListElement(myMaxLevel,HEADER_KEY, 0);

// append the "NIL" element to the header
SkipListElement nilElement = new SkipListElement(myMaxLevel, NIL_KEY, 0);
for (int i=0; i<=myMaxLevel; i++) {
myHeader.forward[i] = nilElement;
}
}

/*
* Generates with help of randomizer the level of a new element.
* The higher a level, the less probable it is (see paper).
* Levels begin at 0 (not at 1 like in the paper).
*/
private int generateRandomLevel() {
int newLevel = 0;
while (newLevel<myMaxLevel &&Math.random()<myProbability ) {
newLevel++;
}
return newLevel;
}

/*
* Inserts a new node into the list.
* If the key already exists, its node is updated to the new value.
*/
public void insert(int searchKey, int value) {
// update pointers to next elements on each level and
// levels run from 0 up to myMaxLevel.
SkipListElement[] update = new SkipListElement[myMaxLevel+1];

// init "cursor" element to header
SkipListElement element = myHeader;

// find place to insert the new node
for (int i=myLevel; i>=0; i--) {
while (element.forward[i].key <searchKey) {
element = element.forward[i];
}
update[i] = element;
}

element = element.forward[0];

// element with same key is overwritten
if (element.key == searchKey) {
element.value = value;
}else{
// or an additional element is inserted
int newLevel = generateRandomLevel();
// element has biggest level seen in this list,update list
if (newLevel > myLevel) {
for (int i=myLevel+1;i<=newLevel; i++) {
update[i] = myHeader;
}

myLevel = newLevel;
}

// allocate new element:
element = new SkipListElement(newLevel,searchKey, value);
for (int i=0; i<=newLevel; i++) {
element.forward[i] = update[i].forward[i];
update[i].forward[i] = element;
}
}

}

/*
* Search for a given key in list. You get the value associated
* with that key or the NOT_FOUND constant.
*/

public int search(int searchKey) {
// init "cursor"-element to header
SkipListElement element = myHeader;

// find element in list:
for (int i=myLevel; i>=0; i--) {
SkipListElement nextElement = element.forward[i];
while (nextElement.key < searchKey) {
element = nextElement;
nextElement = element.forward[i];
}
}

element = element.forward[0];
if (element.key == searchKey) {
return element.value;
}else {
return NOT_FOUND;
}

}

public void delete(int searchKey) {
// update holds pointers to next elements of each level
SkipListElement update[] = new SkipListElement[myMaxLevel+1];

// init "cursor"-element to header
SkipListElement element = myHeader;

// find element in list
for (int i=myLevel; i>=0; i--) {
SkipListElement nextElement = element.forward[i];
while (nextElement.key < searchKey) {
element = nextElement;
nextElement = element.forward[i];
}
update[i] = element;
}

element = element.forward[0];
// element found, so rebuild list without node
if (element.key == searchKey) {
for (int i=0; i<=myLevel; i++) {
if (update[i].forward[i] == element) {
update[i].forward[i] = element.forward[i];
}
}

// element can be freed now
element = null;

// maybe we have to downcorrect the level of the list
while (myLevel>0&& myHeader.forward[myLevel].key==NIL_KEY){
myLevel--;
}
}
}

/*
* inner class
*/

private class SkipListElement {
int key;
int value;
int level;

// array of forward pointers
SkipListElement forward[];

public SkipListElement(int level, int key, int value) {
this.key = key;
this.value = value;
this.level = level;
forward = new SkipListElement[this.level+1];
}
}

}