Пример использования morris traversal

Question

Я написал программу, которая использует обход морриса для прохождения двоичного дерева. И для любопытства я начал выполнять бенчмаркинг между обходным путем и прохождением морриса. Я обнаружил, что после запуска в 1000 раз среднее время прохождения морриса составляет 5795, а для рекурсивного обхода порядка 2457, что почти в два раза быстрее, чем обход морриса.

Я думаю, что обход morris, который использует резьбовое двоичное дерево, имеет сложность O (NlogN), а рекурсивный обход по порядку имеет O (N), поэтому очевидно, что обход morris займет больше времени. Вопрос:

• - это временная сложность, о которой я упоминал правильно?
• Если обход morris здесь довольно медленный, тогда какой прецедент этого в java-мире, где рекурсия не очень дорогостоящая.
• Мое утверждение, что рекурсия не является дорогостоящей в java w.r.t. Языки, подобные 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); 
} 

Answer 1

временная сложность, что я есть упоминание правильно?

Нет, обход Морриса также является линейным.

если Морриса обходом довольно медленно здесь то, что случай использования этого в Java мире, где рекурсия не очень дорого

Моррис не использует дополнительное пространство. Рекурсия использует пространство стека. Если это разница между наличием достаточной памяти и нет, вы, вероятно, не должны были выбирать Java в первую очередь.

Мое утверждение, что рекурсия не является дорогостоящей в java w.r.t. Языки, подобные C, верны или нет?

Это свойство оценки, а не спецификация языка. Нет особых трудностей с реализацией, которые указывали бы априори одному более эффективному, чем другому.