Árbol de búsqueda de dedos
En informática, los árboles de búsqueda de dedos son un tipo de árbol de búsqueda binaria que mantiene punteros a los nodos interiores, llamados dedos . Los dedos aceleran las búsquedas, las inserciones y las eliminaciones de elementos cercanos a los dedos, lo que proporciona 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 distribución , aunque ambos pueden usarse para implementar árboles de búsqueda de dedos.
Guibás et al. [1] introdujo árboles de búsqueda de dedos, basándose en á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 tardan O(1) tiempo, cuando solo se mantienen O(1) dedos móviles. Mover un dedo p posiciones requiere O(log p) tiempo. 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 usar para implementar una estructura de datos con múltiples dedos usando múltiples de tales árboles. [3]
Para realizar una búsqueda de 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 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 aleatoria propuesta por Seidel y Aragon, [5] tiene la propiedad de que la longitud de camino esperada de dos elementos de distancia d es O(log d ). Para la búsqueda de dedos, propusieron agregar punteros para determinar el ancestro menos común (LCA) rápidamente, o en cada nodo mantener los valores mínimos y máximos 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 búsquedas dactilares en treaps en tiempo O(log d), sin necesidad de información contable adicional; este algoritmo logra esto buscando simultáneamente hacia abajo desde el último LCA candidato.
