Estoy buscando el algoritmo más eficiente para tomar un árbol (almacenado como una lista de bordes; O como una lista de asignaciones del nodo principal a una lista de nodos secundarios); y produce, para CADA nodo, una lista de todos los nodos que descienden de él (nivel hoja y nivel no hoja).
La implementación debe ser a través de bucles en lugar de recusión, debido a la escala; e idealmente debería ser O (N).
Esta pregunta SO cubre una solución estándar razonablemente obvia para encontrar la respuesta para UN nodo en un árbol. Pero obviamente, repetir ese algoritmo en cada nodo del árbol es altamente ineficiente (fuera de mi cabeza, O (NlogN) a O (N ^ 2)).
La raíz del árbol es conocida. El árbol tiene una forma absolutamente arbitraria (por ejemplo, no N-nary, no está equilibrado de ninguna manera, forma o forma, no tiene una profundidad uniforme): algunos nodos tienen 1-2 hijos, algunos tienen 30K hijos.
En un nivel práctico (aunque no debería afectar el algoritmo) el árbol tiene ~ 100K-200K nodos.
fuente
Respuestas:
Si realmente desea PRODUCIR cada lista como copias diferentes, no puede esperar lograr un espacio mejor que n ^ 2 en el peor de los casos. Si solo necesita ACCESO a cada lista:
Realizaría un recorrido en orden del árbol a partir de la raíz:
http://en.wikipedia.org/wiki/Tree_traversal
Luego, para cada nodo en el árbol, almacene el número mínimo en orden y el número máximo en orden en su subárbol (esto se mantiene fácilmente a través de la recursión, y puede simular eso con una pila si lo desea).
Ahora coloca todos los nodos en una matriz A de longitud n donde el nodo con el número en orden i está en la posición i. Luego, cuando necesite encontrar la lista para un nodo X, busque en A [X.min, X.max]; tenga en cuenta que este intervalo incluirá el nodo X, que también puede repararse fácilmente.
Todo esto se logra en O (n) tiempo y ocupa O (n) espacio.
Espero que esto ayude.
fuente
La parte ineficiente no es atravesar el árbol, sino construir las listas de nodos. Parecería sensato crear la lista así:
Como cada nodo descendiente se copia en la lista de cada padre, terminamos con una complejidad O (n log n) en promedio para árboles balanceados, y O (n²) en el peor de los casos para árboles degenerados que realmente son listas vinculadas.
Podemos caer a O (n) u O (1) dependiendo de si necesita hacer alguna configuración si usamos el truco de calcular las listas de manera perezosa. Supongamos que tenemos un
child_iterator(node)
que nos da los hijos de ese nodo. Entonces podemos definir trivialmente un tipodescendant_iterator(node)
como este:Una solución no recursiva está mucho más involucrada, ya que el flujo de control del iterador es complicado (¡rutinas!). Actualizaré esta respuesta más tarde hoy.
Dado que el recorrido de un árbol es O (n) y la iteración sobre una lista también es lineal, este truco difiere completamente el costo hasta que se pague de todos modos. Por ejemplo, imprimir la lista de descendientes para cada nodo tiene O (n²) peor complejidad: iterar sobre todos los nodos es O (n) y, por lo tanto, iterar sobre los descendientes de cada nodo, ya sea que estén almacenados en una lista o calculados ad hoc .
Por supuesto, esto no funcionará si necesita una colección real para trabajar.
fuente
Este breve algoritmo debería hacerlo. Echa un vistazo al código.
public void TestTreeNodeChildrenListing()
El algoritmo en realidad pasa por los nodos del árbol en secuencia y mantiene la lista de padres del nodo actual. Según su requisito, el nodo actual es un elemento secundario de cada nodo primario que se agrega a todos y cada uno de ellos como elemento secundario.
El resultado final se almacena en el diccionario.
fuente
Normalmente, solo usaría un enfoque recursivo, ya que le permite cambiar su orden de ejecución para que pueda calcular el número de hojas comenzando desde las hojas hacia arriba. Como tendría que usar el resultado de su llamada recursiva para actualizar el nodo actual, se necesitaría un esfuerzo especial para obtener una versión recursiva de cola. Si no toma ese esfuerzo, entonces, por supuesto, este enfoque simplemente explotaría su pila para un árbol grande.
Dado que nos dimos cuenta de que la idea principal es obtener un orden de bucle que comience en las hojas y regrese hacia la raíz, la idea natural que se nos ocurre es realizar una clasificación topológica en el árbol. La secuencia resultante de nodos puede atravesarse linealmente para sumar el número de hojas (suponiendo que pueda verificar que un nodo es una hoja
O(1)
). La complejidad temporal general del tipo topológico esO(|V|+|E|)
.Supongo que su
N
es el número de nodos, que|V|
normalmente sería (de la nomenclatura DAG). El tamaño de,E
por otro lado, depende en gran medida de la aridad de su árbol. Por ejemplo, un árbol binario tiene como máximo 2 aristas por nodo, por lo tanto,O(|E|) = O(2*|V|) = O(|V|)
en ese caso, lo que daría como resultado unO(|V|)
algoritmo general . Tenga en cuenta que debido a la estructura general de un árbol, no puede tener algo asíO(|E|) = O(|V|^2)
. De hecho, dado que cada nodo tiene un padre único, puede tener como máximo un borde para contar por nodo cuando considera solo las relaciones padre, por lo que para los árboles tenemos una garantía de esoO(|E|) = O(|V|)
. Por lo tanto, el algoritmo anterior siempre es lineal en el tamaño del árbol.fuente