在二叉搜索树上实现迭代器 [英] Implementing an iterator over a binary search tree

问题描述

我最近一直在编写一堆不同的二叉搜索树实现(AVL、splay、treap)，我很好奇是否有一种特别好"的方法来编写迭代器来遍历这些结构.我现在使用的解决方案是让 BST 中的每个节点都存储指向树中下一个和上一个元素的指针，这将迭代减少到标准的链表迭代.但是，我对这个答案并不满意.它将每个节点的空间使用量增加了两个指针(下一个和上一个)，在某种意义上它只是作弊.

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) 辅助存储空间(其中 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. 元素按升序访问(即中序遍历)
2. next() 和 hasNext() 查询在 O(1) 时间内运行.
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-Tree 都使用这种方法.

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屋！