men*_*ics 6 immutability data-structures
我理解树通常用于修改持久数据结构(创建一个新节点并替换它的所有祖先).
但是,如果我有一个10,000个节点的树,我需要修改1000个节点呢？我不想通过创建1000个新根,我只需要一次修改所有内容所产生的新根.
例如:让我们以持久二进制树为例.在单个更新节点的情况下,它会进行搜索,直到找到节点,创建带有修改的新节点和旧子节点,并创建直到根节点的新祖先.
在批量更新的情况下,我们可以这样做:您不仅要更新单个节点,而且要在一次通过中更新1000个节点.
在根节点,当前列表是完整列表.然后,您可以在与左节点匹配的列表和与右侧节点匹配的列表之间拆分该列表.如果没有一个孩子匹配,不要下降到它.然后,您下降到左侧节点(假设存在匹配项),将其搜索列表拆分为其子节点,然后继续.如果您有一个节点和一个匹配项,则更新它并重新启动,替换和更新祖先和其他分支.
即使修改了任意数量的节点,这也只会产生一个新根.
这种"批量修改"操作有时称为批量更新.当然,细节将根据您正在使用的数据结构类型以及您尝试执行的修改类型而有所不同.
典型的操作类型可能包括"删除满足某些条件的所有值"或"增加与此列表中所有键相关联的值".通常,这些操作可以在整个结构上单次执行,花费O(n)时间.
您似乎关心创建"1000个新根"所涉及的内存分配.用于一次一个地执行操作的典型分配将是O(k log n),其中k是被修改的节点的数量.在整个结构上执行单步行的典型分配将是O(n).哪个更好取决于k和n.
在某些情况下,您可以通过特别注意何时发生更改来减少分配数量 - 以更复杂的代码为代价.例如,如果您有一个返回树的递归算法,您可以修改算法以返回一个树以及指示是否有任何更改的布尔值.然后,算法可以在分配新节点之前检查这些布尔值,以查看是否可以安全地重用旧节点.然而,人们通常不会费心去做这个额外的检查,除非他们有证据表明额外的内存分配实际上是一个问题.