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

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

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

键的数据结构将只是一个关联数组(将其实现为哈希表、自平衡树或跳过列表，这无关紧要)从键到值树中的节点。

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

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

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

根据您选择的自平衡算法的要求进行重新平衡时，您必须小心，因为您必须重新计算某些节点的增量，但这不应影响时间复杂度。

编辑:对于跳过列表，管理增量非常容易:当您正在寻找要插入的位置时，在链接列表中的每个节点中增加增量增量，您要与之进行比较，该增量大于或等于您要插入的值(这也意味着你要下一级)。删除与此类似，不同之处在于您必须将已删除项的任何增量移动到右侧。

当你想计算某个节点的实际值时，在当前项目中尽可能爬高，在那里应用增量(一个项目可以在不同级别上多次从一次插入或删除中获得增量，你总是必须使用值在最高级别)，然后进入链表左侧一个节点并重复该过程，直到到达最左侧的项目。

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