纯函数自底向上树算法

Question

假设我想编写一个算法，处理一个不可变的树数据结构，该数据结构以叶子列表作为输入。它需要返回一棵新树，并对从这些叶子向上的旧树进行更改。

我的问题是，如果不重建整个树，检查叶子是否在列表中，似乎没有办法做到这一点纯粹的功能性，因为你总是需要返回一个完整的新树作为操作的结果，你可以' t 改变现有的树。

这是函数式编程中的一个基本问题，只能通过使用更合适的算法来避免，还是我遗漏了什么？

编辑：我不仅要避免重新创建整个树，而且函数算法应该具有与变异变体相同的时间复杂度。

Answer 1

到目前为止我见过的最有前途的（诚然不是很长......）是Zipper 数据结构：它基本上保留了一个单独的结构，从节点到根的反向路径，并对这个单独的结构进行本地编辑。

它可以进行多次本地编辑，其中大部分都是恒定时间，并将它们一次性写回树（重建到根的路径，这是唯一需要更改的节点）。

Zipper 是Clojure 中的标准库（请参阅标题Zippers - 功能树编辑）。

还有Huet 的原始论文以及 OCaml 中的实现。

免责声明：我已经编程很长时间了，但几周前才开始函数式编程，直到上周才听说过树的函数式编辑问题，所以我很可能还有其他解决方案不知道。

尽管如此，Zipper 看起来还是能满足人们的大部分愿望。如果 O(log n) 或以下还有其他替代方案，我想听听。