¿Cómo atravesar un árbol sin usar la recursividad?

19

Tengo un árbol de nodos de memoria muy grande y necesito atravesar el árbol. Pasar los valores devueltos de cada nodo secundario a su nodo primario. Esto debe hacerse hasta que todos los nodos tengan su burbuja de datos hasta el nodo raíz.

El recorrido funciona así.

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

Esto funciona bien, pero me preocupa que la pila de llamadas limite el tamaño del árbol de nodos.

¿Cómo se puede reescribir el código para que no Executese realicen llamadas recursivas ?

Reactgular
fuente
8
Tendría que mantener su propia pila para realizar un seguimiento de los nodos o cambiar la forma del árbol. Ver stackoverflow.com/q/5496464 y stackoverflow.com/q/4581576
Robert Harvey
1
También encontré mucha ayuda en esta Búsqueda de Google , específicamente Morris Traversal .
Robert Harvey
@RobertHarvey le agradece a Rob, no estaba seguro de los términos bajo los cuales esto iría.
Reactgular
2
Te sorprenderían los requisitos de memoria si hicieras los cálculos. Por ejemplo, un árbol binario teranode perfectamente equilibrado solo necesita una pila de 40 entradas de profundidad.
Karl Bielefeldt
@KarlBielefeldt Eso supone que el árbol está perfectamente equilibrado. A veces necesitas modelar árboles que no están equilibrados, y en ese caso es muy fácil volar la pila.
Servy

Respuestas:

27

Aquí hay una implementación transversal del árbol de propósito general que no utiliza la recursividad:

public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

En su caso, puede llamarlo así:

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

Use una en Queuelugar de una Stackpara respirar primero, en lugar de buscar primero la profundidad. Use a PriorityQueuepara una mejor primera búsqueda.

Servy
fuente
¿Estoy en lo cierto al pensar que esto simplemente aplastará el árbol en una colección?
Reactgular
1
@MathewFoscarini Sí, ese es su propósito. Por supuesto, no es necesario que se materialice necesariamente en una colección real. Es solo una secuencia. Puede iterar sobre él para transmitir los datos, sin necesidad de extraer todo el conjunto de datos en la memoria.
Servy
No creo que eso resuelva el problema.
Reactgular
44
No solo recorre el gráfico realizando operaciones independientes como una búsqueda, sino que agrega los datos de los nodos secundarios. Al aplastar el árbol se destruye la información de estructura que necesita para realizar la agregación.
Karl Bielefeldt
1
FYI Creo que esta es la respuesta correcta que busca la mayoría de las personas que buscan en Google esta pregunta. +1
Anders Arpi
4

Si tiene una estimación de la profundidad de su árbol de antemano, ¿tal vez sea suficiente para su caso adaptar el tamaño de la pila? En C # desde la versión 2.0 esto es posible siempre que inicie un nuevo hilo, vea aquí:

http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx

De esa manera puede mantener su código recursivo, sin tener que implementar algo más complejo. Por supuesto, crear una solución no recursiva con su propia pila puede ser más eficiente en cuanto a tiempo y memoria, pero estoy bastante seguro de que el código no será tan simple como lo es por ahora.

Doc Brown
fuente
Acabo de hacer una prueba rápida. En mi máquina, podía hacer 14000 llamadas recursivas antes de llegar al stackoverflow. Si el árbol está equilibrado, solo se necesitan 32 llamadas para almacenar 4 mil millones de nodos. Si cada nodo es de 1 byte (que no será) Se necesitarían 4 GB de RAM para almacenar un árbol equilibrado de altura 32.
Esben Skov Pedersen
I íbamos a utilizar todas las 14000 llamadas en la pila. El árbol ocuparía 2.6x10 ^ 4214 bytes si cada nodo es un byte (que no será)
Esben Skov Pedersen
-3

No puede atravesar una estructura de datos en forma de árbol sin usar la recursividad: si no usa los marcos de pila y las llamadas de función proporcionadas por su idioma, básicamente tiene que programar sus propias llamadas de pila y función, y es es poco probable que logre hacerlo dentro del lenguaje de una manera más eficiente que los escritores del compilador en la máquina en la que se ejecutaría su programa.

Por lo tanto, evitar la recursividad por temor a toparse con los límites de recursos suele ser erróneo. Sin duda, la optimización prematura de los recursos siempre está mal orientada, pero en este caso es probable que incluso si mide y confirma que el uso de la memoria es el cuello de botella, probablemente no podrá mejorarlo sin descender al nivel de escritor compilador

Kilian Foth
fuente
2
Esto es simplemente falso. Ciertamente es posible atravesar un árbol sin usar la recursividad. Ni siquiera es difícil . También puede hacerlo de manera más eficiente, bastante trivial, ya que solo puede incluir tanta información en la pila explícita como esté seguro de que necesita para su recorrido específico, mientras que al usar la recursión termina almacenando más información de la que realmente necesita en muchos casos.
Servy
2
Esta controversia surge de vez en cuando aquí. Algunos carteles consideran que rodar su propia pila no es una recursividad, mientras que otros señalan que simplemente están haciendo lo mismo explícitamente que el tiempo de ejecución de lo contrario haría implícitamente. No tiene sentido discutir sobre definiciones como esta.
Kilian Foth
¿Cómo se define la recursividad entonces? Lo definiría como una función que se invoca dentro de su propia definición. Seguramente puedes atravesar un árbol sin hacer eso, como he demostrado en mi respuesta.
Servy
2
¿Soy malo por disfrutar el acto de hacer clic en el voto negativo de alguien con un puntaje de repetición tan alto? Es un placer tan raro en este sitio web.
Reactgular
2
Vamos @Mat, eso es cosa de niños. Puede estar en desacuerdo, como si tiene miedo de bombardear un árbol que es demasiado profundo, es una preocupación razonable. Solo puedes decirlo.
Mike Dunlavey