Un enlace / árbol cortado es una estructura de datos para representar un bosque , un conjunto de árboles enraizados y ofrece las siguientes operaciones:
- Agregue un árbol que consta de un solo nodo al bosque.
- Dado un nodo en uno de los árboles, desconéctelo (y su subárbol) del árbol del que forma parte.
- Adjunte un nodo a otro nodo como hijo.
- Dado un nodo, encuentre la raíz del árbol al que pertenece. Al realizar esta operación en dos nodos distintos, se puede comprobar si pertenecen al mismo árbol.
Enlace / árbol cortado | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | Árbol | |||||||||||||||
Inventado | mil novecientos ochenta y dos | |||||||||||||||
Inventado por | ||||||||||||||||
Complejidad del tiempo en notación O grande | ||||||||||||||||
|
El bosque representado puede estar formado por árboles muy profundos, por lo que si representamos el bosque como una colección simple de árboles punteros principales , podría llevarnos mucho tiempo encontrar la raíz de un nodo determinado. Sin embargo, si representamos cada árbol del bosque como un enlace / árbol cortado, podemos encontrar a qué árbol pertenece un elemento en O (log ( n )) tiempo amortizado. Además, podemos ajustar rápidamente la colección de árboles de enlace / corte a los cambios en el bosque representado. En particular, podemos ajustarlo para fusionar (vincular) y dividir (cortar) en O ( log (n)) tiempo amortizado .
Los árboles de enlace / corte dividen cada árbol en el bosque representado en caminos separados de vértice, donde cada camino está representado por una estructura de datos auxiliares (a menudo árboles de extensión , aunque el documento original es anterior a los árboles de extensión y, por lo tanto, utiliza árboles de búsqueda binarios sesgados). Los nodos de la estructura de datos auxiliares están ordenados por su profundidad en el árbol representado correspondiente. En una variación, Partición ingenua , las rutas están determinadas por las rutas y nodos a los que se accedió más recientemente, similar a los árboles de tango . En Partitioning by Size, las rutas están determinadas por el hijo más pesado (hijo con la mayoría de los hijos) del nodo dado. Esto da una estructura más complicada, pero reduce el costo de las operaciones de amortizado O (log n) al peor de los casos O (log n). Tiene usos para resolver una variedad de problemas de flujo de red y para intercambiar conjuntos de datos.
En la publicación original, Sleator y Tarjan se refirieron a los árboles de enlace / corte como "árboles dinámicos" o "árboles dinámicos dinámicos".
Estructura
Tomamos un árbol donde cada nodo tiene un grado arbitrario de nodos desordenados y lo dividimos en rutas. A esto lo llamamos el árbol representado . Estas rutas están representadas internamente por árboles auxiliares (aquí usaremos árboles esparcidos), donde los nodos de izquierda a derecha representan la ruta desde la raíz hasta el último nodo de la ruta. Los nodos que están conectados en el árbol representado que no están en la misma ruta preferida (y, por lo tanto, no están en el mismo árbol auxiliar) se conectan mediante un puntero de ruta-padre . Este puntero se almacena en la raíz del árbol auxiliar que representa la ruta.
Caminos preferidos
Cuando se realiza un acceso a un nodo v en el árbol representado , la ruta que se toma se convierte en la ruta preferida . El hijo preferido de un nodo es el último hijo que estaba en la ruta de acceso, o nulo si el último acceso fue a vo si no se realizaron accesos a esta rama particular del árbol. Un borde preferido es el borde que conecta al hijo preferido con v .
En una versión alternativa, las rutas preferidas las determina el niño más pesado.
Operaciones
Las operaciones que nos interesan son FindRoot (nodo v), cortar (nodo v), enlace (nodo v, nodo w) y ruta (nodo v). Cada operación se implementa utilizando la subrutina Access (Nodo v). Cuando accedemos a un vértice v , la ruta preferida del árbol representado se cambia a una ruta desde la raíz R del árbol representado hasta el nodo v . Si un nodo en la ruta de acceso tenía anteriormente un hijo u preferido , y la ruta ahora va al hijo w , el borde preferido anterior se elimina (se cambia a un puntero de ruta-padre ) y la nueva ruta ahora pasa por w .
Acceso
Después de realizar un acceso al nodo v , ya no tendrá ningún hijo preferido y estará al final de la ruta. Dado que los nodos en el árbol auxiliar están codificados por profundidad, esto significa que cualquier nodo a la derecha de v en el árbol auxiliar debe desconectarse. En un árbol de distribución, este es un procedimiento relativamente simple; abrimos en v , lo que lleva a v a la raíz del árbol auxiliar. Luego desconectamos el subárbol derecho de v , que es cada nodo que vino debajo de él en la ruta preferida anterior. La raíz del árbol desconectado tendrá un puntero de ruta-padre, que apuntamos a v .
Ahora caminamos por el árbol representado hasta la raíz R , rompiendo y restableciendo la ruta preferida cuando sea necesario. Para hacer esto, seguimos el puntero path-parent desde v (dado que v ahora es la raíz, tenemos acceso directo al puntero path-parent). Si la ruta en la que está v ya contiene la raíz R (dado que los nodos están codificados por profundidad, sería el nodo más a la izquierda en el árbol auxiliar), el puntero de la ruta principal será nulo y ya hemos terminado el acceso. De lo contrario, seguimos el puntero a algún nodo en otro camino w . Queremos romper la antigua ruta preferida de w y volver a conectarla a la ruta en la que se encuentra v . Para hacer esto, abrimos en w , y desconectamos su subárbol derecho, estableciendo su puntero de ruta-padre en w . Dado que todos los nodos están codificados por profundidad, y cada nodo en la ruta de v es más profundo que cada nodo en la ruta de w (ya que son hijos de w en el árbol representado), simplemente conectamos el árbol de v como el hijo correcto de w . Volvemos a desplegar en v , que, dado que v es un hijo de la raíz w , simplemente rota v a la raíz. Repetimos todo este proceso hasta que el puntero de ruta y los padres de v es nula, y en ese momento se está en la misma ruta preferente como la raíz del árbol representado R .
FindRoot
FindRoot se refiere a encontrar la raíz del árbol representado que contiene el nodo v . Dado que la subrutina de acceso pone v en la ruta preferida, primero ejecutamos un acceso. Ahora el nodo v está en la misma ruta de acceso preferida, y por lo tanto el mismo árbol auxiliar como la raíz R . Dado que los árboles auxiliares están codificados por profundidad, la raíz R será el nodo más a la izquierda del árbol auxiliar. Por lo que sólo tiene que elegir el hijo izquierdo de v de forma recursiva hasta que podamos ir más lejos, y este nodo es la raíz R . La raíz puede ser linealmente profunda (lo que es el peor de los casos para un árbol de distribución), por lo tanto, la distribuimos para que el próximo acceso sea rápido.
Cortar
Aquí nos gustaría cortar el árbol representado en el nodo v . Primero accedemos a v . Esto coloca todos los elementos inferiores a v en el árbol representado como el hijo derecho de v en el árbol auxiliar. Todos los elementos ahora en el subárbol izquierdo de v son los nodos más altos que v en el árbol representado. Por lo tanto, desconectamos el hijo izquierdo de v (que todavía mantiene un vínculo con el árbol representado original a través de su puntero de ruta-padre). Ahora v es la raíz de un árbol representado. Acceder a v también rompe la ruta preferida debajo de v , pero ese subárbol mantiene su conexión con v a través de su puntero de ruta principal.
Enlace
Si v es la raíz de un árbol yw es un vértice en otro árbol, vincule los árboles que contienen v y w agregando el borde (v, w), haciendo que w sea el padre de v . Para hacer esto accedemos tanto a v como a w en sus respectivos árboles, y hacemos que w sea el hijo izquierdo de v . Dado que v es la raíz y los nodos están codificados por profundidad en el árbol auxiliar, acceder a v significa que a v no le quedará ningún hijo en el árbol auxiliar (ya que como raíz es la profundidad mínima). Agregar w como hijo izquierdo lo convierte efectivamente en el padre de v en el árbol representado.
Camino
Para esta operación deseamos hacer alguna función agregada sobre todos los nodos (o bordes) en la ruta desde la raíz R al nodo v (como "suma" o "mínimo" o "máximo" o "aumento", etc.). Para hacer esto accedemos a v , lo que nos da un árbol auxiliar con todos los nodos en el camino desde la raíz R al nodo v . La estructura de datos se puede aumentar con los datos que deseamos recuperar, como los valores mínimos o máximos, o la suma de los costos en el subárbol, que luego se pueden devolver desde una ruta determinada en tiempo constante.
Pseudocódigo de operaciones
Switch-Preferred-Child (x, y): padre-ruta (derecha (x)) = x derecha (x, y)
Acceso (v): Switch-Path-Parent (v, nulo) while (v no es root) w = ruta-padre (v) esparcir (w) Switch-Path-Parent (w, v) path-parent (v) = nulo v = w esparcimiento (v)
Enlace (v, w): Acceso (v) Acceso (w) izquierda (v) = w
Cortar (v): Acceso (v) izquierda (v) = nulo
Análisis
El corte y el enlace tienen un costo de O (1), más el del acceso. FindRoot tiene un límite superior amortizado O (log n ), más el costo del acceso. La estructura de datos se puede aumentar con información adicional (como el nodo con valor mínimo o máximo en sus subárboles, o la suma), según la implementación. Por lo tanto, Path puede devolver esta información en tiempo constante más el límite de acceso.
Por lo que queda por acotar el acceso para encontrar nuestro tiempo de ejecución.
Access hace uso de splaying, que sabemos que tiene un límite superior amortizado O (log n ). Entonces, el análisis restante trata sobre la cantidad de veces que necesitamos expandir. Esto es igual al número de cambios secundarios preferidos (el número de bordes cambiados en la ruta preferida) a medida que recorremos el árbol.
Delimitamos el acceso mediante una técnica llamada Descomposición pesada-ligera .
Descomposición pesada-ligera
Esta técnica llama a un borde pesado o ligero dependiendo del número de nodos en el subárbol. representa el número de nodos en el subárbol de v en el árbol representado. Un borde se llama pesado si el tamaño (v)> 1 ⁄ 2 tamaño (padre (v)). Por lo tanto, podemos ver que cada nodo puede tener como máximo 1 borde pesado . Un borde que no es un borde pesado se denomina borde ligero .
La profundidad de luz se refiere al número de bordes de luz en un camino dado desde la raíz hasta el vértice v . Profundidad de luz ≤ lg n porque cada vez que atravesamos un borde de luz disminuimos el número de nodos en al menos un factor de 2 (ya que puede tener como máximo la mitad de los nodos del padre).
Por lo tanto, un borde dado en el árbol representado puede ser cualquiera de las cuatro posibilidades: mucho preferido , pesado no preferido , ligero preferido o ligero no preferido .
Primero probamos un límite superior.
O (log 2 n ) límite superior
La operación de distribución del acceso nos da log n , por lo que debemos limitar el número de accesos a log n para demostrar el límite superior de O (log 2 n ).
Cada cambio de borde preferido da como resultado la formación de un nuevo borde preferido. Entonces contamos el número de bordes preferidos formados. Dado que hay como máximo log n bordes que son claros en cualquier camino dado, hay como máximo log n bordes claros que cambian a los preferidos.
El número de bordes pesados que se prefieren puede ser para cualquier operación dada, pero es amortizado. En una serie de ejecuciones, podemos hacer que se prefieran n -1 bordes pesados (ya que hay como máximo n -1 bordes pesados en total en el árbol representado), pero a partir de entonces el número de bordes pesados que se prefieren es igual al número de bordes gruesos que se volvieron poco preferidos en un paso anterior. Por cada borde pesado que no se prefiera, se debe preferir un borde ligero. Ya hemos visto que el número de bordes claros que pueden convertirse en preferidos es, como máximo, log n . Por tanto, el número de bordes pesados que se prefieren para m operaciones es. Sobre suficientes operaciones () esto promedia a .
Mejora al límite superior de O (log n )
Hemos limitado el número de cambios de hijo preferido en , por lo que si podemos demostrar que cada cambio de hijo preferido tiene un costo amortizado O (1), podemos vincular la operación de acceso a. Esto se hace utilizando el método potencial .
Sea s (v) el número de nodos bajo v en el árbol de árboles auxiliares. Entonces la función potencial. Sabemos que el costo amortizado de distribución está limitado por:
Sabemos que después de desplegar, v es el hijo de su nodo padre de ruta w . Entonces sabemos que:
Usamos esta desigualdad y el costo de acceso amortizado para lograr una suma telescópica que está limitada por:
donde R es la raíz del árbol representado, y sabemos que el número de cambios secundarios preferidos es. s ( R ) = n , entonces tenemos amortizado.
Solicitud
Los árboles de enlace / corte se pueden utilizar para resolver el problema de conectividad dinámica para gráficos acíclicos. Dados dos nodos xey, están conectados si y solo si FindRoot (x) = FindRoot (y). Otra estructura de datos que se puede utilizar para el mismo propósito es el árbol de viajes de Euler .
Para resolver el problema de flujo máximo , los árboles de enlace / corte se pueden utilizar para mejorar el tiempo de ejecución del algoritmo de Dinic de a .
Ver también
Otras lecturas
- Sleator, DD; Tarjan, RE (1983). "Una estructura de datos para árboles dinámicos". Actas del decimotercer simposio anual de ACM sobre teoría de la computación - STOC '81 (PDF) . pag. 114. doi : 10.1145 / 800076.802464 .
- Sleator, DD; Tarjan, RE (1985). "Árboles de búsqueda binarios autoajustables" (PDF) . Revista de la ACM . 32 (3): 652. doi : 10.1145 / 3828.3835 .
- Goldberg, AV ; Tarjan, RE (1989). "Encontrar circulaciones de coste mínimo cancelando ciclos negativos". Revista de la ACM . 36 (4): 873. doi : 10.1145 / 76359.76368 . - Aplicación a la circulación de costes mínimos
- Árboles Link-Cut en: notas de conferencias en estructuras de datos avanzadas, primavera de 2012, conferencia 19. Prof. Erik Demaine, Scribes: Scribes: Justin Holmgren (2012), Jing Jian (2012), Maksim Stepanenko (2012), Mashhood Ishaque (2007) ).
- http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf