相关疑难解决方法(0)

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

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

• 如果a map被实现为跳过列表,那么结果将是显而易见的
• 然而,它们通常被实现为红黑树(或至少作为二叉搜索树)

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

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

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

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

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

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

• 在有序遍历期间,为平衡(和完整)二叉搜索树增加迭代器真的是O(1)吗？
• 可以将结果扩展到覆盖非完整二叉搜索树吗？