Реализация сбалансированного SkipList.

Статьи по реализации SkipList есть, но почти нет ничего по реализации сбалансированного SkipList.
В статье http://eternallyconfuzzled.com/tuts/skip.html приводится такая реализация — вот
если бы еще понять ее. Сам автор статьи по интересующему меня вопросу выразился так: "Удаление в
балансированном skip list, мягко говоря, боль в заднице." И он полностью убедил меня в этом.

Ниже я привожу минимально необходимый код — определения структур, функцию вставки jsw_insert и
функцию удаления jsw_remove.

#include <limits.h>

/* Max key for signed integers */
#define MAX_KEY INT_MAX

struct jsw_node
{
int data;
struct jsw_node *r;
struct jsw_node *d;
};

struct jsw_skip
{
struct jsw_node *head;
struct jsw_node *bottom;
struct jsw_node *tail;
};

jsw_node* new_node(int key, jsw_node *right, jsw_node *down)
{
jsw_node* node = new jsw_node;
if( !node ) return NULL;
node -> data = key;
node -> r = right;
node -> d = down;
return node;
}

struct jsw_skip *new_skip()
{
struct jsw_skip *skip = new jsw_skip;

if( skip == NULL ) return NULL;

skip -> bottom = new_node( MAX_KEY, NULL, NULL );
skip -> tail = new_node( MAX_KEY, NULL, NULL );
skip -> head = new_node( MAX_KEY, skip -> tail, skip -> bottom );

skip -> bottom -> r = skip -> bottom;
skip -> bottom -> d = skip -> bottom;
skip -> tail -> r = skip -> tail;

return skip;
}

int jsw_insert(jsw_skip *skip, int key )
{
jsw_node *it;

/* Set search params for insertion */
skip -> bottom -> data = key;

for(it = skip -> head; it != skip -> bottom; it = it -> d ) // цикл идет по уровням
{
while( key > it -> data ) it = it -> r;

/* Raise column
if( it -> data > it -> d -> r -> r -> data )
{
it -> r = new_node( it -> data, it -> r, it -> d -> r -> r );
it -> data = it -> d -> r -> data;

}
else if( it -> d == skip -> bottom ) return 0;
}

/* Grow list if necessary */
if( skip -> head -> r != skip -> tail )
skip -> head = new_node( MAX_KEY, skip -> tail, skip -> head );

return 1;
}

struct j_walker
{
struct jsw_node *it; /* Current item */
struct jsw_node *prev; /* Previous gap */
struct jsw_node *next; /* Next gap */
struct jsw_node *save; /* Temporary holder */
int lastb; /* Previous key bottom */
int lastu; /* Previous key up */
};

static struct j_walker w; /* Variables for deletion */

static void fix_gap (struct jsw_skip *skip )
{
w.save = w.it -> r;

if(w.save -> data == w.save -> d -> r -> data || w.next == skip -> bottom)
{
/* Lower next column */
w.it -> r = w.save -> r;
w.it -> data = w.save -> data;
free( w.save );
}
else
{
/* Raise first of next gap, lower next column */
w.it -> data = w.save -> d -> data;
w.save -> d = w.save -> d -> r;
}
}

static void last_gap(struct jsw_skip *skip )
{
if ( w.prev -> data <= w.prev -> d -> r -> data )
{
/* Lower prev column */
if( w.next == skip -> bottom ) w.lastb = w.prev -> data;

w.prev -> r = w.it -> r;
w.prev -> data = w.it -> data;
free( w.it );
w.it = w.prev;
}
else
{
/* Raise last of prev gap, lower prev column */
if( w.prev -> data == w.prev -> d -> r -> r -> data )
w.save = w.prev -> d -> r;
else
w.save = w.prev -> d -> r -> r;

w.prev -> data = w.save -> data;
w.it -> d = w.save -> r;
}
}

static int rebalance(struct jsw_skip *skip )
{
w.next = w.it -> d;

if( w.it -> data == w.next -> r -> data )
{
if( w.it -> data != w.lastu ) fix_gap( skip );
else last_gap( skip );
}
else if( w.next == skip -> bottom ) return 0;

w.lastu = w.it -> data;

return 1;
}

int jsw_remove(struct jsw_skip *skip, int key)
{
/* Set search params for deletion */
skip -> bottom -> data = key;
w.lastu = skip -> head -> data;
w.it = skip -> head -> d;

for ( ; w.it != skip -> bottom; w.it = w.next)
{
while( key > w.it -> data )
{
w.prev = w.it;
w.it = w.it -> r;
}

if( rebalance( skip ) == 0 ) return 0;
}

/* Fix columns taller than 1 */
w.it = skip -> head -> d;

for ( ; w.it != skip -> bottom; w.it = w.it -> d )
{
while ( key > w.it -> data ) w.it = w.it -> r;

if ( key == w.it -> data ) w.it -> data = w.lastb;
}

/* Shrink if necessary */
if( skip -> head -> d -> r == skip -> tail )
{
w.save = skip -> head;
skip -> head = w.save -> d;
free( w.save );
}

return 1;
}

Все мои вопросы связаны с функцией удаления — jsw_remove.

1) Что делает в функции last_gap следующий фрагмент кода:

else
{
/* Raise last of prev gap, lower prev column */
if( w.prev -> data == w.prev -> d -> r -> r -> data )
w.save = w.prev -> d -> r;
else
w.save = w.prev -> d -> r -> r;

w.prev -> data = w.save -> data;
w.it -> d = w.save -> r;
}

2) Что делает в функции jsw_remove следующий фрагмент кода:

/* Fix columns taller than 1 */
w.it = skip -> head -> d;

for ( ; w.it != skip -> bottom; w.it = w.it -> d )
{
while ( key > w.it -> data ) w.it = w.it -> r;

if ( key == w.it -> data ) w.it -> data = w.lastb;
}

3) Почему нужны переменные lastb и lastu ?

Совершенно замечательный алгоритм вставки — просто конфетка ! Но вот удаление!
Я себе плешь проел, пытаясь понять авторский вариант функции удаления jsw_remove.
На ветвь else в фунции last_gap я вообще не смог попасть.

Может кто нибудь подсобит или подскажет источник