á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] Lleva el nombre de Buenos Aires , de la cual el tango es emblemático.
Es un árbol de búsqueda binario en línea que logra una relación competitiva en relación con el árbol de búsqueda binario óptimo fuera de línea , mientras que solo utiliza bits de memoria adicionales por nodo. Esto mejoró la relación competitiva más conocida anterior, que era .
Los árboles de tango funcionan mediante la partición de un árbol de búsqueda binaria en un conjunto de rutas preferidas , que 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 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 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. Manteniendo los árboles auxiliares razonablemente equilibrados , la altura de los árboles auxiliares se puede acotar a O (log log n ). Esta es la fuente de las garantías de rendimiento del algoritmo.
Primero, definimos para cada nodo su elemento secundario preferido , que de manera informal es el elemento secundario visitado más recientemente por una búsqueda de árbol de búsqueda binaria tradicional. 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 al que se accedió 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 de T al que se accedió más recientemente es p , entonces l es el hijo preferido por definición.
