实现一个迭代器的二进制搜索树 [英] Implementing an iterator over a binary search tree

问题描述

我已经编码了一堆不同的二叉搜索树的实现最近（AVL，扇，树堆），并很好奇，如果有一个特别好的方式来写一个迭代器遍历这些结构。我用现在的解决方案是让在BST将指针存储到树，从而减少迭代一个标准的链表迭代的下一个和previous元素的每个节点。不过，我不是很满意这个答案。它增加了每个节点的空间使用率由两个指针（next和previous），在某种意义上，它只是欺骗。

I've been coding up a bunch of different binary search tree implementations recently (AVL, splay, treap) and am curious if there's a particularly "good" way to write an iterator to traverse these structures. The solution I've used right now is to have each node in the BST store pointers to the next and previous elements in the tree, which reduces iteration to a standard linked-list iteration. However, I'm not really satisfied with this answer. It increases the space usage of each node by two pointers (next and previous), and in some sense it's just cheating.

我知道的构建使用O（高）辅助存储空间（其中h是树的高度）通过使用堆栈来跟踪前沿节点探索稍后二叉查找树迭代的方式，但我抵制的编码，因为内存使用的这件事。我希望有一些方法来构建一个使用唯一不变的空间迭代器。

I know of a way of building a binary search tree iterator that uses O(h) auxiliary storage space (where h is the height of the tree) by using a stack to keep track of the frontier nodes to explore later on, but I've resisted coding this up because of the memory usage. I was hoping there is some way to build an iterator that uses only constant space.

我的问题是 - 有没有办法设计一个迭代器的二进制搜索树具有以下属性。

My question is this - is there a way to design an iterator over a binary search tree with the following properties?

1. 元素被访问升序排列（即一个序遍历）
在O（1）时间运行
2. 在next（）和规则hasNext（）查询。
3. 内存使用是O（1）

1. Elements are visited in ascending order (i.e. an inorder traversal)
2. next() and hasNext() queries run in O(1) time.
3. Memory usage is O(1)

为了方便，它是很好，如果你认为树结构是不迭代过程中改变形状（即没有插入，删除或旋转），但如果有一个解决办法，可以确实这将是非常酷处理这个问题。

To make it easier, it's fine if you assume that the tree structure isn't changing shape during the iteration (i.e. no insertions, deletions, or rotations), but it would be really cool if there was a solution that could indeed handle this.

推荐答案

最简单的迭代器存储的最后一次露面键，然后在下一次迭代中，搜索树的最小上限为关键。迭代是O（log n）的。这具有非常简单的优点。如果键是小那么迭代器也小。当然，它具有可通过树遍历的相对缓慢的方式的缺点。它也将不会对非唯一的序列工作。

The simplest possible iterator stores the last seen key, and then on the next iteration, searches the tree for the least upper bound for that key. Iteration is O(log n). This has the advantage of being very simple. If keys are small then the iterators are also small. of course it has the disadvantage of being a relatively slow way of iterating through the tree. It also won't work for non-unique sequences.

有些树使用完全相同你已经在使用的实施，因为这是他们的特定用途非常重要的扫描速度非常快。如果密钥中的每个节点的数目大，则存储兄弟指针的负担并不十分繁重。大多数B-树使用此方法。

Some trees use exactly the implementation you already use, because it's important for their specific use that scanning is very fast. If the number of keys in each node is large, then the penalty of storing sibling pointers isn't too onerous. Most B-Trees use this method.

许多搜索树的实现使每个节点上的父指针，以简化等操作。如果你有，那么你可以使用一个简单的指针到最后出现节点的迭代器的状态。在每次迭代中，你寻找下一个孩子在最后出现节点的父节点。如果没有更多的兄弟姐妹，那么你去了一个多水平。

many search tree implementations keep a parent pointer on each node to simplify other operations. If you have that, then you can use a simple pointer to the last seen node as your iterator's state. at each iteration, you look for the next child in the last seen node's parent. if there are no more siblings, then you go up one more level.

如果没有这些技术适合你，你可以用一个堆栈的节点，存储在迭代器。这通过搜索树作为正常进行迭代时，但不是通过同级循环，并在递归对儿童，则推儿童入堆栈，返回每个连续兄弟供应的功能相同的功能调用堆栈。

If none of these techniques suit you, you can use a stack of nodes, stored in the iterator. This serves a the same function as the function call stack when iterating through the search tree as normal, but instead of looping through siblings and recursing on children, you push children onto the stack and return each successive sibling.

这篇关于实现一个迭代器的二进制搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！