Morris Traversal o(n)的时间复杂度如何？

Question

http://geeksforgeeks.org/?p=6358 任何人都可以解释Morris Traversal的时间复杂度如何o(n)？在遍历中,每当节点具有左子节点时,就将其副本发送给其前任的右子节点.最糟糕的情况是必须为每个节点找到前任

 while(pre->right != NULL && pre->right != current)
        pre = pre->right;

哪个会增加时间复杂度？我在这里错过了什么吗？

Answer 1

查看它的另一种方法是找出遍历树节点的次数.因为它是常量(二叉树的3倍).我们正在寻找O(n).

Answer 2

Morris遍历的原始论文是简单而廉价地遍历二叉树.它声称引言部分的时间复杂度为O(n):

它也是高效的,花费时间与树中的节点数成比例,并且在节点中既不需要运行时堆栈也不需要"标志"位.

全文应该分析时间复杂性.但是无法免费访问完整的论文.

一些分析,Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间).我已经翻译了一些相关部分,并根据我的理解做了一些修改.这是我的理解:

n节点二叉树具有n-1个边.在Morris遍历中,最多访问一个边缘3次.第一次访问是用于定位节点.第二次访问是为了寻找某个节点的前身.而3rd/final用于将前任的正确子项恢复为null.在下面的二叉树中,红色虚线用于定位节点(第一次访问).黑色虚线用于寻找前任节点(行进两次:第二次访问和第三次访问).定位时将访问节点F. 当节点H正在寻找其前身时,也将访问它.最后,将节点G(H的前身)的正确子节点恢复为null时将访问它.

Answer 3

它不会增加复杂性,因为算法只在一个方向上重建树(重建只需要O(n),之后只有O(n)再次打印它们......但是它们已将两个功能合并到一个相同的功能,并为算法赋予了一个特殊的名称...

Answer 4

首先，我对您提出的主张进行更正：

在遍历过程中，每当节点有左子节点时，都会将其副本复制到其前任节点的右子节点

[当前]节点的副本不会复制到其[当前节点]前任节点的右子节点 - 当前节点的前任节点的右子节点指向当前节点 - 指针不会进行任何复制；相反，它只是指向已经存在的当前节点。

现在回答有关代码片段的问题：

while(pre->right != NULL && pre->right != current)
        pre = pre->right;

• 该循环确实增加了算法的运行时间[与代码中没有该循环相比]
• 但在最坏的情况下，它增加的时间恰好是n（运行时间从n到2n）。当每个节点必须被额外访问一次才能找到所有前驱时，就会发生这种最坏的情况；顺便说一句，给定节点的每次此类额外访问都是在查找前驱时访问它的唯一额外时间（这是因为查找任何其他前驱永远不会经过与查找任何其他前驱相同的节点） - 这解释了为什么额外的时间有助于从n -> 2n [线性] 而不是n -> n^2 [二次]
• 即使2n > n ，当考虑[Big-O]复杂度时，O(2n) = O(n)
• 换句话说，与n相比，花费更长的2n时间并不是实际的额外复杂性： n和2n运行时都具有相同的 O(n) 复杂性 [它们都是“线性”]

现在，尽管听起来我在上面暗示整个算法运行时间是2n，但事实并非如此——它实际上是3n。

• 代码片段本身的循环贡献了n次
• 但整个算法的运行时间为3n，因为每个节点最多被访问 3 次{一次/第一次将其“线程”回其前身节点（代码片段帮助实现的最终目标）；在正常遍历中第二次到达[而不是与前驱线程有关]；然后第三次/最后一次，再次发现它作为前驱[本身是第二次/最后一次]，并且其右子指针/线程从指向当前节点的右子节点中删除[直接在打印当前节点之前] }
• 再次[正如复杂度O(2n) = O(n)]，复杂度O(3n) = O(n)
• 总结一下： 是的，您的代码片段循环确实贡献了时间，但没有额外的时间复杂度

顺便说一句，我不认为这条线（从完整的算法中）删除旧的前身“线程”引用是绝对必要的（尽管它不会造成伤害，并且可以被认为是很好的整理）：

pre->right = NULL; 

Answer 5

我这里讨论Morris中序遍历，因为一个节点最多可以被访问4次，所以时间复杂度为O(n)。

我们把一个节点被访问的类型分为两种：

1. 访问current该节点。

   如果一个节点有左孩子，current则访问两次，否则访问一次。

2. 建立一个循环并销毁该循环。

   如果一个节点处于循环中，则该节点被访问两次，否则为零。

我画了下图，用isA + B来表示时间，Ais current，Bis循环。

对于节点D， current从 移动B到D并从E移动到D。D也在循环中A B D F G，当从 移动到（构建循环）和从移动到（破坏循环）D时被访问。因此，节点被访问 2 + 2 = 4 次。currentABAHD