c++ - std::set(红/黑树)前向迭代是如何实现的？

Question

如果我对平衡 BST 从最小值到最大值进行中序遍历，我会使用 DFS 来维护大小为 lg(n) 的堆栈。但是如果我需要找到任意节点的中序后继节点，这是最坏的 lg(n) 操作。但是如果我想按顺序迭代，id 需要为每个产生 O(n*lg(n)) 的节点重复找到顺序后继。 std::set 是否使用了一些技巧来进行中序迭代，或者它真的花费了 O(n*lg(n))，还是时间成本以某种方式摊销了？

Answer 1

中序迭代没有技巧；您只需要一个 O(1) 机制来查找当前节点的父节点。

有序扫描恰好遍历每个父子边两次:一次从父子到子，一次从子到父。由于树中的边数与非根节点的数量相同，因此完整的迭代执行 Θ(n) 次转换以迭代 n 个节点，这是每个节点的摊销常数时间。

找到父节点的通常方法是在节点中存储一个父节点链接。额外的链接肯定会增加节点的大小(四个指针而不是三个)，但成本在合理范围内。

如果不是因为 C++ 迭代器失效规则，它要求有序关联容器元素的迭代器不能因插入或删除其他元素而失效，那么维护一个大小为 O(log < em>n) 在迭代器中。这样的迭代器会很笨重，但并非难以管理(因为 log n 在实践中被限制为一个较小的整数)，但在任何树修改后它都将无法使用。