在插入键值对后增加搜索树中的值

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

我认为，如果您需要通过某个键进行快速查找，并根据实际值修改结果，则需要两个数据结构：一个用于键，一个用于值。

密钥的数据结构将只是一个关联数组（将它实现为散列表，自平衡树或跳过列表，它无关紧要）从您的密钥到树中的节点值。

值为树将成为一个自平衡二叉搜索树（或跳过列表，请参阅下面的编辑）。树中的节点与它们相关的增量及其值。增量适用于大于或等于特定节点的所有节点，即适用于其自身和其右子树中的所有节点。

当您插入一个值时，您将增加所有节点的增量大于或等于您要插入的值。这会增加所有节点的实际值，其值大于或等于您在整个树中插入的值。删除是相似的，你只需用递减替换增量。

当您想要读取值时，可以使用基于键的结构在基于值的树中查找节点。然后你爬到根节点（你必须保留指向树中父节点的指针），并从节点累积增量，其值大于或等于你开始节点的值。

由于您必须重新计算某些节点的增量，因此您在选择自平衡算法时必须小心进行重新平衡，但这不会影响时间复杂度。

编辑：对跳转列表，管理三角洲是很容易的：当你正在寻找插入的地方，增量三角洲链表的每一个节点你比较大于或等于该你插入的价值（这也意味着你要下降一级）。删除是类似的，除了你必须将被删除的项目的任何增量移动到右边。

当您想要计算某个节点的实际值时，请尽可能地在当前项目中进行爬升，然后在其中应用增量（一个项目可以在不同级别上多次插入或删除一个增量，您总是必须使用最高级别的值），然后将链接列表中的一个节点放到左侧，并重复该过程，直到到达最左侧的项目。

您访问节点的方式也意味着链接列表必须双向链接。