Cómo atravesar un árbol binario en O (n) tiempo sin memoria extra

Question

Dado un árbol binario con un número entero, & izquierdos punteros, cómo se puede recorrer el árbol en O (n) tiempo y O (1) memoria adicional (sin pila/cola/recursividad)?

This guy dio una solución que no es O (n) tiempo total que codificó la ruta actual como un entero (y por lo tanto funciona en árboles de profundidad limitada).

Busco la solución clásica

(SPOILER)

que codificaba el padre de cada nodo en los niños.

Answer 1

Cualquier buen libro de algoritmos tendrá este algoritmo, mira p. en Knuth (TAOCP I.2.3.1 Recorrido de árboles binarios, ejercicio 21). Sin embargo, debido a que este algoritmo modifica el árbol en su lugar, debe usar extreme precaución en un entorno de subprocesos múltiples.

También puede utilizar árboles roscados (consulte en Knuth).

Answer 2

El algoritmo de ese tipo es interesante, pero debe señalarse que requiere O (log n) extra bits de espacio para atravesar un árbol binario con n nodos. Los requisitos de espacio se deben medir en bits, no en bytes; por lo general, se colapsan en la misma cosa cuando se utiliza la notación Big Oh, pero casos como este indican por qué es importante hacer la distinción.

Para ver esto, pregunte cómo se puede atravesar un árbol con más de 2^32-1 nodos utilizando un único entero de almacenamiento (en una plataforma de 32 bits).

Answer 3

Utilice el almacenamiento O (1) para recordar el puntero "último nodo visitado". Puede inicializarlo en 0 o en algún valor desconocido.

Para recorrer el árbol, comience en el nodo raíz. Mira los dos hijos del nodo. Si su "último nodo visitado" es igual al nodo DERECHO, vaya al nodo principal. Si la "última visita" es igual al nodo IZQUIERDO, luego pásese al nodo derecho. Else paso hacia el nodo izquierdo.

Repita hasta que haya terminado de caminar todo el árbol. La única habilidad real es usar la única variable para recordar de dónde vienes para decidir a dónde ir. Esto hace que el recorrido sea determinista.

Terminará tomando O (n) pasos. Visitarás cada nodo medio tres veces, y cada hoja una vez, por lo que todavía eres O (N). El almacenamiento es O (1).

Answer 4

La idea principal es similar al algoritmo de inversión de lista, con un truco súper feo (desde un punto de vista teórico, probablemente un truco), basado en el hecho de que los punteros son (en todos los languges conocidos actualmente por los humanos), 0 modo 4 como enteros.

La idea es que puede voltear los punteros en el camino hacia abajo del árbol para apuntar hacia arriba. El problema es que - y aquí es donde se desvía del algoritmo de inversión de lista - cuando retrocede necesita saber si los puntos a la izquierda o a la derecha apuntan hacia arriba; en ese punto usamos el truco.

pseudo código siguiente:

current = root->left 
next = current 
while (current != null) { 
    next = current->left 
    current->left = static_cast<int>(prev) + 1 // ugly hack. 
    current = next 
} 
status = done 
while (current != root or status != done) { 
    if (status = done) { 
    if (static_cast<u32>(current->left) %4 = 1) { 
     next = static_cast<u32>(current->left) -1 
     current->left = prev 
     status = middle 
    } 
    else { 
     next = current->right 
     current->right = prev 
     status = done 
    } 
    prev = current 
    current = next 
    } 
    else if (status == left) { 
    if (current->left) { 
     prev = current->left 
     current->left = static_cast<u32>(next) +1 
     next = current 
    } 
    else 
     status = middle 
    } 
    else if (status == right) { 
    if (current->right) { 
     prev = current->right; 
     current ->right = next; 
     next = current 
    } 
    else 
     status = done 
    } 
    else {// status == middle 
    work_on_node(current) 
    status = right 
    } 
} 

Answer 5

Aquí hay otra solución

http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

pero me preguntaba si hay una manera de hacer esto en lenguajes como Java, que no tienen punteros en verdadero sentido