Traiter chaque feuille sous un nœud dans un arbre efficacement

Question

Version courte: Dans un arbre (non binaire) avec de nombreux niveaux d'enfants, où chaque nœud peut avoir plusieurs feuilles, quelle est la meilleure façon de laisser des feuilles de classification qui répondent à une certaine condition donnée à un nœud?

longue et compliquée: Dites que vous avez des dossiers, qui peuvent contenir plus de dossiers. En production, mon système compte environ 15 couches de dossiers au plus profond. Chaque dossier peut avoir des documents.

Lorsqu'un utilisateur navigue dans un dossier, ils doivent savoir combien de documents sont dans ce dossier, total. Ils doivent également savoir combien de ces documents ont été "signalés". Les documents peuvent être signalés si, après une certaine période, ils n'ont pas été mis à jour. Ceci est déterminé en fonction des entrées d'histoire - prenez la dernière entrée d'historique du dossier, s'il est plus grand que X, puis il est signalé.

À l'heure actuelle, je suis itération sur tous les dossiers> Subfolders> etc> enfants à vérifier l'entrée d'histoire et à la scène récursivement. Cela devient assez lent maintenant, alors j'ai besoin d'une nouvelle approche.

J'ai proposé deux options mais je veux savoir s'il y a une meilleure approche, ou laquelle est la meilleure.

Option 1 : chaque fois que l'ajout d'un document ou de supprimer un document, itérair le graphe parent et incrémenter / décrémenter une propriété "DocumentCount" stockée dans l'entité de dossier. Cela signifie que l'ajout / suppression d'un minimum de performances. Mais le problème ici est que je dois réellement compter le nombre total de documents, ainsi que le nombre total de documents signalés (en vérifiant les entrées d'historique), de sorte que cela signifie que j'aurai besoin d'un autre champ et d'un autre processus pour appeler quand cela changements d'état. Cela introduit encore plus de complexité comme vérifiant si quelque chose est signalé est un appel de méthode, pas une propriété.

Option 2: Demandez à un travail de minuterie et mettez à jour les propriétés "DocumentationCount" et "NonOpérédocumentCount" de chaque dossier du système, seraient beaucoup de cycles de processeur et semblent gaspillés.

Option 3 : Juste pensé à cela - peut-être itération de chaque document et de voir si le document est un enfant direct ou distant du nœud cible avant d'évaluer serait mieux que d'itération via la récursivité. Je me sens comme ça serait mieux pour les nœuds haut de gamme dans l'arbre, mais itérant sur chaque enfant pour un nœud de bas niveau serait ridicule. Hmmm ...

Je suis tenté de mettre en œuvre l'option 1 .. Quelles autres options y a-t-il?

Answer 1

Si vous connaissez la (s) condition (s) que vous souhaitez décompter lorsque vous ajoutez le nœud à l'arborescence, vous pouvez concevoir votre routine Ajouter pour recourir à travers l'arbre, au lieu de simplement descendre, puis détournez les récursions et mettez-vous à jour.les comptes des nœuds parents.

De même, lorsque vous mettez à jour les nœuds, vous les recurez, puis détournez les récursions et mettez à jour les parents.

Si vous ne connaissez pas la condition (s) à l'avance, vous êtes vissé.Vous n'avez pas d'autre choix que de traverser l'arbre de l'ordre du sens.D'après ce que vous avez dit, il semble que tout ce que vous faites à un nœud est fonction de l'autre des sous-arbres gauche et droit, qui fait ressembler à une traverse postérieure à la bonne réponse.

Remarque: Si ce qui précède n'a pas de sens pour vous, lisez Knuth Vol.1 .