O (1) algoritmo para determinar si el nodo es descendiente de otro nodo en un árbol de múltiples vías?

Solución:

¿Son sus árboles de entrada siempre estáticos? Si es así, puede utilizar un algoritmo de ancestro común más bajo para responder a la pregunta del descendiente en O (1) tiempo con una construcción de tiempo / espacio O (n). A una consulta de LCA se le asignan dos nodos y se le pregunta cuál es el nodo más bajo del árbol cuyo subárbol contiene ambos nodos. Luego, puede responder la consulta IsDescendent con una sola consulta LCA, si LCA (A, B) == A o LCA (A, B) == B, entonces uno es descendiente del otro.

Este tutorial del algoritmo Topcoder ofrece una discusión exhaustiva del problema y algunas soluciones en varios niveles de complejidad / eficiencia del código.

No sé si esto encajaría con su problema, pero una forma de almacenar jerarquías en bases de datos, con funciones rápidas de “darme todo desde este nodo y hacia abajo” es almacenar una “ruta”.

Por ejemplo, para un árbol que se ve así:

    +-- b
    |
a --+       +-- d
    |       |
    +-- c --+
            |
            +-- e

almacenaría las filas de la siguiente manera, asumiendo que la letra en el árbol anterior es el “id” de cada fila:

id    path
a     a
b     a*b
c     a*c
d     a*c*d
e     a*c*e

Para encontrar todos los descendientes de un nodo en particular, haría una consulta “EMPIEZA CON” en la columna de la ruta, es decir. todos los nodos con una ruta que comienza con a*c*

Para saber si un nodo en particular es descendiente de otro nodo, vería si la ruta más larga comenzaba con la ruta más corta.

Entonces, por ejemplo:

• e es descendiente de un desde a*c*e comienza con a
• d es descendiente de c ya que a*c*d comienza con a*c

¿Sería útil en su caso?

Atravesar cualquier árbol requerirá pasos de “profundidad de árbol”. Por lo tanto, si mantiene una estructura de árbol equilibrada, se puede demostrar que necesitará O (log n) operaciones para su buscar operación. Por lo que tengo entendido, tu árbol se ve especial y no puedes mantenerlo de manera equilibrada, ¿verdad? Entonces Sobre) será posible. Pero esto es malo durante la creación del árbol de todos modos, por lo que probablemente morirá antes de usar el buscar de todas formas…

Dependiendo de la frecuencia con la que lo necesitará buscar operación en comparación con insertar, puede decidir pagar durante insertar para mantener una estructura de datos adicional. Sugeriría un hash si realmente necesitar amortizado O (1). En cada operación de inserción que pones todos padres de un nodo en una tabla hash. Según tu descripción, esto podría ser Sobre) elementos en un dado insertar. Si lo haces norte inserciones esto suena mal (hacia O (n ^ 2)), pero en realidad su árbol no se puede degradar ese mal, por lo que probablemente obtenga un tamaño hastable total amortizado de O (n log n). (en realidad, el log n parte depende del grado de degradación de su árbol. Si espera que se degrade al máximo, no lo haga).

Entonces, pagarías sobre O (log n) en cada insertary obtenga eficiencia hashtable O (1) para buscar.

---

---

Utiliza Nuestro Buscador