java - モリストラバーサルのユースケース

Question

二分木をトラバースするためにモリストラバーサルを使用するプログラムを作成しました。そして好奇心のために、私はインオーダートラバーサルとモリストラバーサルの間のベンチマークを始めました。1000 回実行した後、モリス トラバーサルの平均時間は 5795 で、再帰的インオーダー トラバーサルの平均時間は 2457 で、モリス トラバーサルのほぼ 2 倍の速さであることがわかりました。

スレッド化された二分木を使用するモリス探索は複雑性が O(NlogN) で、再帰的インオーダー探索は O(N) であると思うので、明らかにモリス探索の方が時間がかかります。私の質問は以下の通りです：

• 私が言及した時間の複雑さは正しいですか？
• ここでモリストラバーサルがかなり遅い場合、再帰がそれほどコストがかからないJavaの世界でこれを使用するケースは何ですか。
• java再帰はwrt 言語のようなコストがかからないという私の主張Cが正しいかどうか? 前もって感謝します。

コードサンプル:

public class ThreadedBinaryTree<T extends Comparable<T>>
{
private TreeNode root;

public void morrisTraverse()
{
    TreeNode current = root;
    if(current == null)
    {
        return;
    }

    while(current != null)
    {
        if(current.left != null)
        {
            TreeNode temp = current.left;
            while(true)
            {
                if(temp.right == null) break;
                if(temp.right == current) break;
                temp = temp.right;
            }

            if(temp.right == null)
            {
                //create the link to predecessor
                temp.right = current;
                current = current.left;
            }
            else
            {
                //remove the link
                temp.right = null;
                //System.out.println(current.t);
                current = current.right;
            }
        }
        else
        {
            //System.out.println(current.t); 
            current = current.right;
        }
    }
}

public void inorder()
{
    inorder(root);
}

private void inorder(TreeNode node)
{
    if(node != null)
    {
        inorder(node.left);
        //System.out.println(node.t);
        inorder(node.right);
    }
}

private static class TreeNode<T extends Comparable<T>>
{
    private T t;
    private TreeNode left;
    private TreeNode right;

    private TreeNode(T t)
    {
        this.t = t;
    }
}
}

ドライバープログラム:

public static void main(String[] args)
{
    ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();
    binaryTree.insert(500);
    binaryTree.insert(20);
    binaryTree.insert(15);
    binaryTree.insert(25);
    binaryTree.insert(40);
    binaryTree.insert(35);
    ………….
………….. 
…………. some more inserts to tree
    int index = 1;
    long moris = 0;
    long normal = 0;
    while(index <= 1000)
    {
        long start = System.nanoTime();
        binaryTree.morrisTraverse();
        moris += System.nanoTime() -start;
        //System.out.println("__________________________________________________________");
        long start1 = System.nanoTime();
        binaryTree.inorder();
        normal+=System.nanoTime() -start1;
        index++;
    }
    System.out.println(moris/1000);
    System.out.println(normal/1000);
}