search — Skip List Explanation (Структуры данных и алгоритмы на C ++, Адам Дроздек)

Может кто-нибудь, пожалуйста, объясните skipListSearch() а также skipListInsert() метод? Код взят из книги Адама Дроздека Структуры данных и алгоритмы в C ++.
В этом пропускаемом списке вставка не требует реструктуризации списка, и узлы генерируются так, чтобы распределение узлов на разных уровнях оставалось адекватным.

maxLevel = 4, Для 15 элементов необходимо количество одноходовых указателей
узлов — восемь, узлов с двумя указателями — четыре, узлов с тремя указателями — два, а узлов с четырьмя указателями — один. Каждый раз, когда вставляется узел, генерируется случайное число r от 1 до 15. Если г < 9, затем вставляется узел первого уровня. Если г < 13, узел второго уровня вставлен. Если г < 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
}
}