0

在去面试之前我正在做一些准备工作，我刚刚了解了 Morris Traversal。

这是我用 Java 编写的 Morris Traversal 代码（它的工作）：

protected void morrisTraversal(){
    BinaryNode pre = null;//BinaryNode is a class which represent a node in the tree
    BinaryNode current = this.root;//root is the root of the tree
    while(current != null){
        if(current.getLeftChild() == null){
            System.out.println(current.getNodeData().getId());//id is unique
            current = current.getRightChild();
        }//if
        else{
            pre = current.getLeftChild();
            while(pre.getRightChild() != null && pre.getRightChild().getNodeData().getId() != current.getNodeData().getId())
                pre = pre.getRightChild();
            if(pre.getRightChild() == null){
                pre.setRightChild(current);
                current = current.getLeftChild();
            }//if
            else{
                System.out.println(current.getNodeData().getId());
                current = current.getRightChild();
                pre.setRightChild(null);
            }//else
        }//else
    }//while
}//MorrisTraversal

这是我的 In-Order 方法的代码：

protected void recInOrder() {
    if(this.root != null)
        recInOrderHelper(this.root);
    else
        System.out.println("The Tree Is Empty");;
}//recInOrder


private void recInOrderHelper(BinaryNode node)  {
    if(node != null){
        recInOrderHelper(node.getLeftChild());
        System.out.println(node.getNodeData().getId());
        recInOrderHelper(node.getRightChild());
    }
}//recInOrderHelper

我主要做的是：我在我的二叉树中插入了 70,000,000 个节点，然后我做了下一个小检查：

long start = System.currentTimeMillis();
tree4.morrisTraversalInOrder();
System.out.println("morris traversal TOOK: " + (System.currentTimeMillis() - start) + " ms");

start = System.currentTimeMillis();
tree4.recInOrder();
System.out.println("recursive in-order TOOK: " + (System.currentTimeMillis() - start) + " ms");

结果让我吃惊！

这些是结果：

莫里斯遍历 TOOK：637 毫秒

递归有序 TOOK：367 毫秒

注意 - 当我做这个测试时，我评论了来自 morrisTraversal() 和 recInOrderHelper() 方法的所有 System.out.println(...) 。

这些结果让我感到惊讶，因为我认为 Morris Traversal 会更快，因为它的迭代（不打开堆栈帧等）和 In-Order 是递归的（每次递归调用打开大约 70,000,000 个堆栈帧）

我知道它们都是 O(n)，所以显然我对某些事情是错误的，但是哪个？我错过了什么？为什么 Morris Traversal 比递归 In-Order 慢得多？

编辑-我还进行了下一个测试：我没有向树中插入 70,000,000 个节点，而是插入了 100,000 个节点并且我确实运行了下一个代码：

//running the two algorithms one time before doing the actual test(but in the same execution)
tree4.recInOrder();
tree4.morrisTraversalInOrder();

//starting the actual test
long start = System.currentTimeMillis();
for(i = 0; i < 100000; i++){
    tree4.recInOrder(); 
}
System.out.println("Recursive In-Order TOOK: " + (System.currentTimeMillis() - start) + " ms");

start = System.currentTimeMillis();
for(i = 0; i < 100000; i++){
    tree4.morrisTraversalInOrder(); 
}
System.out.println("Morris Traversal TOOK: " + (System.currentTimeMillis() - start) + " ms");

结果是：

递归有序 TOOK：214434 毫秒

莫里斯遍历 TOOK：502786 毫秒

正如您所看到的，与递归 In-Order 相比，Morris Traversal 仍然非常慢。所以我又做了一次测试，只插入了 1000 个节点，每个代码只运行了 10000 次，结果是：

递归有序 TOOK：44 毫秒

莫里斯遍历 TOOK：97 毫秒

我还是不明白？为什么莫里斯遍历速度较慢？

4

3 回答 3

2

看到这里你就明白其中的逻辑了。只需对 morris 进行空运行以进行遍历，假设它需要 2k 时间。现在为递归中序遍历做空运行，我很确定你会或多或少地找到时间 k。这里的逻辑是，Morris 中序遍历所花费的时间或多或少是中序遍历所花费时间的两倍，因为我们最多到达每个节点 2 次。一次用于创建虚拟正确链接，另一次用于删除该正确链接。

现在，如果您对空间复杂性感兴趣，那么莫里斯中序遍历就像是国王。在这里你不需要额外的空间。它的空间复杂度是 O(1)，但是递归中序遍历的空间复杂度是 O(n)。希望现在您可以了解两种遍历策略的用途。:)

于 2020-04-15T03:27:26.000 回答
0

如果不将性能估计分解为它们的组件，就很难判断，但是当用假的正确部分追溯节点时，Morris Traversal 本质上遍历了树的一部分。你也在莫里斯循环中做更多的工作，所以常数因子会更大。奇怪的是它几乎是 2 倍，但如果没有进一步的细节，我不会相信这是实际成本。

于 2013-02-06T00:17:51.843 回答
0

你没有热身证。您应该先执行这两个方法，然后再按时执行。您还忽略了大多数 Java 代码在长时间运行的进程中运行的事实，这些进程最终会编译为机器代码。我会尝试使用较小的树并多次执行遍历。

于 2013-02-06T00:33:45.123 回答