Árbol exponencial

Un árbol exponencial es un tipo de árbol de búsqueda donde el número de hijos de sus nodos disminuye exponencialmente al aumentar la profundidad. Los valores se almacenan únicamente en los nodos hoja. Cada nodo contiene un divisor, un valor menor o igual a todos los valores del subárbol que se utiliza durante la búsqueda. Los árboles exponenciales utilizan otra estructura de datos en los nodos internos que contienen los divisores de los hijos, lo que permite una búsqueda rápida.

Los árboles exponenciales alcanzan una complejidad asintótica óptima en algunas operaciones. Su importancia es principalmente teórica.

Un árbol exponencial es un árbol con raíz donde cada nodo contiene un divisor y cada nodo hoja contiene un valor. El valor puede ser diferente del divisor. Un árbol exponencial con${\displaystyle n}$Los valores se definen recursivamente:

• La raíz tiene${\displaystyle \Theta (n^{1/k})}$niños
• El divisor de la raíz es el mismo que el divisor del hijo más a la izquierda.
• Los divisores de todos los hijos se almacenan en una estructura de datos local.
• Los subárboles son árboles exponenciales con${\displaystyle \Theta (n^{1-1/k})}$valores

Una condición adicional es que la búsqueda de un valor utilizando los divisores debe producir el nodo correcto (es decir, el que contiene el valor). Por lo tanto, si una raíz de un subárbol contiene el divisor${\displaystyle s}$y su hermano derecho contiene el divisor${\displaystyle s'}$, entonces este subárbol solo puede contener claves en el rango${\displaystyle [s,s')}$.

El árbol utiliza una estructura de datos estática en cada nodo interno para permitir una búsqueda rápida de valores. Debe ser posible construir esta estructura con${\displaystyle d}$valores en el tiempo${\displaystyle O(d^{k-1})}$El tiempo de búsqueda en esta estructura se denota${\displaystyle S(d)}$.

Un árbol Fusion puede utilizarse como esta estructura de datos.

• Andersson, Arne (octubre de 1996). «Clasificación y búsqueda deterministas más rápidas en espacio lineal». Actas de la 37.ª Conferencia sobre Fundamentos de la Informática . págs. 135-141 . doi : 10.1109/SFCS.1996.548472 . ISBN  0-8186-7594-2. S2CID 13603426 . 
• Andersson, Arne; Thorup, Mikkel (2007-06-01). "Conjuntos ordenados dinámicos con árboles de búsqueda exponenciales" . Journal of the ACM . 54 (3): 13–es. arXiv : cs/0210006 . doi : 10.1145/1236457.1236460 . ISSN 0004-5411 . S2CID 8175703 .