En informática, los árboles de búsqueda digital son un tipo de árbol de búsqueda binario que mantiene punteros a nodos interiores, llamados dedos . Los dedos aceleran las búsquedas, inserciones y eliminaciones de elementos cercanos a los dedos, dando búsquedas O (log n) amortizadas e inserciones y eliminaciones O (1) amortizadas. No debe confundirse con un árbol de dedos ni con un árbol de dispersión , aunque ambos pueden usarse para implementar árboles de búsqueda de dedos.
Guibas et al. [1] introdujo árboles de búsqueda dactilar, basándose en árboles B. La versión original admite búsquedas dactilares en tiempo O (log d), donde d es el número de elementos entre el dedo y el objetivo de búsqueda. Las actualizaciones toman O(1) tiempo, cuando solo se mantienen O(1) dedos móviles. Mover un dedo p posiciones requiere tiempo O(log p). Huddleston y Mehlhorn refinaron esta idea como árboles B vinculados por niveles. [2]
Tsakalidis propuso una versión basada en árboles AVL que facilita la búsqueda desde los extremos del árbol; se puede utilizar para implementar una estructura de datos con varios dedos mediante el uso de varios de dichos árboles. [3]
Para realizar una búsqueda con el dedo en un árbol binario, la forma ideal es comenzar desde el dedo y buscar hacia arriba hasta la raíz, hasta llegar al ancestro menos común , [4] [5] también llamado nodo giratorio , [3] de x e y, y luego bajamos hasta encontrar el elemento que estamos buscando. Determinar si un nodo es el antepasado de otro no es trivial.
Treaps , una estructura de árbol aleatoria propuesta por Seidel y Aragón, [5] tiene la propiedad de que la longitud del camino esperado de dos elementos de distancia d es O(log d ). Para la búsqueda digital, propusieron agregar punteros para determinar rápidamente el ancestro menos común (LCA), o mantener en cada nodo los valores mínimo y máximo de su subárbol.
Se ha escrito un capítulo de libro que cubre en profundidad los árboles de búsqueda dactilar. [4] En el cual, Brodal sugirió un algoritmo para realizar búsquedas dactilares en trampas en tiempo O(log d), sin necesidad de ninguna información contable adicional; este algoritmo logra esto buscando simultáneamente hacia abajo desde el último LCA candidato.