¿Cómo es la complejidad de Morris Traversal o (n)?

Question

http://geeksforgeeks.org/?p=6358 ¿Puede alguien explicar cómo Morris Traversal tiene una complejidad de tiempo de o(n)? En el cruce, cada vez que el nodo tiene un hijo izquierdo, se realiza una copia al hijo derecho de su predecesor. El peor caso es que el predecesor se debe encontrar para cada nodo

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

¿Qué va a aumentar la complejidad? ¿Me falta algo aquí?

Answer 1

no va a aumentar la complejidad ya que el algoritmo simplemente reconstruye el árbol en una sola dirección (la reconstrucción toma solo O (n) después de lo cual es O (n) nuevamente para imprimirlos ... pero se han fusionado Tanto la funcionalidad en una misma función y le dio un nombre especial para el algo que es ...

Answer 2

Otra forma de verlo es averiguar cuántas veces se atravesará un nodo del árbol. Como es constante (3 . veces para un árbol binario) lo que buscamos en O (n)

Answer 3

El documento original para Morris recorrido es Traversing binary trees simply and cheaply se afirma que el tiempo la complejidad es O (n) en la sección Introducción:..

También es eficiente, tomando un tiempo proporcional al número de nodos en el árbol y que no requiere ni una pila en tiempo de ejecución ni bits de 'bandera' en los nodos.

El documento completo debe tener un análisis de la complejidad del tiempo. Pero no se puede acceder al documento completo de forma gratuita.

Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） hace algunos análisis. Ella es una traducción de la parte correspondiente:

Un árbol binario n-node tiene n-1 bordes. En una travesía de Morris, se visita un borde como máximo 2 veces. Una visita es para ubicar un nodo. Una visita es para buscar el predecesor de algún nodo. En el siguiente árbol binario, la línea discontinua roja es para localizar un nodo. La línea punteada negra es para buscar el nodo predecesor.