Procesando cada hoja debajo de un nodo en un árbol de manera eficiente

Question

versión corta: En un árbol (no binario) con muchos niveles de niños, donde cada nodo puede tener múltiples hojas, ¿cuál es la mejor manera de hojas de tally que cumplen con una determinada condición dada un nodo?

Long, versión enrevesada: Di que tiene carpetas, que pueden contener más carpetas. En la producción, mi sistema tiene aproximadamente 15 capas de carpetas en la más profunda. Cada carpeta puede tener documentos.

Cuando un usuario navega a una carpeta, deben saber cuántos documentos están en esa carpeta, total. También necesitan saber cuántos de esos documentos han sido "marcados". Los documentos se pueden marcar si, después de un cierto período de tiempo, no se han actualizado. Esto se determina en función de las entradas de historial: tome la última entrada del historial para la carpeta, si es más grande que x, entonces se marca.

Ahora mismo estoy iterando sobre todas las carpetas> Subfolders> Etc> Niños para verificar la entrada de la historia y el tally recursivamente. Esto se está poniendo bastante lento ahora, así que necesito un nuevo enfoque.

Me he encontrado con dos opciones pero quiero saber si hay un mejor enfoque, o cuál de estos es mejor.

Opción 1 : Siempre que agregue un documento o la eliminación de un documento, ite el gráfico de padres e incrementa / disminuya una propiedad "DOCUMENTECOUNT" que se almacena en la entidad de la carpeta. Esto significa que agregar / eliminar tome un mínimo de rendimiento. Pero el problema aquí es que en realidad necesito contar el número total de documentos, así como el número total de documentos que están marcados (al verificar las entradas de historial), por lo que significa que necesitaré otro campo y otro proceso para llamar cuando esto cambios de estado. Esto introduce aún más complejidad a medida que se comprueba si algo está marcado, es una llamada de método, no una propiedad.

Option 2: tiene un trabajo de temporizador Ejecutar y actualizar las propiedades "DocumentCount" y "UNOPEDDOCUDCULSCOUNTE" de cada carpeta en el sistema, serían muchos ciclos de CPU y parecerían un desperdicio.

Option 3 : Pensamiento de esto, tal vez iterando sobre cada documento y ver si el documento es un niño directo o distante del nodo objetivo antes de evaluar sería mejor que el iteración a través de la recursión. Siento que esto sería mejor para los nodos altos en el árbol, pero iterando sobre todos los niños para un nodo de bajo nivel sería ridículo. Hmmm ...

Estoy tentado a implementar la opción 1. ¿Qué otras opciones hay?

Answer 1

Si conoce la (s) condición (s) que desea recuentar cuando agrega el nodo al árbol, puede diseñar su rutina Agregar para recurrir a través del árbol, en lugar de volver a bajar y volver a descender las recursiones y actualizar.Los contabeles en los nodos primarios.

De manera similar, a medida que actualizó los nodos, le recurre a ellos y luego relaja las recursiones y actualice a los padres.

Si no conoce la (s) condición (s) de antemano, está atornillado.No tiene más remedio que recorrer el árbol en cualquier orden tenga sentido.Por lo que ha dicho, suena como si fuera lo que esté haciendo en un nodo sea una función de lo que sea de los subárboles izquierdo y derecho, lo que hace que un desplazamiento posterior sea la respuesta correcta.

Nota: Si lo anterior no tiene sentido para usted, lea KNURTH VOL.1 .