Árbol de tango

Un árbol de tango es un tipo de árbol de búsqueda binaria propuesto por Erik D. Demaine , Dion Harmon, John Iacono y Mihai Pătrașcu en 2004. ^{[ 1 ]} Recibe su nombre de Buenos Aires , de la cual el tango es emblemático.

Es un árbol de búsqueda binaria en línea que logra un $O(\log \log n)$ relación competitiva en relación con el árbol de búsqueda binaria óptimo fuera de línea , mientras que solo se utiliza $O(\log \log n)$ bits adicionales de memoria por nodo. Esto mejoró la mejor relación competitiva conocida anteriormente, que era $O(\log n)$ .

Estructura

Los árboles Tango funcionan dividiendo un árbol de búsqueda binaria en un conjunto de rutas preferidas , que a su vez se almacenan en árboles auxiliares (por lo que el árbol Tango se representa como un árbol de árboles).

Árbol de referencia

Para construir un árbol de tango, simulamos un árbol de búsqueda binaria completo llamado árbol de referencia , que es simplemente un árbol de búsqueda binaria tradicional que contiene todos los elementos. Este árbol nunca aparece en la implementación real, pero es la base conceptual de las siguientes partes de un árbol de tango.

En concreto, la altura del árbol de referencia es ⌈ log ₂( 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. Al mantener los árboles auxiliares razonablemente equilibrados , su altura puede limitarse a O (log log n ). Esta es la base de las garantías de rendimiento del algoritmo.

Rutas preferidas

Primero, definimos para cada nodo su hijo preferido , que informalmente es el hijo visitado más recientemente mediante una búsqueda binaria tradicional en árbol. De forma más formal, consideremos un subárbol T , con raíz en p , cuyos hijos son l (izquierdo) y r (derecho). Definimos r como el hijo preferido de p si el nodo de T al que se accedió más recientemente pertenece al subárbol con raíz en r , y l como el hijo preferido en caso contrario. Cabe destacar que si el nodo de T al que se accedió más recientemente es el propio p , entonces l es el hijo preferido por definición.

Se define una ruta preferida comenzando en la raíz y siguiendo los nodos hijos preferidos hasta llegar a un nodo hoja. Al eliminar los nodos de esta ruta, el resto del árbol se divide en varios subárboles, y se aplica recursión a cada subárbol (formando una ruta preferida desde su raíz, que a su vez 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 binaria balanceado , específicamente un árbol rojo-negro . Cada nodo no hoja n en una ruta preferida P tiene un hijo no preferido c , que es la raíz de un nuevo árbol auxiliar. Conectamos la raíz de este otro árbol auxiliar ( c ) con n en P , uniendo así los árboles auxiliares. Además, ampliamos el árbol auxiliar almacenando en cada nodo la profundidad mínima y máxima (profundidad en el árbol de referencia) de los nodos en el subárbol bajo ese nodo.

Algoritmo

Búsqueda

Para buscar un elemento en el árbol de tango, simplemente simulamos la búsqueda en el árbol de referencia. Comenzamos buscando en la ruta preferida conectada a la raíz, lo cual se simula buscando en el árbol auxiliar correspondiente a dicha ruta. Si el árbol auxiliar no contiene el elemento deseado, la búsqueda finaliza en el padre de la raíz del subárbol que contiene el elemento deseado (el inicio de otra ruta preferida), por lo que simplemente continuamos buscando esa ruta preferida en el árbol auxiliar, y así sucesivamente.

Actualizando

Para mantener la estructura del árbol de tango (los árboles auxiliares corresponden a las rutas preferidas), debemos actualizarlo cada vez que los nodos hijos preferidos cambien como resultado de las búsquedas. Cuando un nodo hijo 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 realizar esto de manera eficiente, definiremos operaciones de corte y unión en nuestros árboles auxiliares.

Unirse

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) sea hijo del nodo inferior del otro (esencialmente, que las rutas preferidas correspondientes se puedan concatenar). Esto funcionará basándose en la operación de concatenación de árboles rojo-negro, que combina dos árboles siempre que tengan la propiedad de que todos los elementos de uno sean menores que todos los elementos del otro, y en la operación de división , que hace lo contrario. En el árbol de referencia, observe que existen dos nodos en la ruta superior tales que un nodo está en la ruta inferior si y solo si su par clave-valor 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 obtenemos nuestro árbol auxiliar final unido.

Cortar

Nuestra operación de corte dividirá una ruta preferida en dos partes en un nodo dado: una parte superior y una parte inferior. De forma más formal, dividirá un árbol auxiliar en dos árboles auxiliares, de modo que uno contenga todos los nodos a una cierta profundidad o superior en el árbol de referencia, y el otro contenga todos los nodos por debajo de esa profundidad. Como en la operación de unión , observe que la parte superior tiene dos nodos que delimitan la parte inferior. Por lo tanto, podemos simplemente dividir en cada uno de estos dos nodos para dividir la ruta en tres partes, y luego concatenar las dos partes externas para obtener dos partes, la superior y la inferior, como se desea.

Análisis

Para acotar la relación de competitividad de los árboles de tango, debemos encontrar un límite inferior para el rendimiento del árbol óptimo fuera de línea que utilizamos como referencia. Una vez que encontremos un límite superior para el rendimiento del árbol de tango, podemos dividirlos para acotar la relación de competitividad.

Encuadernación intercalada

Para hallar una cota inferior del trabajo realizado por el árbol de búsqueda binaria fuera de línea óptimo, volvemos a utilizar la noción de hijos preferidos. Al considerar una secuencia de acceso (una secuencia de búsquedas), registramos cuántas veces cambia el hijo preferido de un nodo del árbol de referencia. El número total de cambios (sumado en todos los nodos) proporciona una cota inferior asintótica del trabajo realizado por cualquier algoritmo de árbol de búsqueda binaria en la secuencia de acceso dada. Esto se denomina cota inferior de entrelazado . ^{[ 1 ]}

Árbol de tango

Para relacionar esto con los árboles de tango, encontraremos una cota superior para el trabajo realizado por el árbol de tango para una secuencia de acceso dada. Nuestra cota superior será $(k+1)O(\log \log n)$ , donde k es el número de entrelazados.

El coste total se divide en dos partes: la búsqueda del elemento y la actualización de la estructura del árbol de tango para mantener las invariantes adecuadas (cambio de hijos preferidos y reorganización de rutas preferidas).

Búsqueda

Para ver que la búsqueda (no la actualización) se ajusta a este límite, simplemente observe que cada vez que una búsqueda en el árbol auxiliar no tiene éxito y tenemos que pasar al siguiente árbol auxiliar, eso resulta en un cambio de hijo preferido (ya que la ruta preferida del padre ahora cambia de dirección para unirse a la ruta preferida del hijo). Dado que todas las búsquedas en el árbol auxiliar no tienen éxito excepto la última (nos detenemos una vez que una búsqueda tiene éxito, naturalmente), buscamos $k+1$ árboles auxiliares. Cada búsqueda lleva $O(\log \log n)$ , porque el tamaño de un árbol auxiliar está limitado por $\log n$ , la altura del árbol de referencia.

Actualizando

El costo de actualización también se ajusta a este límite, ya que solo tenemos que realizar un corte y una unión por cada árbol auxiliar visitado. Una sola operación de corte o unión requiere solo un número constante de búsquedas, divisiones y concatenaciones , cada una de las cuales requiere un tiempo logarítmico en el tamaño del árbol auxiliar, por lo que nuestro costo de actualización es $(k+1)O(\log \log n)$ .

Índice de competitividad

Los árboles de tango son $O(\log \log n)$ -competitivo, porque el trabajo realizado por el árbol de búsqueda binaria fuera de línea óptimo es al menos lineal en k (el número total de cambios de hijos preferidos), y el trabajo realizado por el árbol tango es como máximo $(k+1)O(\log \log n)$ .

Véase también

Referencias

1 2 Demaine, ED; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Optimalidad dinámica—casi" (PDF) . SIAM Journal on Computing . 37 (1): 240. doi : 10.1137/S0097539705447347 .

[DHIP-1] 1 2 Demaine, ED; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Optimalidad dinámica—casi" (PDF) . SIAM Journal on Computing . 37 (1): 240. doi : 10.1137/S0097539705447347 .

[ 1 ]