莫里斯遍历的时间复杂度为O(n)是如何实现的？

Question

http://geeksforgeeks.org/?p=6358 有人可以解释一下为什么莫里斯遍历的时间复杂度是o(n)吗？在这种遍历中，每当节点有一个左子节点时，它的前驱节点会被复制到其右子节点中。所以最坏情况是需要为每个节点找到前驱节点。

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

哪个会增加时间复杂度？ 我是否有遗漏什么？

- Hari Krishna

Answer 1

原始的 Morris 遍历论文为Traversing binary trees simply and cheaply。在介绍部分它声称时间复杂度为 O(n)：

它也很高效，花费的时间与树中节点的数量成比例，并且不需要运行时堆栈或节点中的'标志'位。

完整的论文应该对时间复杂度进行分析。但是完整论文无法免费访问。

Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）进行了一些分析。我已经翻译了一些相关部分并根据我的理解做出了一些更正。以下是我的理解：

一棵具有n个节点的二叉树有n-1条边。在Morris遍历中，一条边最多被访问3次。第一次访问是为了找到一个节点，第二次访问是为了查找某个节点的前驱节点，而第三次/最后一次是为了将前驱节点的右孩子恢复为null。在下面的二叉树中，红色虚线用于定位一个节点（第一次访问）。黑色虚线用于查找前驱节点（两次遍历：第二次访问和第三次访问）。当查找节点H的前驱节点时，节点F也会被访问。最后，当将节点G（H的前驱）的右孩子恢复为null时，节点F也会被访问。

- Jingguo Yao

---

为什么不是3次呢？当指向的节点有其右子（非 null）指针引用被重新设置为null时（在打印当前节点之前直接发生），难道不也有第三次/最后一次访问吗？ 我指的是来自完整算法的这一行：pre->right = NULL; - cellepo

@cellepo 你说得对。当将前驱节点的右子节点恢复为null时，会再次访问一个节点。我已经更新了我的答案。 - Jingguo Yao

谢谢 - 你的编辑看起来很好。我跟进并澄清了黑线被走了两次（第二次和第三次都是如此） - 我不确定你是否已经看到了这个编辑，但如果你认为我写错了什么，请告诉我。 - cellepo

Answer 2

这不会增加复杂度，因为该算法仅在一个方向上重建树（重建仅需O(n)，之后再打印需要O(n)...但他们将两个功能合并到同一个函数中，并为算法赋予了特殊名称，就这样。

- jagadeesh

---

刚刚意识到，在二叉树中找到所有节点的前驱需要O(n)的时间。 - Hari Krishna

Answer 3

另一种看待它的方式是找出一个树节点会被遍历多少次。由于这是常数（对于二叉树而言为3次），因此我们得到了O(n)的时间复杂度。

- arpit gautam

---

一个节点可以被访问超过3次。例如，在树 [1, 2, 3, 4, 5, ..., 43] 中，节点 5 将被访问4次。 - qqqqqqq

Answer 4

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

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

1. 当前节点被访问。

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

2. 建立循环并销毁循环。

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

我绘制了下面的图形，并使用 A + B 表示访问次数，其中 A 是 current，B 是循环。

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

- baicaihenxiao

Answer 5

首先，我需要更正一下您所说的内容：

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

不是将当前节点复制到其前任的右子节点上 - 当前节点的前任的右子节点指向当前节点 - 指针并不会创建任何副本；相反，它只是指向已经存在的当前节点。

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

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

• 这个循环确实会增加算法的运行时间[与如果代码中没有该循环相比]
• 但在最坏情况下，它增加的时间恰好是n（将运行时间从n提高到2n）。当每个节点都必须被额外访问一次才能找到所有的前驱节点时，就会出现这种最坏情况。顺便说一下，每次对给定节点进行额外访问是找到前驱节点时它唯一的额外访问时间（因为查找任何其他前驱节点都不会经过与查找任何其他前驱节点经过的相同节点）。这就解释了为什么额外时间导致从n->2n [线性]而不是n->n^2 [二次]。
• 即使2n>n，当考虑[大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; 

- cellepo

---

只供参考：维基百科也有关于这个算法的好文章：在那里被称为"Threaded binary tree"。 - cellepo