Un árbol de tango es un tipo de árbol binario de búsqueda 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.
Se trata de un árbol binario de búsqueda en línea que logra una relación competitiva con respecto al árbol binario de búsqueda óptimo fuera de línea , mientras que solo utiliza bits adicionales de memoria por nodo. Esto mejoró la relación competitiva conocida anteriormente, que era de .
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).
Para construir un árbol de tango, simulamos un árbol binario de búsqueda completo llamado árbol de referencia , que es simplemente un árbol binario de búsqueda 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 partes de un árbol de tango.
En particular, la altura del árbol de referencia es ⌈log 2 ( n +1)⌉. Esto es igual 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 , la altura de los árboles auxiliares se puede limitar a O (log log n ). Esta es la fuente de las garantías de rendimiento del algoritmo.
Primero, definimos para cada nodo su hijo preferido , que informalmente es el hijo visitado más recientemente por una búsqueda tradicional en un árbol binario. Más formalmente, considere un subárbol T , con raíz en p , con hijos l (izquierda) y r (derecha). Establecemos r como el hijo preferido de p si el nodo accedido más recientemente en T está en el subárbol con raíz en r , y l como el hijo preferido en caso contrario. Tenga en cuenta que si el nodo accedido más recientemente de T es p en sí, entonces l es el hijo preferido por definición.
Una ruta preferida se define comenzando en la raíz y siguiendo los hijos preferidos hasta llegar a un nodo de hoja. Al eliminar los nodos de esta ruta, se divide el resto del árbol en varios subárboles y se recurre a cada subárbol (formando una ruta preferida desde su raíz, que divide el subárbol en más subárboles).
Para representar una ruta preferida, almacenamos sus nodos en un árbol binario de búsqueda balanceado , específicamente un árbol rojo-negro . Para 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. Adjuntamos la raíz ( c ) de este otro árbol auxiliar a n en P , vinculando así los árboles auxiliares entre sí. 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.
Para buscar un elemento en el árbol de tango, simplemente simulamos una búsqueda en el árbol de referencia. Comenzamos buscando en 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 a buscar en el árbol auxiliar esa ruta preferida, y así sucesivamente.
Para mantener la estructura del árbol de tango (los árboles auxiliares corresponden a las rutas preferidas), debemos realizar un trabajo de actualización cada vez que los hijos preferidos cambian como resultado de las búsquedas. Cuando un 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 hacer esto de manera eficiente, definiremos operaciones de corte y unión en nuestros árboles auxiliares.
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 un hijo del nodo inferior del otro (esencialmente, que las rutas preferidas correspondientes se puedan concatenar). Esto funcionará en base a la operación de concatenación de árboles rojo-negros, 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 split , 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 clave-valor está entre ellos. Ahora, para unir la ruta inferior con 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.
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. Como en join , observe que la parte superior tiene dos nodos que enmarcan 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 los dos externos para terminar con dos partes, la superior y la inferior, como se desee.
Para delimitar la relación competitiva de los árboles de tango, debemos encontrar un límite inferior para el rendimiento del árbol offline óptimo que utilizamos como referencia. Una vez que encontramos un límite superior para el rendimiento del árbol de tango, podemos dividirlos para delimitar la relación competitiva.
Para encontrar un límite inferior para el trabajo realizado por el árbol binario de búsqueda fuera de línea óptimo, utilizamos nuevamente la noción de hijos preferidos. Al considerar una secuencia de acceso (una secuencia de búsquedas), llevamos un registro de cuántas veces cambia el hijo preferido de un nodo del árbol de referencia. El número total de cambios (sumados para todos los nodos) da un límite inferior asintótico para el trabajo realizado por cualquier algoritmo de árbol binario de búsqueda en la secuencia de acceso dada. Esto se denomina límite inferior de intercalación . [1]
Para conectar esto con los árboles de tango, encontraremos un límite superior para el trabajo realizado por el árbol de tango para una secuencia de acceso dada. Nuestro límite superior será , donde k es el número de intercalaciones.
El costo total se divide en dos partes: búsqueda del elemento y actualización de la estructura del árbol de tango para mantener las invariantes adecuadas (cambiando los hijos preferidos y reorganizando las rutas preferidas).
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 de árbol auxiliar no es exitosa y tenemos que pasar al siguiente árbol auxiliar, eso da como resultado 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 de árboles auxiliares no son exitosas excepto la última (nos detenemos una vez que una búsqueda es exitosa, naturalmente), buscamos árboles auxiliares. Cada búsqueda toma , porque el tamaño de un árbol auxiliar está limitado por , la altura del árbol de referencia.
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 requiere solo una cantidad 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 .
Los árboles de tango son -competitivos, 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 de tango es como máximo .
