二阶搜索树中的有序遍历复杂性(使用迭代器)？

Question

相关问题:二叉树O(N)的InOrder树遍历的时间复杂度？但是它基于遍历递归(因此在O(log N)空间中),而迭代器只允许消耗O(1)空间.

在C++中,通常需要将标准容器的迭代器递增为O(1)操作.对于大多数容器来说,它已被轻易证明,但是有了map这样,似乎有点困难.

因此,在有序遍历期间,有时候"下一个"值不容易达到.例如,如果您指向左子树的右下方叶子,那么要遍历的下一个节点就是根,这是depth一步之遥.

我试过"证明"算法的复杂性(就"步骤"而言)是摊销的 O(1),这似乎没问题.但是我还没有进行演示.

这是我为深度为4的树追踪的一个小图,数字(在节点的位置)表示在有序遍历期间从该节点到下一个节点的步数:

       3
   2       2
 1   1   1   1
1 2 1 3 1 2 1 4

注意:如果这是一棵较大树的子树,则最右边的叶子的成本为4.

总和为28,总节点数为15:因此平均每个节点的成本小于2,(如果它保持)将是一个很好的摊销成本.所以:

Answer 1

是的O(1),对于任何树,摊销成本确实是每次迭代.

证明基于您"访问"每个节点的次数.
叶子只访问过一次.没有叶子最多访问3次:

没有更多的访问任何节点,因此如果我们总结每个节点的访问次数,我们得到一个小于那个的数字3n,因此所有节点的总访问次数是O(n),这使我们O(1)按步骤摊销.

(注意,因为在完整的树中有n/2个叶子,我们得到2n你遇到的,我相信可以证明访问的总和将小于2n任何树,但这个"优化"超出了范围IMO).

每个步骤的最坏情况是O(h),O(logn)在一个平衡的树中,但O(n)在某些情况下可能.

PS我不知道如何在C++中实现Red-Black树,但如果您的树数据结构包含parent来自每个节点的字段,它可以替换递归堆栈并允许O(1)空间消耗.(这当然是"作弊",因为存储n这些字段O(n)本身).