Implementação de SkipList em linguagem C (C99)

skip.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

/**
 * Definindo a porcentagem de changes para
 * executação do laço que cria o nível do nó.
 * Nesse caso, 50% de chance que o laço executará uma vez.
 */
#define P 0.5

/**
 * Definindo o número máximo de níveis que poderão existir.
 */
#define MAX_LEVEL 5

/**
 * Definindo o tamanho do arranjo que armazena o valor de cada nó.
 */
#define WORD_SIZE 30

/**
 * Definindo o valor para strings null.
 */
#define NULL_STRING "null"

/**
 * Definição da estrutura de dados dos nós.
 */
typedef struct node {

    /* Valor do nó.
     */
    char word[WORD_SIZE];

    /* Nível do nó.
     */
    int level;

    /* Arranjo de ponteiros para os nós que vem à frente deste.
     */
    struct node** forward;
}__node__;

/**
 * Definição da estrutura de dados da skip list.
 */
typedef struct skip {

    /* Nó-cabeçalho da skip list.
     */
    struct node* header;

    /* Nível do cabeçalho da skip list.
     */
    int level;

}__skip__;

/**
 * Gerar números aletórios entre 0 e 1.
 */
float randomize(){
    float _result = 0.0;

    _result = ((float)rand()) / (float)(RAND_MAX);

    return _result;
}

/**
 * Criar uma novo nível aleatório.
 */
int random_level(){
    int _result = 1;

    while(randomize() < P && _result < MAX_LEVEL){
        _result++;
    }

    return _result;
}

/**
 * Testa o criador de níveis aletórios.
 */
void random_level_teste(){
    printf("\n\nRANDOM LEVEL TESTE\n");

    int _counter = 0;
    while(_counter < 100){
        printf("nivel aletorio %d\n", random_level());

        _counter++;

    }
}

/**
 * Criar uma nova instância de node.
 */
struct node* criar_node(int level, char* word){
    struct node* _result = 0;

    /* Alocando memória para armazenar uma instância de node.
     */
    _result = malloc(sizeof(struct node));

    /* Atribuindo ao novo nó o seu level.
     */
    _result->level = level;

    /* Alocando memória para o arranjo forward.
     */
    _result->forward = malloc( (level + 1) * sizeof(struct node*));

    /* Configurar todas as posições do arranjo forward com 0 (null).
     */
    int _index = 0;
    while(_index < (_result->level + 1)){

        _result->forward[_index] = 0;

        _index++;
    }

    /* Atribuindo o valor do novo nó.
     */
    strcpy(_result->word, word);

    return _result;
}

/**
 * Testa a função criadora de nós.
 */
void criar_node_teste(){
    printf("\n\nCRIAR NODE TESTE\n");

    int _level = random_level();
    printf("Nivel aletorio para criar novo node: %d\n", _level);

    char _word[WORD_SIZE];
    strcpy(_word, "fabiojose");

    printf("Valor para criar novo node: %s\n", _word);

    struct node* _node = criar_node(_level, _word);

    printf("Nivel aletorio do node criado: %d\n", _node->level);
    printf("Valor do node criado: %s\n", _node->word);
}

/**
 * Criar uma nova skip list.
 */
struct skip* criar_skip(){
    struct skip* _result = 0;

    /* Alocando memória para a instância de skip.
     */
    _result = malloc(sizeof(struct skip));

    /* Criando o nó header, sendo seu nível o valor máximo.
     */
    _result->header = criar_node(MAX_LEVEL, NULL_STRING);

    /* Configurando level da skip list como sendo zero.
     */
    _result->level = 0;

    return _result;
}

/**
 * Testa criador de skip lists.
 */
void criar_skip_teste(){
    printf("\n\nCRIAR SKIP TESTE\n");

    struct skip* _skip = criar_skip();
    printf("Nivel da skip list: %d\n", _skip->level);

    struct node* _header = _skip->header;
    printf("Nivel do node header da skip list: %d\n", _header->level);
    printf("Nivel maximo configurado: %d\n", MAX_LEVEL);

    printf("Valor do node header da skip list: %s\n", _header->word);

}

/**
 * Procurar na skip list por toSearch e retornar o nó onde esse valor está.
 */
struct node* procurar(struct skip* sl, char* toSearch){

    /* x incialmente aponta para o header da skip list.
     */
    struct node* x = sl->header;

    /* Nível inicial.
     */
    int _level = x->level;

    /* Iniciar pelo topo, descendo até o nível mais baixo.
     */
    for(int i = _level; i >= 0; i--){
        /* Enquando forward[i] não for null E forward[i]->word menor que toSearch
         */
        while(x->forward[i] != 0 && strcmp(x->forward[i]->word, toSearch) < 0){
            /* Andar para frente.
             */
            x = x->forward[i];
        }
    }

    /* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
     * - x está apontando para o valor que estava sendo procurado;
     * - x está apontando para um valor maior que o procurado;
     * - x está null.
     */
    x = x->forward[0];

    /* Retornar o valor de x.
     */
    return (struct node*)x;
}

/**
 * Verificar se um determinado valor existe na skip list.
 * 0 = o valor não existe na skipt
 * qualquer valor diferente de 0, o valor existe na skip list.
 */
int existe(struct skip* sl, char* toSearch){
    int _result = 0;

    struct node* _encontrado = procurar(sl, toSearch);
    if(_encontrado != 0){
        if(strcmp(_encontrado->word, toSearch) == 0){
            /* Existe.
             */
            _result = 1;
        }
    }

    return _result;
}

/**
 * Testa a função de procura.
 */
void procurar_teste(){
    printf("\n\nPROCURAR TESTE\n");

    struct skip* _skip = criar_skip();
    char _toSearch[WORD_SIZE];
    strcpy(_toSearch, "fabiojose");

    struct node* _encontrado = procurar(_skip, _toSearch);
    if(_encontrado != 0){
        if(strcmp(_encontrado->word, _toSearch) == 0){
            printf("Encontrado o valor: %s", _toSearch);
        } else {
            printf("Nao foi encontrado o valor: %s", _toSearch);
        }
    } else {
        printf("Nao foi encontrado o valor: %s", _toSearch);
    }
}

/**
 * Inserir word na skip list.
 */
void inserir(struct skip* sl, char* word){

    /* Alocando memória para o arranjo que armazena
     * os nós que deverão ser atualizados.
     */
    struct node** update = malloc( (MAX_LEVEL + 1) * sizeof(struct node*) );

    /* x aponta para o cabeçalho da skip list.
     */
    struct node* x = sl->header;

    /* Nível inicial.
     */
    int _level = x->level;

    /* Iniciar pelo topo, descendo até o nível mais baixo.
     */
    for(int i = _level; i >= 0; i--){
        /* Enquando forward[i] não for null E forward[i]->word menor que toSearch
         */
        while(x->forward[i] != 0 && strcmp(x->forward[i]->word, word) < 0){
            /* Andar para frente.
             */
            x = x->forward[i];
        }
        /* Guardar em update o nó que será atualizado.
         */
        update[i] = x;
    }

    /* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
     * - x está apontando para o valor que estava sendo procurado;
     * - x está apontando para um valor maior que o procurado;
     * - x está null.
     */
    x = x->forward[0];

    /* Caso x seja null ou x->word não seja igual à word
     */
    if(x == 0 || strcmp(x->word, word) != 0){

        /* Obter o nível do nó novo.
         */
        int _newLevel = random_level();

        /* Caso o nível do nó novo seja maior que o nível da skip list
         */
        if(_newLevel > _level){
            /* Atualizar o arranjo updade para que aponte para o header da skip list
             * em todas as posições entre seu nível e o nível do nó novo.
             */
            for(int _index = _level + 1; _index <= _newLevel; _index++){
                update[_index] = sl->header;
            }

            /* Atualizar o nível da skip list.
             */
            sl->level = _newLevel;
        }

        /* Criar a instância do nó novo para.
         */
        x = criar_node(_newLevel, word);

        /* Inserindo o nó novo na skip list.
         */
        for(int _index = 0; _index <= _newLevel; _index++){
            x->forward[_index] = update[_index]->forward[_index];
            update[_index]->forward[_index] = x;
        }
    }
}

/**
 * Testar a inserção na skip list.
 */
void inserir_teste(){
    printf("\n\nINSERIR TESTE\n");

    struct skip* _skip = criar_skip();

    char _word[WORD_SIZE];

    /* Inserção 0
     */
    printf("\n\nInsercao 0\n");
    strcpy(_word, "fabiojose");
    printf("Inserir na skip list: %s\n", _word);
    inserir(_skip, _word);
    if(existe(_skip, _word)){
        printf("Encontrado o valor inserido: %s\n", _word);
    } else {
        printf("Nao foi encontrado o valor inserido: %s\n", _word);
    }

    /* Inserção 1
     */
    printf("\n\nInsercao 1\n");
    strcpy(_word, "serranegra");
    printf("Inserir na skip list: %s\n", _word);
    inserir(_skip, _word);
    if(existe(_skip, _word)){
        printf("Encontrado o valor inserido: %s\n", _word);
    } else {
        printf("Nao foi encontrado o valor inserido: %s\n", _word);
    }

    /* Procurar novamente a Inserção 0
     */
    printf("\n\nProcurar novamente a Insercao 0\n");
    strcpy(_word, "fabiojose");
    if(existe(_skip, _word)){
        printf("Encontrado o valor inserido: %s\n", _word);
    } else {
        printf("Nao foi encontrado o valor inserido: %s\n", _word);
    }

    /* Inserção 2
     */
    printf("\n\nInsercao 2\n");
    strcpy(_word, "aguamineral");
    printf("Inserir na skip list: %s\n", _word);
    inserir(_skip, _word);
    if(existe(_skip, _word)){
        printf("Encontrado o valor inserido: %s\n", _word);
    } else {
        printf("Nao foi encontrado o valor inserido: %s\n", _word);
    }

    /* Novamente executar Inserção 0
     */
    printf("\n\nNovamente executar Insercao 0\n");
    strcpy(_word, "fabiojose");
    printf("Inserir na skip list: %s\n", _word);
    inserir(_skip, _word);
    if(existe(_skip, _word)){
        printf("Encontrado o valor inserido: %s\n", _word);
    } else {
        printf("Nao foi encontrado o valor inserido: %s\n", _word);
    }
}

/**
 * Testa todas as funções.
 */
void testar(){

    /* Testar criador de níveis aletórios.
     */
    random_level_teste();

    /* Testar criador de nós.
     */
    criar_node_teste();

    /* Testar criador de skip list.
     */
    criar_skip_teste();

    /* Testar a procura na skip list.
     */
    procurar_teste();

    /* Testar a inserção na skip list.
     */
    inserir_teste();
}

int main(int argc, char* argv[]){

    /* Fornecendo uma "semente" ao gerador de números aletórios.
     */
    srand((time(0)));

    /* Testes.
     */
    testar();

    return 0;
}

Faltou só a remoção, né... Rsrs
Essa está dando um trabalhão aqui.
Acho que facilitaria se eu tivesse optado por algo "duplamente" ligado