Insert - Jump Lists / Skip Lists

Asked

Viewed 627 times

1

I’m trying to implement the insertion of a node in a jump list, but I’m not making progress with the solution because I don’t know at what point I should add the Node.

So far I’ve made this algorithm:

void insert(Node **head, char *word){
    /*
        Navegar pelo canto superior esquerdo
    */

    for(i = MAX_LEVEL - 1; i>=0; i--){
        if((*head)->skipList[i] == NULL){
            /* Desce um nivel */
        }else{
            /*Percorre o nivel*/
            Node *here = (*head)->skipList[i];
            while(here != NULL){
                /* Caso as palavras forem iguais */
                if(strcmp(here->word, word) == 0){
                    here->count++;
                }else if(strcmp(here->word,word) > 0){
                    /* Caso a palavra actual for maior que a word */
                    /* Volta ao inicio para descer */
                    break;
                }else if(strcmp(here->word, word) < 0){
                    /* Caso a word for maior que a atual */
                    /* Se existir um proximo no */ 
                    if( here->skipList[i] != NULL){
                        /* Se ele for menor que a word */
                        if(strcmp(here->skipList[i]->word, word) <= 0){
                            /* Andamos para a frente*/
                            here = here->skipList[i];
                        }else if(strcmp(here->skipList[i]->word, word) > 0){
                            /* se o next for maior que a word descemos um nivel neste no*/
                            (*head) = here;
                            break;
                        }
                    }else{
                        /* Caso nao exista um no next nesse nivel descemos de nivel neste node*/
                        (*head) = here;
                        break;
                    }
                }
            }
        }
    }
}

The structures I’m using are:

typedef struct node{
    int count;
    int level;
    char word[WORD_SIZE];
    node **skipList;
}Node;

typedef struct header{
    node *skipList[MAX_LEVEL];
}Header;

1 answer

2


Based on that article from Skip List creator William Pugh, I came up with the following implementation in C (C99).

1. Create the data structures:

Node

/**
 * 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__;

Skip

/**
 * 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__;

2. Function to generate the levels of each new node, numbers that are random due to the probabilistic nature of the Skip lists.

/**
 * 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;
}

3. Function to create Node instances for each new node to be inserted in the Skip list.

/**
 * 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;
}

4. Function to create an instance of Skip, which is the Skip list representation.

/**
 * 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;
}

5. Function to fetch a value in the Skip list.

/**
 * 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;
}

Since the function procurar can return an instance of node, then it is interesting to create a function that checks the existence of a certain value in the Skip list and returns only true (!=0) or false (==0).

/**
 * 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;
}

6. Function to insert values in the Skip list.

/**
 * 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;
        }
    }
}

Finally, see the full code, operation and testing on ideone.

It is also published in gist the source code.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.