轻松的树遍历和快速的随机节点访问
以下是 Alex Taggart 评论后编辑的。
我正在使用拉链轻松遍历和编辑一棵可以增长到数千个节点的树。每个节点在第一次创建时都是不完整的。数据将一直在随机位置添加/删除，叶节点将被分支替换，等等。
树可能非常不平衡。 对节点的快速随机访问也很重要。
一种实现是使用拉链遍历树并创建按键索引的节点的哈希表。不用说，上面的方法效率非常低，因为：
- 需要创建每个节点的 2 个副本，
- 任何更改都需要在 2 个数据结构（树和哈希图）之间一致镜像。
简而言之，是否有一种时间/空间有效的方法将拉链遍历/更新的便捷性与 clojure 中哈希表的快速访问结合起来？
Edited after Alex Taggart's remark below.
I am using a zipper to easily traverse and edit a tree which can grow to many thousands of nodes. Each node is incomplete when it is first created. Data is going to be added/removed all the time in random positions, leaf nodes are going to be replaced by branches, etc.
The tree can be very unbalanced.
Fast random access to a node is also important.
An implementation would be to traverse the tree using a zipper and create a hash table of the nodes indexed by key. Needless to say the above would be very inefficient as:
- 2 copies of each node need to be created
- any changes need to be consistently mirrored between the 2 data structures (tree and hashmap).
In short, is there a time/space efficient way to combine the easiness of traversing/updating with a zipper and the fast access of a hash table in clojure?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Clojure 的数据结构是持久的并使用结构共享。这意味着添加、删除或累积等操作并不像您描述的那样低效。内存成本将是最小的，因为您不会复制已有的内容。
默认情况下，Clojure 的数据结构是不可变的。因此，除非您使用某种引用类型（如 Var），否则树状结构中的节点不会自行更新。我对您的具体用例了解不够，无法就访问节点的最佳方式提供建议。访问嵌套结构中的节点的一种方法是 get-in 函数，您可以在其中使用提供节点的路径以返回其值。
希望这有助于解决您的问题。
Clojure's data structures are persistent and use structural sharing. This means that operations like adding, removing or accumulating are not as inefficient as you describe. The memory cost will be minimal since you are not duplicating what's already there.
By default Clojure's data structures are immutable. The nodes in your tree like structure will thus not update themselves unless you use some sort of reference type (like a Var). I don't know enough about your specific use case to advice on the best way to access nodes. One way to access nodes in a nested structure is the get-in function where you supply the path to the node to return its value.
Hope this helps solving your problem.