Блог

В учебнике CLRS «Введение в алгоритм» есть такой параграф на стр. 258.

Мы можем удалить элемент за O (1) раз, если списки двусвязны. (Обратите внимание, что CHAINED-HASH-DELETE принимает в качестве входных данных элемент x, а не его ключ k, так что нам не нужно сначала искать x. Если хэш-таблица поддерживает удаление, то ее связанный список должен быть двусвязным, чтобы мы могли быстро удалить элемент. Если бы списки были только односвязными, то для удаления элемента x нам сначала пришлось бы найти x в списке, чтобы мы могли обновить атрибут next предшественника x. В односвязных списках как удаление, так и поиск будут иметь одинаковое асимптотическое время выполнения).

Что меня озадачивает в этих больших круглых скобках, я не смог понять его логику. В двусвязном списке все равно нужно найти x, чтобы удалить его, чем это отличается от односвязного списка? Пожалуйста, помогите мне разобраться в этом!

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

Предположим, у вас есть простой связанный список :

 v ----> w ----> x ----> y ----> z
                |
            you're here
  

Теперь, если вы удалите x , вам нужно подключиться w к y , чтобы сохранить ваш список связанным. Вам нужно получить доступ w и указать ему, чтобы он указывал на y (вы хотите иметь w ----> y ). Но вы не можете получить доступ w из x , потому что это просто связано! Таким образом, вы должны просмотреть весь свой список, чтобы найти w за O (n) операций, а затем указать ему ссылку на y . Это плохо.

Тогда предположим, что вы двусвязны :

 v <---> w <---> x <---> y <---> z
                |
            you're here
  

Круто, вы можете получить доступ к w и y отсюда, так что вы можете соединить их ( w <---> y ) в операции O (1)!

Мне кажется, что часть хэш-таблицы в этом в основном отвлекающий маневр. Реальный вопрос таков: «можем ли мы удалить текущий элемент из связанного списка за постоянное время, и если да, то как?»

Ответ таков: это немного сложно, но по сути да, мы можем — по крайней мере, обычно. Нам не (обычно) приходится обходить весь связанный список, чтобы найти предыдущий элемент. Вместо этого мы можем поменять местами данные между текущим элементом и следующим элементом, а затем удалить следующий элемент.

Единственное исключение из этого — когда / если нам нужно / захочется удалить последний элемент в списке. В этом случае нет следующего элемента для замены. Если вам действительно нужно это сделать, нет реального способа избежать поиска предыдущего элемента. Однако есть способы, которые, как правило, работают, чтобы избежать этого — один из них заключается в том, чтобы завершить список сигналом вместо нулевого указателя. В этом случае, поскольку мы никогда не удаляем узел со значением sentinel, нам никогда не приходится иметь дело с удалением последнего элемента в списке. Это оставляет нам относительно простой код, что-то вроде этого:

 template <class key, class data>
struct node {
    key k;
    data d;
    node *next;
};

void delete_node(node *item) {
    node *temp = item->next;
    swap(item->key, temp->key);
    swap(item->data, temp->data);
    item ->next = temp->next;
    delete temp;
}
  

В целом вы правы — опубликованный вами алгоритм принимает сам элемент в качестве входных данных, а не только его ключ:

Обратите внимание, что CHAINED-HASH-DELETE принимает в качестве входных данных элемент x, а не его ключ k, так что нам не нужно сначала искать x.

У вас есть элемент x — поскольку это двусвязный список, у вас есть указатели на предшественника и преемника, поэтому вы можете исправить эти элементы в O (1) — с односвязным списком был бы доступен только преемник, поэтому вам пришлось бы искать предшественника в O (n).

предположим, вы хотите удалить элемент x, используя список двусвязей, вы можете легко соединить предыдущий элемент x со следующим элементом x . таким образом, нет необходимости просматривать весь список, и он будет в O (1).

Find(x) в общем случае, это O (1) для связанной хэш-таблицы — не имеет значения, используете ли вы односвязные списки или двусвязные списки. Они идентичны по производительности.

Если после выполнения Find(x) вы решите, что хотите удалить возвращенный объект, вы обнаружите, что внутри хэш-таблицы может потребоваться повторный поиск вашего объекта. Обычно все равно будет O (1), и это не имеет большого значения, но вы обнаруживаете, что удаляете ужасно много, вы можете сделать немного лучше. Вместо того, чтобы возвращать элемент пользователя напрямую, верните указатель на базовый хэш-узел. Затем вы можете воспользоваться некоторыми внутренними структурами. Итак, если в этом случае вы выбрали двусвязный список в качестве способа выражения вашей цепочки, то в процессе удаления нет необходимости пересчитывать хэш и выполнять повторный поиск в коллекции — вы можете пропустить этот шаг. У вас достаточно информации, чтобы выполнить удаление прямо с того места, где вы сидите. Необходимо соблюдать дополнительную осторожность, если отправляемый вами узел является головным узлом, поэтому для обозначения местоположения вашего узла в исходном массиве может использоваться целое число, если это заголовок связанного списка.

Компромисс заключается в гарантированном пространстве, занимаемом дополнительным указателем, по сравнению с возможным более быстрым удалением (и немного более сложным кодом). На современных настольных компьютерах пространство обычно очень дешево, так что это может быть разумным компромиссом.

С точки зрения кодирования: для реализации этого можно использовать unordered_map на c .

 unordered_map<value,node*>mp;
  

Где node* — указатель на структуру, хранящую ключ, левый и правый указатели!

Как использовать:

Если у вас есть значение v и вы хотите удалить этот узел, просто сделайте:

1. Получите доступ к этим узлам со значением like mp[v] .

2. Теперь просто направьте его левый указатель на узел справа.

И вуаля, готово.

(Просто напомним, что в C unordered_map требуется среднее значение O (1) для доступа к определенному сохраненному значению.)

Просматривая учебник, я тоже запутался в той же теме (является ли «x» указателем на элемент или самим элементом), а затем в конечном итоге наткнулся на этот вопрос. Но после прохождения вышеупомянутого обсуждения и повторного обращения к учебнику, я думаю, что в книге «x» неявно предполагается как «узел», а его возможные атрибуты — «ключ», «следующий».

Некоторые строки образуют учебник..

1)CHAINED-HASH-INSERT(T,x) вставьте x в начало списка T[h (x.key)]

2) Если бы списки были только односвязными, то для удаления элемента x нам сначала пришлось бы найти x в списке T[h (x.key)], чтобы мы могли обновить следующий атрибут предшественника x.

Следовательно, мы можем предположить, что указатель на элемент дан, и я думаю, что Фезвез дал хорошее объяснение заданному вопросу.

Учебник неверен. Первый элемент списка не имеет полезного указателя «предыдущий», поэтому необходим дополнительный код, чтобы найти и разорвать связь с элементом, если он первый в цепочке (обычно 30% элементов являются началом их цепочки, если N = M, (при отображении N элементов в M слотов; каждый слот имеет отдельную цепочку.))

Редактировать:

Лучшим способом, чем использование обратной ссылки, является использование указателя на ссылку, которая указывает на нас (обычно -> следующая ссылка предыдущего узла в списке)

 struct node {
   struct node **pppar;
   struct node *nxt;
   ...
   }
  

удаление тогда становится:

 *(p->pppar) = p->nxt;
  

И приятной особенностью этого метода является то, что он одинаково хорошо работает для первого узла в цепочке (чей указатель pppar указывает на некоторый указатель, который не является частью узла.

ОБНОВЛЕНИЕ 2011-11-11

Поскольку люди не понимают моей точки зрения, я попытаюсь проиллюстрировать. В качестве примера есть хэш-таблица table (в основном массив указателей) и множество узлов one , two , three один из которых должен быть удален.

     struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one->next = two , two-next = three, three->next = NULL;
                one->prev = NULL, two->prev = one, three->prev = two;


    /* How to delete element one :*/
    if (one->prev == NULL) {
            table[31] = one->next;
            }
    else    {
            one->prev->next = one->next
            }
    if (one->next) {
            one->next->prev = one->prev;
            }
  

Теперь очевидно, что код obove равен O (1), но есть кое-что неприятное: ему все еще нужен array , и индекс 31 , поэтому в большинстве случаев узел является «самодостаточным», и указателя на узел достаточно, чтобы удалить его из своей цепочки, заисключением table случаев, когда это первый узел в его цепочке; тогда потребуется дополнительная информация, чтобы найти 31 и,,.

Далее рассмотрим эквивалентную структуру с указателем на указатель в качестве обратной ссылки.

     struct node {
            struct node *next;
            struct node **ppp;
            char payload[43];
            };

    struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one-next = two , two-next = three, three->next = NULL;
                one->ppp = amp;table[31], two->ppp = amp;one->next, three->ppp = amp;two-next;

    /* How to delete element one */
    *(one->ppp) = one->next;
    if (one->next) one->next->ppp = one->ppp;
  

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

Часто в сценарии {prev,next} особых случаев удается избежать, добавляя фиктивный узел в начало двусвязного списка; Но это тоже необходимо выделить и инициализировать.