我知道具有左右子节点的 RB 树可以以纯函数方式实现，而不会降低 log n 性能。可以在对数时间内实现带有父指针的树吗？似乎循环引用 child->parent 和 parent->child 需要克隆所有树，因此是线性时间。
问问题
481 次
1 回答
3
完全持久的纯功能数据结构是树形的，但可以利用指针共享成为有向无环图。但是，一旦引入了指针循环，就不能在不复制整个子图的情况下“更改”该子图的一部分。
解决方案是添加间接：您将“身份”分配给值，这些值可以是对象（如 Clojure 的原子）或用作查找键的简单值（如数字或符号）。您可以将不可变指针视为 IDeref 的实现，它始终返回相同的对象。循环图可以表示为邻接图，其中按名称“取消引用”节点与在名称到节点的映射中查找它相同。
有关表示完全持久图的更多信息，请参阅完全持久图 - 选择哪一个？.
于 2013-08-26T18:10:01.283 回答