Увеличение значений в дереве поиска после вставки пары ключ-значение

Question

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

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

Вот пример.

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

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)

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

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

Есть мысли?

Answer 1

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

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

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

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

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

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

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

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

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