使用迭代器克隆 BST 比递归更快吗？
我有一个关于二叉排序树设计原理的问题。
我需要创建二元表达式树的深层副本，我通过遍历树中的所有节点并创建一个新的相同节点来完成此任务。
我已经设置了一个用于其他用途的 treeIterator，并且想知道迭代器是否会更快、更慢，或者与递归执行的速度/内存使用量大致相同。
谢谢！
I had a question about a Binary Sorted Tree design principle.
I need to create a deep copy of a Binary Expression Tree, and I am accomplishing this by going through all the nodes in the tree and creating a new, identical one.
I already have a treeIterator set up for other uses and was wondering if an iterator would be faster, slower, or about the same speed/memory usage as doing it recursively.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为递归会更快。
我不知道你的迭代器的确切实现，但我假设它会到达每个节点？如果您的 BST 基于根节点结构，那么访问每个节点（如在迭代器中）将比递归慢。
这是我的实现方式：
递归地，
创建一个新的根节点（与原始根节点相同）。
添加原始根的左节点和右节点的副本。 （如果存在的话）
I think recursion would be faster.
I don't know your iterator's exact implementation, but I assume that it goes to each node? If your BST is based on a root node structure, then going to each node (as in a iterator) would be slower than recursion.
Here's how I would implement it:
Recursively,
Create a new root node (identical to the original root node).
Add copies of the original root's left and right nodes. (If they exist)
有两个部分：(1) 遍历树和 (2) 创建新的树副本。我假设迭代是指手动维护树中位置的循环。这可能比递归更快/更少的内存。但是，在构建新树时，最好使用递归并在遍历时构建树。如果迭代并将节点插入到新树中，则需要 O(n lg n)。另一方面，递归只需要 O(n)，尽管你可能会在非常深的树上耗尽堆栈。
There's two parts: (1) walking the tree and (2) creating a new tree copy. I assume by iteration you mean a loop that maintains the position in the tree manually. This is likely faster/less memory than recursion. However, when building a new tree it's probably better to use recursion and build the tree as you walk it. If you iterate and insert the node into a new tree that's going to take O(n lg n). Recursion, on the other hand, will take just O(n), though you may blow out your stack on very deep trees.
您没有指定如何实现迭代器。迭代器只是一个接口，而不是具体的实现。
在 BST 中搜索需要 O(log n) 时间，这意味着在任何时间点，查找下一个节点都应该花费 O(log n) 时间。
解释：
下一个节点始终是右子树中的最小元素或当前节点的父节点。无论如何，花费的时间不会超过 log n 时间。
除非你的迭代器实现花费的时间少于 O(log n) 时间，否则递归会更快。
编辑：我需要指出，这里的 O 表示法适用于平均情况，而不是最坏情况。但是，假设您有一个相当平衡的树，log n 应该仍然适用。
You didn't specify how you would implement the iterator. The iterator is just an interface, not a specific implementation.
Searching in a BST takes O(log n) time, which implies that at any point in time, finding the next node should take O(log n) time.
Explanation:
The next node is always either the smallest element in the right subtree or the parent of the current node. In any case, it will not take more than log n time.
Unless your iterator implementation takes less than O(log n) time, recursion will be faster.
Edit : I need to point out that the O-notation here is for average case, not for the worst case. However, assuming that you have a fairly balanced tree, log n should still apply.