有人可以解释一下skipListSearch()
andskipListInsert()
方法吗?代码来自 Adam Drozdek 的著作Data Structures and Algorithms in C++。在这个skiplist中,插入不需要列表重组,并且生成节点,从而保持不同级别的节点分布足够。
maxLevel = 4
. 对于 15 个元素,所需的一指针节点数为 8,二指针节点数为 4,三指针节点数为 2,四指针节点数为 1。每插入一个节点,就会产生一个介于 1 到 15 之间的随机数 r。如果 r < 9,则插入一级节点。如果 r < 13,则插入第二级节点。如果 r < 15,则为三级节点。如果 r = 15,则生成并插入四级节点。
#include <iostream>
#include <cstdlib>
using namespace std;
const int maxLevel = 4;
template<class T>
class SkipListNode{
public:
SkipListNode(){}
T key;
SkipListNode **next;
};
template<class T>
class SkipList{
public:
SkipList();
bool isEmpty() const;
void choosePowers();
int chooseLevel();
T* skipListSearch(const T&);
void skipListInsert(const T&);
private:
typedef SkipListNode<T> *nodePtr;
nodePtr root[maxLevel];
int powers[maxLevel];
};
template<class T>
SkipList<T>::SkipList(){
for (int i = 0 ; i < maxLevel ; i++){
root[i] = 0;
}
}
template<class T>
bool SkipList<T>::isEmpty() const{
return root[0] == 0;
}
template<class T>
void SkipList<T>::choosePowers(){
powers[maxLevel - 1] = (2 << (maxLevel - 1)) - 1; // 2^maxLevel - 1
for (int i = maxLevel - 2, j = 0 ; i >= 0 ; i--, j++){
powers[i] = powers[i + 1] - (2 << j); // 2^(j + 1)
}
}
template<class T>
int SkipList<T>::chooseLevel(){
int i , r = rand() % powers[maxLevel - 1] + 1;
for ( i = 1 ; i < maxLevel ; i++)
if (r < powers[i])
return i - 1;
return i - 1;
}
template<class T>
T* SkipList<T>::skipListSearch(const T& key){
if (isEmpty()) return 0;
nodePtr prev , curr;
int lvl;
for (lvl = maxLevel - 1 ; lvl >= 0 && !root[lvl]; lvl--); // level
prev = curr = root[lvl];
while(true){
if (key == curr->key)
return &curr->key;
else if (key < curr->key){
if (lvl == 0)
return 0;
else if (curr == root[lvl])
curr = root[--lvl];
else curr = *(prev->next + --lvl);
}
else{
prev = curr;
if (*(curr->next + lvl) != 0)
curr = *(curr->next + lvl);
else{
for (lvl--; lvl >= 0 && *(curr->next + lvl) == 0; lvl--);
if (lvl >= 0)
curr = *(curr->next + lvl);
else return 0;
}
}
}
}
template<class T>
void SkipList<T>::skipListInsert(const T& key){
nodePtr curr[maxLevel] , prev[maxLevel] , newNode;
int lvl , i;
curr[maxLevel - 1] = root[maxLevel - 1];
prev[maxLevel - 1] = 0;
for (lvl = maxLevel - 1; lvl >= 0 ; lvl--){
while (curr[lvl] && curr[lvl]->key < key){ // go to next
prev[lvl] = curr[lvl]; // if smaller
curr[lvl] = *(curr[lvl]->next + lvl);
}
if (curr[lvl] && curr[lvl]->key == key) // dont include
return; // duplicates
if (lvl > 0) // go one level down
if (prev[lvl] == 0){ // if not the lowest
curr[lvl - 1] = root[lvl - 1]; // level , using a link
prev[lvl - 1] = 0; // either from the root
}
else{ // or from the predecessor
curr[lvl - 1] = *(prev[lvl]->next + lvl -1);
prev[lvl - 1] = prev[lvl];
}
}
lvl = chooseLevel(); // generate randomly level for newNode
newNode = new SkipListNode<T>;
newNode->next = new nodePtr[sizeof(nodePtr) * (lvl -1)];
newNode->key = key;
for (i = 0 ; i <= lvl; i++){ // initialize next fields of
*(newNode->next + i) = curr[i]; // newNode and reset to newNode
if (prev[i] == 0) // either fields of the root
root[i] = newNode; // or next fields of newNode's
else *(prev[i]->next + i) = newNode; // predecessors
}
}