Удаление узла из списка пропуска

Question

У меня проблемы с удалением узла из списка пропусков. У меня есть следующие структуры:

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

Проблема, я думаю, заключается в функции, которая ищет узел с заданным значением, а затем удаляет его. Функция реализована так:

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

Функция работает нормально, как есть, однако список, кажется, ломается, если я раскомментирую две закомментированные строки. Под прерыванием я подразумеваю, что следующий тестовый код никогда не завершается:

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

Проблема заключается в последнем цикле for, который вставляет больше значений в список. Если эти две строки закомментированы, программа завершается примерно через 10 секунд. Если я раскомментирую их, кажется, что они входят в бесконечный цикл, так как он даже не заканчивается за несколько минут. Я не уверен, является ли это правильным способом удаления узла из списка пропусков или нет, поэтому я также публикую свою функцию вставки:

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

Итак, мои вопросы:

1. Почему программа ломается и как я могу заставить ее работать, фактически удаляя узлы, которые я хочу удалить из памяти?
2. Это правильный способ реализации списков пропуска, или я использую неправильный подход?

Answer 1

Существует проблема с методом Remove, как вы уже догадались:

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

Для примера, давайте предположим, что узел, который мы хотим удалить, появляется на 2 уровнях: 0 и 1.

Цикл for на уровнях L->H до 2 ничего не делает.

На уровне 1 он найдет запрошенный узел и удалит его.

На уровне 0 он будет пытаться следовать указателю на уже удаленный узел, что приведет к неопределенному поведению.

Решение:

Удалять узел можно только на уровне 0. Пока вы находитесь на верхнем уровне, на узел все еще ссылаются, и вы должны поддерживать его в рабочем состоянии.

Answer 2

В вашей функции Remove ваш внешний цикл перебирает список для подсчета текущего количества записей. Затем в цикле вы удаляете один из этих ntries, но продолжаете итерацию по старому счету.