Hispanopedia WikiEn la teoría de grafos y la informática teórica , el problema del ancestro de nivel es el problema de preprocesar un árbol enraizado T dado en una estructura de datos que pueda determinar el ancestro de un nodo dado a una distancia dada de la raíz del árbol.
Más precisamente, sea T un árbol con raíz y n nodos, y sea v un nodo arbitrario de T. La consulta de ancestro de nivel LA( v , d ) solicita el ancestro del nodo v a profundidad d , donde la profundidad de un nodo v en un árbol es el número de aristas en el camino más corto desde la raíz del árbol hasta el nodo v . Es posible resolver este problema en tiempo constante por consulta, después de un algoritmo de preprocesamiento que toma O( n ) y que construye una estructura de datos que utiliza un espacio de almacenamiento de O( n ). [ 1 ] [ 2 ]
Algoritmo de puntero de salto
El algoritmo de punteros de salto [ 1 ] preprocesa un árbol en tiempo O( n log n ) y responde consultas de ancestros de nivel en tiempo O(log n ). El algoritmo de punteros de salto asocia hasta log n punteros a cada vértice del árbol. Estos punteros se llaman punteros de salto porque saltan hacia arriba en el árbol, hacia la raíz del mismo. Para un nodo v dado de un árbol, el algoritmo almacena una matriz de longitud saltadores dondeEl i -ésimo elemento de este arreglo apunta al 2i - ésimo ancestro de v . El uso de esta estructura de datos nos permite saltar hasta la mitad del árbol desde cualquier nodo dado. Cuando se le pide al algoritmo que procese una consulta, saltamos repetidamente hacia arriba en el árbol usando estos punteros. El número de saltos será como máximo log n y, por lo tanto, las consultas se pueden responder en log n tiempo.
Algoritmo de escalera
El algoritmo de escalera [ 1 ] se basa en la idea de simplificar un árbol en una colección de caminos . Esto se debe a que los caminos son más fáciles de consultar cuando se trata de consultas de ancestros de nivel. Consideremos un camino P que consta de n nodos con raíz en un nodo r. Podemos almacenar el camino en un arreglo de tamaño n llamado Escalera y podemos responder rápidamente una consulta de ancestro de nivel LA(v, d) devolviendo Escalera[d] si profundidad(v)≤d. Esto tomará O( 1 ). Sin embargo, esto solo funcionará si el árbol dado es un camino. De lo contrario, necesitamos descomponerlo en caminos. Esto se hace en dos etapas: descomposición de caminos largos y extensión de los caminos largos en escaleras.
Etapa 1: descomposición de ruta larga
Este es un método recursivo que descompone un árbol dado en caminos. Esta etapa comienza encontrando el camino más largo de la raíz a la hoja en el árbol. Luego elimina este camino rompiendo sus vínculos con el árbol, lo que dividirá el resto del árbol en subárboles , y luego procesa recursivamente cada subárbol. Cada vez que se descompone un camino, se crea un arreglo asociado con el camino que contiene los elementos en el camino desde la raíz hasta la hoja. El caso base de esta recursión es cuando el árbol es un camino, en cuyo caso su eliminación deja un grafo vacío. Cada vértice v tiene una escalera única que es la escalera que lo contiene y la llamamos "escalera de v". Sin embargo, después de esta etapa de preprocesamiento, las consultas no se pueden responder rápidamente. De hecho, para responder una consulta de ancestro de nivel, el algoritmo necesita saltar de un camino a otro hasta llegar a la raíz, y puede haber Θ( √ n ) de tales caminos en un camino de hoja a raíz. Esto nos lleva a un algoritmo que puede preprocesar el árbol en tiempo O( n ) y responder consultas en O( √n ). Para alcanzar el tiempo de consulta óptimo, necesitamos procesar los resultados en una segunda etapa que se describe a continuación.
Etapa 2: convertir los caminos largos en escaleras
La primera etapa del algoritmo descompone el árbol en varios caminos disjuntos. En la segunda etapa, cada camino se extiende, por lo que los caminos resultantes no serán mutuamente excluyentes. En la primera etapa, cada camino se asocia con un arreglo de tamaño h' . Extendemos este camino agregando los h' ancestros inmediatos en la parte superior del mismo arreglo. Esto extenderá cada arreglo al doble de su tamaño original como máximo, lo que dará como resultado un total de 2n nodos en todas las escaleras. Nótese que el número de escaleras no cambia y la escalera de cada nodo permanece igual. Aunque un nodo v puede aparecer en varios caminos, su escalera es la que se le asoció en la primera etapa. Estas dos etapas se pueden procesar en tiempo O( n ), pero el tiempo de consulta aún no es constante. Consideremos una consulta de ancestro de nivel en un nodo u de altura h. Al recorrer la parte superior de la escalera de u, se alcanzará un vértice de altura al menos 2h . Observe que todos los nodos tienen una altura de al menos 1 y, por lo tanto, después de hacer esto i veces, llegamos a un nodo de altura de al menos 2i y , por lo tanto, necesitamos hacer esto como máximo log n veces. Esto nos da un tiempo de consulta de O(log n ).
Etapa 3: combinación de ambos enfoques
Resulta que el algoritmo de escalera no funciona por sí solo. De hecho, el algoritmo de puntero de salto y el algoritmo de escalera se complementan. Los dos algoritmos funcionan en direcciones opuestas: el algoritmo de puntero de salto realiza saltos exponencialmente decrecientes y el algoritmo de escalera realiza saltos exponencialmente crecientes. Una combinación de ambos algoritmos puede responder consultas en tiempo O( 1 ). Un solo puntero de salto lleva cualquier consulta al menos hasta la mitad del árbol, después de lo cual subir solo una escalera responderá la consulta. Esto resulta en un tiempo de preprocesamiento de O( n log n ) y un tiempo de consulta de O( 1 ). El preprocesamiento se puede reducir aún más a tiempo O( n ) mediante la aplicación del Método de los Cuatro Rusos , en el que el árbol se reduce a un árbol más pequeño con preprocesamiento lineal y a una colección de árboles muy pequeños, que son lo suficientemente pequeños como para que una enumeración exhaustiva de todos los árboles y el preprocesamiento de esos árboles siga siendo tiempo O( n ). Basta con árboles de tamaño (log n )/4.
La solución de Berkman y Vishkin
Una solución diferente se debe a Berkman y Vishkin. [ 2 ] [ 3 ] Esta solución se basa en la técnica de recorrido de Euler para procesar árboles. La observación principal es que LA( v , d ) es el primer nodo de profundidad d que aparece en el recorrido de Euler después de la última aparición de v . Por lo tanto, al construir el recorrido de Euler y la información asociada sobre la profundidad, el problema se reduce a una consulta sobre arreglos, llamada encontrar más pequeño (FS). Para un arreglo A , y un índice válido i , FS( i , x ) devuelve el primer índice j > i tal que A [ i ] < x (aquí, usamos x = d +1). Una solución eficiente al problema FS es difícil en general, pero más fácil para el caso especial que surge de los recorridos de Euler; en este caso, los elementos adyacentes difieren en ±1. Esta idea produce un tiempo de consulta O(1), con un algoritmo de preprocesamiento de complejidad O( n log n ). El tiempo de preprocesamiento se mejora a O( n ) mediante la aplicación del Método de los Cuatro Rusos .
Véase también
Referencias
- 1 2 3 Bender, Michael A. ; Farach-Colton, Martin (2004). "El problema del ancestro de nivel simplificado" . Theor. Comput. Sci . 321 : 5–12 . doi : 10.1016/j.tcs.2003.05.002 .
- 1 2 Berkman, Omer; Vishkin, Uzi (abril de 1994). "Encontrar ancestros de nivel en árboles" . J. Comput. Syst. Sci . 2. 48 (2): 214– 230. doi : 10.1016/S0022-0000(05)80002-9 .
- ↑ Ben-Amram, Amir M. (2009). "The Euler Path to Static Level-Ancestors". arXiv : 0909.1030v1 [ cs.DS ].
- informática teórica
- Árboles (teoría de grafos)