Comment traverser un arbre sans utiliser la récursivité?

19

J'ai une très grande arborescence de nœuds de mémoire et j'ai besoin de traverser l'arbre. Passer les valeurs renvoyées de chaque nœud enfant à leur nœud parent. Cela doit être fait jusqu'à ce que tous les nœuds aient leur bulle de données jusqu'au nœud racine.

La traversée fonctionne comme ça.

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);
}

Cela fonctionne bien, mais je crains que la pile d'appels limite la taille de l'arborescence des nœuds.

Comment le code peut-il être réécrit afin qu'aucun appel récursif ne Executesoit effectué?

Reactgular
la source
8
Vous devrez soit conserver votre propre pile pour suivre les nœuds, soit modifier la forme de l'arborescence. Voir stackoverflow.com/q/5496464 et stackoverflow.com/q/4581576
Robert Harvey
1
J'ai également trouvé beaucoup d'aide dans cette recherche Google , en particulier Morris Traversal .
Robert Harvey
@RobertHarvey merci Rob, je ne savais pas sous quelles conditions cela irait.
Reactgular
2
Vous pourriez être surpris des besoins en mémoire si vous faisiez le calcul. Par exemple, un arbre binaire teranode parfaitement équilibré n'a besoin que d'une pile de 40 entrées de profondeur.
Karl Bielefeldt
@KarlBielefeldt Cela suppose cependant que l'arbre est parfaitement équilibré. Parfois, vous devez modéliser des arbres qui ne sont pas équilibrés, et dans ce cas, il est très facile de faire sauter la pile.
Servy

Réponses:

27

Voici une implémentation de traversée d'arbre à usage général qui n'utilise pas la récursivité:

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);
    }
}

Dans votre cas, vous pouvez l'appeler ainsi:

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

Utilisez une Queueau lieu d'un Stackpour respirer d'abord, plutôt que la profondeur d'abord. Utilisez un PriorityQueuepour une meilleure première recherche.

Servy
la source
Ai-je raison de penser que cela ne fera qu'aplatir l'arbre en une collection?
Reactgular
1
@MathewFoscarini Oui, c'est son but. Bien sûr, il n'a pas besoin d'être nécessairement matérialisé dans une collection réelle. Ce n'est qu'une séquence. Vous pouvez itérer dessus pour diffuser les données, sans avoir besoin de mettre l'ensemble de données en mémoire.
Servy
Je ne pense pas que cela résout le problème.
Reactgular
4
Il ne parcourt pas seulement le graphique en effectuant des opérations indépendantes comme une recherche, il agrège les données des nœuds enfants. L'aplatissement de l'arbre détruit les informations de structure dont il a besoin pour effectuer l'agrégation.
Karl Bielefeldt
1
FYI Je pense que c'est la bonne réponse que la plupart des gens recherchent sur Google. +1
Anders Arpi
4

Si vous avez au préalable une estimation de la profondeur de votre arbre, peut-être suffit-il que votre cas adapte la taille de la pile? En C # depuis la version 2.0, cela est possible chaque fois que vous démarrez un nouveau thread, voir ici:

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

De cette façon, vous pouvez conserver votre code récursif, sans avoir à implémenter quelque chose de plus complexe. Bien sûr, la création d'une solution non récursive avec votre propre pile peut être plus efficace en termes de temps et de mémoire, mais je suis sûr que le code ne sera pas aussi simple qu'il l'est pour l'instant.

Doc Brown
la source
Je viens de faire un test rapide. Sur ma machine, je pouvais passer 14 000 appels récursifs avant d'atteindre stackoverflow. Si l'arbre est équilibré, seuls 32 appels sont nécessaires pour stocker 4 milliards de nœuds. Si chaque nœud fait 1 octet (ce qui ne sera pas le cas), il faudrait 4 Go de RAM pour stocker un arbre équilibré de hauteur 32.
Esben Skov Pedersen
Si nous devions utiliser les 14 000 appels de la pile. L'arbre prendrait 2,6 x 10 ^ 4214 octets si chaque nœud est un octet (ce qui ne sera pas le cas)
Esben Skov Pedersen
-3

Vous ne pouvez pas traverser une structure de données sous la forme d'un arbre sans utiliser la récursivité - si vous n'utilisez pas les cadres de pile et les appels de fonction fournis par votre langage, vous devez essentiellement programmer votre propre pile et les appels de fonction, et c'est il est peu probable que vous parveniez à le faire dans le langage de manière plus efficace que les rédacteurs du compilateur sur la machine sur laquelle votre programme s'exécuterait.

Par conséquent, éviter la récursivité par crainte de rencontrer des limites de ressources est généralement malavisé. Certes, l'optimisation prématurée des ressources est toujours erronée, mais dans ce cas, il est probable que même si vous mesurez et confirmez que l'utilisation de la mémoire est le goulot d'étranglement, vous ne pourrez probablement pas l'améliorer sans descendre au niveau de la rédacteur du compilateur.

Kilian Foth
la source
2
C'est tout simplement faux. Il est très certainement possible de parcourir un arbre sans utiliser de récursivité. Ce n'est même pas difficile . Vous pouvez également le faire plus efficacement, de manière assez triviale, car vous ne pouvez inclure autant d'informations dans la pile explicite que vous êtes sûr d'avoir besoin pour votre parcours spécifique, tandis qu'en utilisant la récursivité, vous finissez par stocker plus d'informations que vous n'en avez réellement besoin dans de nombreux cas.
Servy
2
Cette controverse revient de temps en temps ici. Certaines affiches considèrent que rouler votre propre pile n'est pas récursive, tandis que d'autres soulignent qu'elles font simplement la même chose explicitement que le runtime ferait autrement implicitement. Il est inutile de discuter de définitions comme celle-ci.
Kilian Foth
Comment définissez-vous alors la récursivité? Je le définirais comme une fonction qui s'invoque dans sa propre définition. Vous pouvez très certainement traverser un arbre sans jamais le faire, comme je l'ai démontré dans ma réponse.
Servy
2
Suis-je méchant d'avoir apprécié l'acte de cliquer sur le downvote sur quelqu'un avec un score de répétition aussi élevé? C'est un plaisir si rare sur ce site.
Reactgular
2
Allez @Mat, c'est des trucs d'enfants. Vous pouvez être en désaccord, comme si vous avez peur de bombarder un arbre trop profond, c'est une préoccupation raisonnable. Vous pouvez simplement le dire.
Mike Dunlavey