我知 Prop 有左子树和右子树的 RB 树可以以纯函数方式实现，而不会降低 log n 性能。带父指针的树可以在对数时间内实现吗？似乎循环引用子->父和父->子需要克隆所有树，因此是线性时间。
最佳答案
完全持久的、纯功能性的数据结构是树形的，但可以利用指针共享来成为有向无环图。但是，一旦引入指针循环，就无法在不复制整个子图的情况下“更改”该子图的一部分。
解决方案是添加一个间接寻址:将“身份”分配给值，这些值可以是对象(如 Clojure 的原子)或用作查找键的简单值(如数字或符号)。您可以将不可变指针视为 IDeref 的实现，它始终返回相同的对象。循环图可以表示为邻接图，其中按名称“解引用”节点与在名称到节点的映射中查找节点相同。
有关表示完全持久图的更多信息，请参阅 Fully Persistent Graphs - Which One to Choose? .
关于clojure - 带父指针的纯函数树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18007606/