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

Question

5

我正在处理一个编程问题，遇到了难题。我想构建一种数据结构来将任意整数映射到另一个整数。你可能会说“哈希表！”或“搜索树！”，事实上我已经考虑过这些方法（甚至尝试了一种不太可靠的实现）。但是，有个问题！

每次我插入或移除映射值时，我想对所有大于等于插入/移除值的值进行增量/减量操作（增量/减量为1或某个任意偏移量）。

以下是一个示例:

假设我有两个整数列表，用于此映射中的键和值:

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

现在，如果我添加一个键值对（7, 1），我希望将所有大于或等于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)

使用一些列表/数组和每次插入/删除后的一些处理，这个任务相当容易完成（即遍历值并逐个更改）。

但是，我正在寻找一种更有效的方法，也许不必遍历整个值列表并逐个增加/减少它们。甚至可以延迟增量/减量，直到请求了应该增量/减量的值。

有什么想法吗？

- jsherer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- svick · Accepted Answer

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

关键字的数据结构将仅是关联数组（将其实现为哈希表、自平衡树或跳表均可），从您的关键字到值树中的节点。

值树将是自平衡二叉搜索树（或跳表，请参见下面的编辑）。树中的节点与其值一起关联有一个增量。增量适用于大于或等于特定节点的所有节点，即它适用于它本身和右子树中的所有节点。

当您插入一个值时，您会增加大于或等于要插入的值的所有节点的增量。这会增加整个树中值大于或等于您要插入的值的所有节点的实际值。删除类似，只需用减法代替增量。

当您想读取一个值时，您使用基于关键字的结构在基于值的树中查找节点。然后，您爬到根（您必须为此保留指向树中节点的父指针），并累积来自节点的增量，其值大于或等于开始节点中的值。

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

编辑：对于跳表，管理增量非常容易：当您正在寻找要插入的位置时，在与您要插入的值大于或等于的链接列表中的每个节点中递增增量（这也意味着您正在向下移动一个级别）。删除类似，除了您必须将删除的项保留的任何增量移到右侧。

当您想计算某个节点的实际值时，请尽可能高地爬升到当前项目中，在那里应用增量（一个项目可以多次具有来自插入或删除的增量在不同的级别上，您始终必须使用最高级别中的值），然后向左移动链接列表中的一个节点，并重复该过程，直到到达最左边的项目。

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