jsh*_*rer 5 language-agnostic tree hash list data-structures
我正在研究编程问题,并遇到了障碍.我试图想出一个数据结构来将任意整数映射到另一个整数.你可能倾向于说"哈希表!" 或"搜索树!",我实际上已经想到了这些(甚至尝试了一个脏实现).但是有一个问题!
每次我从映射中插入或删除一个值时,我还想增加/减少(减去一个或某个任意偏移量)所有大于或等于插入/删除值的值.
这是一个例子.
假设我有两个整数列表,我将用于此映射中的键和值:
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)
这对于几个列表/数组以及每次插入/删除后的一些处理(即,遍历值并逐个更改它们)相当简单.
但是,我正在寻找一种方法来更有效地完成它,也许无需遍历整个值列表并递增/递减它们.也许甚至通过延迟递增/递减直到请求了一个值(应该已经递增/递减).
有什么想法吗？
我认为如果你需要通过某个键进行快速查找，并根据实际值修改结果，你需要两种数据结构：一种用于键，一种用于值。
键的数据结构将只是一个从键到值树中的节点的关联数组（将其实现为哈希表、自平衡树或跳跃列表，这并不重要）。
值树将是一个自平衡二叉搜索树（或一个跳跃列表，请参阅下面的编辑）。树中的节点有一个与之关联的增量以及它们的值。增量适用于大于或等于特定节点的所有节点，即，它适用于自身及其右子树中的所有节点。
当您插入一个值时，您会增加所有大于或等于您要插入的值的节点的增量。这会增加值大于或等于您在整个树中插入的值的所有节点的实际值。删除类似，只是将增量替换为减量。
当你想要读取一个值时，你可以使用基于键的结构来查找基于值的树中的节点。然后，您爬到根（为此，您必须保留指向树中节点的父节点的指针）并从节点累积增量，其值大于或等于您开始的节点中的值。
在进行重新平衡时必须小心，因为您选择的自平衡算法需要，因为您必须重新计算某些节点的增量，但这不应该影响时间复杂度。
编辑：对于跳过列表，管理增量非常简单：当您正在寻找插入位置时，在您比较的链表中的每个节点中增加增量增量，该增量大于或等于您要插入的值（其中也意味着您将下降一级）。删除是类似的，只是您必须将已删除项目保留的任何增量移到右侧。
当您想要计算某个节点的实际值时，请在当前项目中爬得尽可能高，并在那里应用增量（一项可以在不同级别上多次插入或删除而产生增量，您始终必须使用最高层的值），然后进入链表左侧一个节点并重复该过程，直到到达最左边的项目。
访问节点的方式也意味着链表必须是双向链接的。