Un árbol de tango es un tipo de árbol de búsqueda binario propuesto por Erik D. Demaine , Dion Harmon, John Iacono y Mihai Pătrașcu en 2004. [1] Lleva el nombre de Buenos Aires , de la que el tango es emblemático.
Es un árbol de búsqueda binaria en línea que logra un relación competitiva en relación con el árbol de búsqueda binario óptimo fuera de línea , mientras que solo se usabits adicionales de memoria por nodo. Esto mejoró la relación competitiva más conocida anterior, que era.
Estructura
Los árboles de tango funcionan dividiendo un árbol de búsqueda binario en un conjunto de rutas preferidas , que a su vez se almacenan en árboles auxiliares (por lo que el árbol de tango se representa como un árbol de árboles).
Árbol de referencia
Para construir un árbol de tango, simulamos un árbol de búsqueda binario completo llamado árbol de referencia , que es simplemente un árbol de búsqueda binario tradicional que contiene todos los elementos. Este árbol nunca aparece en la implementación real, pero es la base conceptual detrás de las siguientes piezas de un árbol de tango.
En particular, la altura del árbol de referencia es ⌈log 2 ( n +1) ⌉. Esto equivale a la longitud del camino más largo y, por lo tanto, al tamaño del árbol auxiliar más grande. Manteniendo los árboles auxiliares razonablemente equilibrados , la altura de los árboles auxiliares puede limitarse a O (log log n ). Esta es la fuente de las garantías de rendimiento del algoritmo.
Caminos preferidos
Primero, definimos para cada nodo su hijo preferido , que informalmente es el hijo visitado más recientemente por una búsqueda de árbol de búsqueda binaria tradicional. Más formalmente, considere un subárbol T , enraizado en p , con hijos l (izquierda) y r (derecha). Establecemos r como el hijo preferido de p si el nodo al que se ha accedido más recientemente en T está en el subárbol enraizado en r , y l como el hijo preferido en caso contrario. Tenga en cuenta que si el nodo de T al que se ha accedido más recientemente es el mismo p , entonces l es el hijo preferido por definición.
Una ruta preferida se define comenzando en la raíz y siguiendo a los hijos preferidos hasta llegar a un nodo hoja. Extracción de los nodos en este camino particiones el resto del árbol en un número de subárboles, y recursivamente en cada subárbol (formando un camino preferido de su raíz, que divide el subárbol en más subárboles).
Árboles auxiliares
Para representar una ruta preferida, almacenamos sus nodos en un árbol de búsqueda binario balanceado , específicamente un árbol rojo-negro . Para cada nodo n no hoja en una ruta preferida P , tiene un hijo c no preferido , que es la raíz de un nuevo árbol auxiliar. Adjuntamos la raíz de este otro árbol auxiliar ( c ) an en P , uniendo así los árboles auxiliares. También aumentamos el árbol auxiliar almacenando en cada nodo la profundidad mínima y máxima (es decir, la profundidad en el árbol de referencia) de los nodos en el subárbol debajo de ese nodo.
Algoritmo
buscando
Para buscar un elemento en el árbol de tango, simplemente simulamos la búsqueda del árbol de referencia. Comenzamos buscando la ruta preferida conectada a la raíz, que se simula buscando en el árbol auxiliar correspondiente a esa ruta preferida. Si el árbol auxiliar no contiene el elemento deseado, la búsqueda termina en el padre de la raíz del subárbol que contiene el elemento deseado (el comienzo de otra ruta preferida), por lo que simplemente procedemos buscando en el árbol auxiliar esa ruta preferida. , Etcétera.
Actualizando
Para mantener la estructura del árbol de tango (los árboles auxiliares corresponden a los caminos preferidos), debemos realizar algunos trabajos de actualización siempre que los niños preferidos cambien como resultado de las búsquedas. Cuando un niño preferido cambia, la parte superior de una ruta preferida se separa de la parte inferior (que se convierte en su propia ruta preferida) y se vuelve a unir a otra ruta preferida (que se convierte en la nueva parte inferior). Para hacer esto de manera eficiente, definiremos las operaciones de corte y unión en nuestros árboles auxiliares.
Entrar
Nuestra operación de unión combinará dos árboles auxiliares siempre que tengan la propiedad de que el nodo superior de uno (en el árbol de referencia) es hijo del nodo inferior del otro (esencialmente, que las rutas preferidas correspondientes se pueden concatenar). Esto funcionará en base a la operación de concatenar de árboles rojo-negro, que combina dos árboles siempre que tengan la propiedad de que todos los elementos de uno son menores que todos los elementos del otro, y se dividen , lo que hace lo contrario. En el árbol de referencia, observe que existen dos nodos en la ruta superior, de modo que un nodo está en la ruta inferior si y solo si su valor-clave está entre ellos. Ahora, para unir la ruta inferior a la ruta superior, simplemente dividimos la ruta superior entre esos dos nodos, luego concatenamos los dos árboles auxiliares resultantes a cada lado del árbol auxiliar de la ruta inferior, y tenemos nuestro árbol auxiliar final unido.
Cortar
Nuestra operación de corte dividirá una ruta preferida en dos partes en un nodo determinado, una parte superior y una parte inferior. Más formalmente, dividirá un árbol auxiliar en dos árboles auxiliares, de modo que uno contenga todos los nodos en o por encima de una cierta profundidad en el árbol de referencia, y el otro contenga todos los nodos por debajo de esa profundidad. Al igual que en la unión , tenga en cuenta que la parte superior tiene dos nodos que rodean la parte inferior. Por lo tanto, podemos simplemente dividir en cada uno de estos dos nodos para dividir la ruta en tres partes, luego concatenar las dos externas para terminar con dos partes, la superior y la inferior, como deseemos.
Análisis
Para limitar la relación competitiva de los árboles de tango, debemos encontrar un límite inferior en el rendimiento del árbol fuera de línea óptimo que utilizamos como punto de referencia. Una vez que encontramos un límite superior en el rendimiento del árbol del tango, podemos dividirlos para limitar la proporción competitiva.
Entrelazado enlazado
Para encontrar un límite inferior en el trabajo realizado por el árbol de búsqueda binario fuera de línea óptimo, usamos nuevamente la noción de hijos preferidos. Al considerar una secuencia de acceso (una secuencia de búsquedas), hacemos un seguimiento de cuántas veces cambia el hijo preferido de un nodo del árbol de referencia. El número total de conmutadores (sumado en todos los nodos) da un límite inferior asintótico en el trabajo realizado por cualquier algoritmo de árbol de búsqueda binaria en la secuencia de acceso dada. Esto se llama límite inferior entrelazado . [1]
Árbol de tango
Para conectar esto con los árboles de tango, encontraremos un límite superior en el trabajo realizado por el árbol de tango para una secuencia de acceso determinada. Nuestro límite superior será, donde k es el número de intercalados.
El costo total se divide en dos partes, buscar el elemento y actualizar la estructura del árbol de tango para mantener las invariantes adecuadas (cambiar los niños preferidos y reorganizar los caminos preferidos).
buscando
Para ver que la búsqueda (no la actualización) encaja en este límite, simplemente tenga en cuenta que cada vez que una búsqueda de árbol auxiliar no tiene éxito y tenemos que pasar al siguiente árbol auxiliar, eso da como resultado un cambio secundario preferido (ya que la ruta preferida de los padres ahora cambia de dirección para unirse a la ruta preferida del niño). Dado que todas las búsquedas del árbol auxiliar no tienen éxito excepto la última (nos detenemos una vez que la búsqueda es exitosa, naturalmente), buscamosarboles auxiliares. Cada búsqueda toma, porque el tamaño de un árbol auxiliar está limitado por , la altura del árbol de referencia.
Actualizando
El costo de actualización también se ajusta a este límite, porque solo tenemos que realizar un corte y una unión por cada árbol auxiliar visitado. Una sola operación de corte o unión toma solo un número constante de búsquedas, divisiones y concatenaciones , cada una de las cuales toma un tiempo logarítmico en el tamaño del árbol auxiliar, por lo que nuestro costo de actualización es.
Relación competitiva
Los árboles de tango son -competitivo, porque el trabajo realizado por el árbol de búsqueda binario fuera de línea óptimo es al menos lineal en k (el número total de cambios secundarios preferidos), y el trabajo realizado por el árbol de tango es como máximo.
Ver también
Referencias
- ^ a b Demaine, ED; Harmon, D .; Iacono, J .; Pătraşcu, M. (2007). "Optimidad dinámica: casi" (PDF) . Revista SIAM de Computación . 37 (1): 240. doi : 10.1137 / S0097539705447347 .