comprobar si 2 nodos del árbol están relacionados (antepasado/descendiente) en O (1) con pre-procesamiento

Question

comprobar si 2 nodos del árbol están relacionados (es decir ancestro-descendiente)

• resolverlo de O (1) tiempo, se permite con O (N) espacio (N = # de nodos)
• pre-procesamiento

Eso es todo. Voy a ir a mi solución (enfoque) a continuación. Por favor, detente si quieres pensar primero.

---

Para una pre-procesamiento decidí hacer una pre-orden (ir de forma recursiva a través de la raíz primero, entonces los niños) y dar una etiqueta a cada nodo.

Voy a explicar las etiquetas en los detalles. Cada etiqueta constará de números naturales separados por comas como "1,2,1,4,5"; la longitud de esta secuencia es igual a (la profundidad del nodo + 1). P.ej. la etiqueta de la raíz es "1", los hijos de la raíz tendrán etiquetas "1,1", "1,2", "1,3", etc. Los nodos del siguiente nivel tendrán etiquetas como "1,1,1" , "1,1,2", ..., "1,2,1", "1,2,2", ...

Suponga que "el número de orden" de un nodo es el "1-based index of this node" en la lista secundaria de su elemento primario.

Regla común: la etiqueta del nodo consta de su etiqueta principal seguida de una coma y "el número de orden" del nodo.

Por lo tanto, para responder si dos nodos están relacionados (es decir ancestro-descendiente) en O (1), voy a comprobar si la etiqueta de uno de ellos es "un prefijo" de la etiqueta de la otra. Aunque no estoy seguro si se puede considerar que esas etiquetas ocupan O (N) espacio. Se espera que

Cualquier críticos con correcciones o un enfoque alternativo.

Answer 1

Puede hacerlo en O (n) tiempo de procesamiento previo, y O (n) el espacio, con O (1) tiempo de consulta, si almacena el número de orden previo y el número de orden posterior para cada vértice y utiliza este hecho:

Para dos nodos dados x e y de un árbol T, x es un antepasado de y si y sólo si x se produce antes y en el recorrido en preorden de T y después de y en el recorrido de post-fin.

(A partir de esta página: http://www.cs.arizona.edu/xiss/numbering.htm)

Lo que hizo en el peor de los casos es Theta (d), donde d es la profundidad del nodo superior, por lo que no es O (1). El espacio tampoco es O (n).

Answer 2

Hay tiempo lineal algoritmos antepasado más bajo común (al menos fuera de línea). Por ejemplo, echar un vistazo here. También puede echar un vistazo al tarjan's offline LCA algorithm. Tenga en cuenta que estos artículos requieren que conozca las parejas para las que realizará el ACV por adelantado. Creo que también hay algoritmos de tiempo de precomputación en tiempo lineal en línea, pero son muy complejos. Por ejemplo, hay un algoritmo de tiempo de precomputación lineal para el problema de consulta mínimo de rango. Por lo que recuerdo, esta solución pasó por el problema de LCA dos veces.El problema con el algoritmo es que tenía una constante tan grande que requiere una entrada enorme para ser realmente más rápido que el algoritmo O (n * log (n)).

Hay un enfoque mucho más simple que requiere O (n * log (n)) memoria adicional y responde de nuevo en tiempo constante.

Espero que esto ayude.

Answer 3

si considera un árbol donde un nodo en el árbol tiene n/2 hijos (por ejemplo), el tiempo de ejecución de la configuración de las etiquetas será tan alto como O (n * n). Entonces este esquema de etiquetado no funcionará ...