Processando cada folha sob um nó em uma árvore eficientemente

Question

versão curta: Em uma árvore (não-binário) com muitos níveis de crianças, onde cada nó pode ter várias folhas, qual é a melhor maneira de folhas de registro que atendam a uma determinada condição dada a um nó?

versão longa e complicada: Digamos que você tenha pastas, que podem conter mais pastas. Na produção, meu sistema tem cerca de 15 camadas de pastas no mais profundo. Cada pasta pode ter documentos.

Quando um usuário navega para uma pasta, eles precisam saber quantos documentos estão nessa pasta, total. Eles também precisam saber quantos desses documentos foram "sinalizados". Os documentos podem ser sinalizados se, após um determinado período de tempo, eles não foram atualizados. Isso é determinado com base nas entradas do histórico - faça a última entrada de histórico para a pasta, se for maior que x, então é sinalizada.

Agora estou iterando sobre todas as pastas> subpastas> etc> crianças para verificar a entrada de histórico e contravelar recursivamente. Isso está ficando muito lento agora, então eu preciso de uma nova abordagem.

Eu inventei duas opções, mas quero saber se há uma melhor abordagem, ou qual deles é melhor.

Opção 1 : Sempre adicionar um documento ou remover um documento, iterar o gráfico pai e incremento / diminuição de uma propriedade "DocumentCount" que é armazenado na entidade da pasta. Isso significa que adicionar / remover assumir um atendimento de desempenho mínimo. Mas o problema aqui é que eu realmente preciso contar o número total de documentos, bem como o número total de documentos que são sinalizados (verificando entradas do histórico), de modo que eu precisarei de outro campo e outro processo para chamar quando isso alterações de status. Isso introduz ainda mais complexidade como verificar se algo é ou não sinalizado é uma chamada de método, não uma propriedade.

Opção 2: Ter um trabalho de temporizador Executar e atualizar as propriedades "DocumentCount" e "UnoDDocumentCount" de cada pasta no sistema, seriam muitos ciclos de CPU e parece desperdiçador.

Opção 3 : Apenas pensei nisso - talvez iterating sobre cada documento e ver se o documento é uma criança direta ou distante do nó alvo antes de avaliar, seria melhor do que iterating via recursion. Eu sinto que isso seria melhor para nós no alto da árvore, mas iterando sobre cada criança para um nó de baixo nível seria ridículo. Hmmm ...

Estou tentado a implementar a opção 1 .. Que outras opções existem?

Answer 1

Se você conhece a (s) condição (s) que você deseja contabilizar quando adicionar o nó à árvore, você pode projetar sua rotina adicionar para recorrer através da árvore, em vez de simplesmente descer e, em seguida, descontrair as recursões e atualizaros registros nos nós pai.

Da mesma forma, à medida que você atualiza nós, recorre para eles e, em seguida, descontraindo as recursões e atualiza os pais.

Se você não conhece a (s) condição (s) de antemão, você está ferrado.Você não tem escolha a não ser atravessar a árvore em qualquer ordem faz sentido.Pelo que você disse, parece que o que você está fazendo em um nó é uma função do que sejam as subárvores esquerdas e certas, o que faz uma encaminhamento percorrer a resposta certa.

Nota: Se o acima não fizer sentido para você, leia knuth vol.1 .