En informática, los árboles de búsqueda de dedos son un tipo de árbol binario de búsqueda que mantiene punteros a nodos interiores, llamados dedos . Los dedos aceleran las búsquedas, inserciones y eliminaciones de elementos cercanos a los dedos, lo que da como resultado búsquedas amortizadas de O (log n) e inserciones y eliminaciones amortizadas de O(1). No debe confundirse con un árbol de dedos ni con un árbol de splay , aunque ambos pueden usarse para implementar árboles de búsqueda de dedos.
Guibas et al. [1] introdujeron los árboles de búsqueda de dedos, basándose en los árboles B. La versión original admite búsquedas de dedos 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 tiempo O(1), cuando solo se mantienen O(1) dedos movibles. Mover un dedo p posiciones requiere tiempo O(log p). Huddleston y Mehlhorn refinaron esta idea como árboles B vinculados a 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 múltiples dedos utilizando múltiples de dichos árboles. [3]
Para realizar una búsqueda de dedo en un árbol binario, lo ideal es empezar desde el dedo y buscar hacia arriba hasta la raíz, hasta llegar al ancestro menos común , [4] [5] también llamado nodo de giro , [3] de x e y, y luego ir hacia abajo para encontrar el elemento que estamos buscando. Determinar si un nodo es el ancestro de otro no es trivial.
Treaps , una estructura de árbol aleatorizada propuesta por Seidel y Aragon, [5] tiene la propiedad de que la longitud de ruta esperada de dos elementos de distancia d es O(log d ). Para la búsqueda por dedos, propusieron agregar punteros para determinar rápidamente el ancestro común mínimo (LCA), o en cada nodo mantener los valores mínimo y máximo de su subárbol.
Se ha escrito un capítulo de libro que cubre los árboles de búsqueda de dedos en profundidad. [4] En el cual, Brodal sugirió un algoritmo para realizar la búsqueda de dedos en árboles 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.