二叉树中的Morris遍历与递归有序性能

Question

在接受采访之前，我正在做一些准备，但我刚刚了解了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

这是我的订购方法代码：

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");

结果令我惊讶！

这些是结果：

Morris遍历时间：637毫秒

递归顺序操作：367毫秒

注意-当我进行此测试时，我评论了morrisTraversal（）和recInOrderHelper（）方法中的所有System.out.println（...）。

这些结果令我感到惊讶，因为我认为Morris Traversal会更快，因为它的迭代过程（不会打开堆栈框架等）并且按顺序是递归的（每个递归调用大约打开70,000,000个堆栈框架）

我知道他们两个都是O（n），所以很明显，我在某些事情上错了，但是哪一个呢？我想念什么？为什么Morris Traversal比递归顺序慢得多？

EDIT-我还进行了下一个测试：而不是在树上插入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");

结果是：

递归有序操作：214434毫秒

Morris遍历时间：502786毫秒

并且您可以看到，与递归顺序相比，莫里斯遍历仍然很慢。所以我进行了另一项测试，仅插入了1,000个节点，每个代码仅运行了10,000次结果是：

递归顺序操作：44毫秒

Morris遍历时间：97毫秒

我还是不明白吗？为什么Morris Traversal慢一些？

Answer 1

很难将性能评估分解为各个组成部分，但是当使用假的正确部分回溯节点时，Morris遍历实际上遍历了树的一部分两次。您还需要在Morris循环中做更多的工作，因此常数因子将会更大。奇怪的是它几乎是原来的2倍，但是如果没有更多细节，我将不依赖于实际成本。

Answer 2

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

Answer 3

请参阅此处，您必须了解逻辑。只需对morris进行空运行以遍历遍历，可以说需要2k的时间。现在对递归有序遍历进行空运行，我非常确定您会发现k或多或少的时间。这里的逻辑是，莫里斯有序遍历所花费的时间大约是有序遍历所花费时间的两倍，因为我们最多到达每个节点2次。一次用于创建虚拟右链接，另一个用于删除该右链接。

现在，如果您对空间复杂性感兴趣，那么莫里斯有序遍历就像国王一样。在这里，您不需要多余的空间。它的空间复杂度是O（1），但是递归有序遍历的空间复杂度是O（n）。希望现在您可以了解这两种遍历策略的用法。 ：）