Eliminación de un nodo de una lista de salto

Question

Estoy teniendo algunos problemas al eliminar un nodo de una lista de salto. Tengo las siguientes estructuras:

struct Node
{
    int info;
    Node **link_;

    Node(int v, int levels)
    {
        info = v;
        link_ = new Node*[levels];

        for ( int i = 0; i < levels; ++i )
            link_[i] = NULL;
    }
};

struct List
{
    int H; // list height

    Node *Header;

    List()
    {
        Header = new Node(0, maxH);
        H = 1;
    }
};

El problema, creo, está en la función que las búsquedas de un nodo con un valor dado y lo elimina. La función se implementa como esto:

void Remove(int v, List *L)
{
    Node *current = L->Header;

    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
            if ( current->link_[i]->info > v )
                break;
            else if ( current->link_[i]->info == v )
            {
                // Node *del = current->link_[i];
                current->link_[i] = current->link_[i]->link_[i];

                // delete del;
                break;
            }
    }
}

La función funciona bien como está, sin embargo, la lista parece romperse si me elimine el comentario de dos líneas de comentarios. Para las vacaciones me refiero a que el siguiente código de prueba nunca termina:

int main()
{
    srand((unsigned)time(0));

    List *SKL = new List();


    for ( int i = 0; i < 1000000; ++i )
        Insert(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Search(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Remove(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Insert(rand() * rand(), SKL);


    return 0;
}

El problema radica en el último bucle for que las inserciones más valores en la lista. Si esas dos líneas están deshabilitadas, el programa termina en alrededor de 10 segundos. Si les quitar los comentarios, parece entrar en un bucle infinito, ya que ni siquiera terminar en cuestión de minutos. No estoy seguro de si esa es la forma correcta de la eliminación de un nodo de una lista de omisión o no, así que lo pongo mi función de inserción, así:

void Insert(int v, List *L)
{
    // this section just determines the levels the new node will be part of
    int newH = 0;

    int tmp;
    unsigned int rnd = rand() * rand(); 
    do
    {
        tmp = lookup[rnd & 255];
        rnd >>= 8;
        newH += tmp;
    } while ( tmp == 8 );

    if ( newH >= L->H )
        ++L->H;

    // this does the actual insertion
    Node *newNode = new Node(v, L->H);
    Node *current = L->Header;
    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
            if ( current->link_[i]->info >= v )
                break;

        if ( i <= newH )
        {
            newNode->link_[i] = current->link_[i];
            current->link_[i] = newNode;
        }
    }
}

Por lo tanto, mis preguntas son:

1. ¿Por qué la ruptura programa, y ??cómo puedo hacer que funcione, cuando en realidad la eliminación de los nodos quiero borrar de la memoria?
2. ¿Es esta una forma correcta de aplicación de salto listas, o estoy usando un enfoque equivocado?

Answer 1

Hay un problema con el método Remove, como lo has adivinado:

void Remove(int v, List *L)
{
    Node *current = L->Header;

    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
        {
            if ( current->link_[i]->info > v )
            {
                break;
            }
            else if ( current->link_[i]->info == v )
            {
                // Node *del = current->link_[i];
                current->link_[i] = current->link_[i]->link_[i];

                // if (0 == i) delete del;
                break;
            }
        }
    }
}

En aras de ejemplo, vamos a suponer que el nodo que deseamos que aparezca Eliminar en 2 niveles:. 0 y 1

El bucle for en los niveles L->H a 2 no hacer nada.

En el nivel 1 se encuentra el nodo solicitado, y eliminarlo.

En el nivel 0, intentará seguir un puntero al nodo ya eliminada, lo que lleva a un comportamiento indefinido.

Solución:

Sólo borrar el nodo cuando en el nivel 0. Mientras que su en una capa superior, el nodo está siendo referenciado y que necesita para mantenerlo vivo.

Answer 2

En su función para borrar el bucle exterior itera sobre la lista para el recuento del número actual de entradas. Luego, en el bucle se quita uno de esos ntries pero guarda en la iteración en el viejo conde.