Problema de ancestro de nivel
En teoría de grafos y ciencias de la computación teóricas , el problema del ancestro de nivel es el problema de preprocesar un árbol enraizado T dado en una estructura de datos que puede determinar el ancestro de un nodo dado a una distancia dada de la raíz del árbol.
Más precisamente, dejar que T sea un árbol con n nodos, y dejar que v sea un nodo arbitrario de T . La consulta de nivel antecesor LA ( v , d ) solicita el antepasado del nodo v en la profundidad d , donde la profundidad de un nodo v en un árbol es el número de bordes en la ruta más corta desde la raíz del árbol al nodo v . Es posible resolver este problema en tiempo constante por consulta, luego de un algoritmo de preprocesamiento que toma O ( n ) y que construye una estructura de datos que usa O ( n ) espacio de almacenamiento. [1] [2]
La forma más sencilla de encontrar un antepasado de nivel de un nodo es trepar por el árbol hacia la raíz del árbol. En el camino a la raíz del árbol, se puede visitar cada antepasado de un nodo y, por lo tanto, informar. En este caso, no es necesario preprocesar el árbol y el tiempo para responder una consulta es O ( h ), donde "h" es la altura del árbol. Este enfoque no es factible en situaciones en las que el árbol puede tener una gran altura y es necesario procesar una gran cantidad de consultas.
Alternativamente, todas las posibles soluciones se pueden calcular previamente y almacenar en una tabla. En este caso, las consultas se pueden responder en O (1) pero el espacio y el tiempo de preprocesamiento es O ( n 2 ).
Las consultas más simples que se pueden responder en tiempo constante sin ningún procesamiento previo son LA ( v , 0) y LA ( v , profundidad ( v )). En el primer caso, la respuesta es siempre la raíz del árbol y en el último caso, la respuesta es el propio nodo v . Cada uno de estos resultados toma O (1).
Almacenar las rutas a través del árbol en una lista sesgada de acceso aleatorio binario permite que el árbol aún se extienda hacia abajo un O (1) paso a la vez, pero ahora permite que la búsqueda continúe en O (log ( p )), donde "p "es la distancia desde v hasta la profundidad solicitada. Este enfoque es factible cuando el árbol es particularmente ancho o se extenderá en línea y, por lo tanto, no se puede preprocesar de manera efectiva, ya que el tiempo de almacenamiento y acceso está determinado puramente por la longitud de la ruta. [3]
