Блог

Я работаю над проблемой программирования и сталкиваюсь с препятствием. Я пытаюсь придумать структуру данных для сопоставления произвольного целого числа с другим целым числом. Возможно, вы склонны сказать «Хэш-таблица!» или «Дерево поиска!», и я действительно думал об этом (и даже попробовал грязную реализацию). Но есть одна загвоздка!

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

Вот пример.

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

 Keys: (1, 6, 18, 21, 24)  
Vals: (2, 1,  3,  0,  4)
  

Теперь, если я добавлю пару ключ-значение (7, 1), я хочу увеличить все значения, большие или равные 1, что приведет к этому:

 Keys: (1, 6, 7, 18, 21, 24)  
Vals: (3, 2, 1,  4,  0,  5)
  

И впоследствии, если я удалю пару ключ-значение (21, 0), это результат:

 Keys: (1, 6, 7, 18, 24)  
Vals: (2, 1, 0,  3,  4)
  

Это довольно тривиально сделать с помощью пары списков / массивов и некоторой обработки после каждой вставки / удаления (т. Е. перебирать значения и изменять их одно за другим).

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

Есть мысли?

Я думаю, что если вам нужно выполнить быстрый поиск по какому-либо ключу и изменить результаты на основе фактических значений, вам понадобятся две структуры данных: одна для ключа, другая для значений.

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

Дерево значений будет самобалансирующимся бинарным деревом поиска (или списком пропусков, см. Редактирование ниже). С узлами в дереве связана дельта вместе с их значением. Дельта применяется ко всем узлам, которые больше или равны определенному узлу, т.е. она применяется к самому себе и ко всем узлам в его правом поддереве.

Когда вы вставляете значение, вы увеличиваете дельту всех узлов, которая больше или равна вставляемому значению. Это увеличивает фактическое значение всех узлов, значение которых больше или равно значению, которое вы вставляете во все дерево. Удаление аналогично, вы просто с увеличением заменяете на уменьшение.

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

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

РЕДАКТИРОВАТЬ: Для списка пропусков управлять дельтами довольно просто: когда вы ищете место для вставки, увеличивайте дельту в каждом сравниваемом вами узле связанного списка, который больше или равен вставляемому значению (что также означает, что вы переходите на один уровень вниз). Удаление аналогично, за исключением того, что вам нужно переместить любые дельты, удерживаемые удаленным элементом, вправо.

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

Способ доступа к узлам также означает, что связанные списки должны быть связаны дважды.