En informática , una búsqueda con el dedo en una estructura de datos es una extensión de cualquier operación de búsqueda que admita esa estructura, en la que se proporciona una referencia (dedo) a un elemento de la estructura de datos junto con la consulta. Si bien el tiempo de búsqueda de un elemento se expresa con mayor frecuencia como una función del número de elementos de una estructura de datos, los tiempos de búsqueda con el dedo son una función de la distancia entre el elemento y el dedo.
En un conjunto de n elementos, la distancia d ( x , y ) (o simplemente d cuando no hay ambigüedad) entre dos elementos x e y es su diferencia de rango. Si x e y son los elementos i th y j th más grandes en la estructura, entonces la diferencia de rango es | i - j |. Si una búsqueda normal en alguna estructura normalmente tomaría O(f( n )) tiempo, entonces una búsqueda de dedo para x con el dedo y idealmente debería tomar O(f( d )) tiempo. Observe que como d ≤ n , se deduce que en el peor de los casos, la búsqueda de dedo solo es tan mala como la búsqueda normal. Sin embargo, en la práctica estas búsquedas degeneradas de dedo hacen más trabajo que las búsquedas normales. Por ejemplo, si f( n ) es log( n ), y la búsqueda de dedo hace el doble de comparaciones que la búsqueda normal en el peor de los casos, se deduce que la búsqueda de dedo es más lenta cuando d > √ n . Por lo tanto, la búsqueda de dedo solo se debe utilizar cuando uno puede esperar razonablemente que el objetivo esté realmente cerca del dedo.
Algunas estructuras de datos populares admiten la búsqueda por dedo sin realizar cambios adicionales en la estructura real. En las estructuras en las que la búsqueda de un elemento x se logra mediante la reducción de un intervalo en el que se puede encontrar x , la búsqueda por dedo desde y generalmente se logra invirtiendo el proceso de búsqueda desde y hasta que el intervalo de búsqueda sea lo suficientemente grande como para contener x , momento en el que la búsqueda continúa de manera normal.
En una lista enlazada , normalmente se busca un elemento de forma lineal, recorriendo el recorrido de un extremo al otro. Si la lista enlazada está ordenada y tenemos una referencia a algún nodo que contenga y , entonces podemos encontrar x en tiempo O( d ) iniciando nuestra búsqueda desde y .
En una matriz ordenada A , normalmente se busca un elemento x en A con una búsqueda binaria . La búsqueda por dedos se logra realizando una búsqueda unilateral desde A [ j ] = y . Mientras que la búsqueda binaria reduce a la mitad el espacio de búsqueda después de cada comparación, la búsqueda unilateral duplica el espacio de búsqueda después de cada comparación. Específicamente, en la k ésima iteración de la búsqueda unilateral (asumiendo que x > y ), el intervalo en consideración es A [ j , j +2 k -1 ]. La expansión se detiene tan pronto como A [ j + 2 k -1 ] ≥ x , momento en el cual se realiza una búsqueda binaria de x en este intervalo .
Si la búsqueda unilateral requiere k iteraciones para encontrar un intervalo que contenga x , entonces se deduce que d > 2 k -2 . La búsqueda binaria en este rango también requerirá otras k iteraciones. Por lo tanto, la búsqueda de x a partir de y requiere un tiempo O( k ) = O(log d ).
En una lista de saltos , se puede buscar x con el dedo desde un nodo que contiene el elemento y simplemente continuando la búsqueda desde este punto. Nótese que si x < y , entonces la búsqueda procede hacia atrás, y si x > y , entonces la búsqueda procede hacia adelante. El caso hacia atrás es simétrico a la búsqueda normal en una lista de saltos, pero el caso hacia adelante es en realidad más complejo. Normalmente, se espera que la búsqueda en una lista de saltos sea rápida porque el centinela al comienzo de la lista es tan alto como el nodo más alto. Sin embargo, nuestro dedo podría ser un nodo de altura 1. Debido a esto, ocasionalmente podemos trepar mientras intentamos buscar; algo que nunca ocurre normalmente. Sin embargo, incluso con esta complicación, podemos lograr un tiempo de búsqueda esperado de O(log d ). [1]
Un treap es un árbol binario de búsqueda (BST) aleatorio. La búsqueda en un treap es lo mismo que la búsqueda de un elemento en cualquier otro BST. Sin embargo, los treap tienen la propiedad de que la longitud de ruta esperada entre dos elementos de distancia d es O(log d ). Por lo tanto, para realizar una búsqueda de dedo desde el nodo que contiene y para x , se puede escalar el árbol desde y hasta que se encuentre un ancestro de x , momento en el que la búsqueda BST normal procede de la forma habitual. Si bien determinar si un nodo es el ancestro de otro no es trivial, se puede ampliar el árbol para admitir consultas de esta forma para obtener un tiempo de búsqueda de dedo esperado de O(log d ). [1]
Las implementaciones de la cuerda (estructura de datos) normalmente implementan un iterador de posición de cuerda para recorrer la cadena. El iterador puede verse como un dedo que apunta a algún carácter específico de la cadena. Como la mayoría de los árboles balanceados, las cuerdas requieren un tiempo O(log( n )) para recuperar datos en una hoja del árbol cuando solo se les da la raíz del árbol. Leer cada hoja del árbol parecería requerir un tiempo O( n *log( n )). Sin embargo, al almacenar un poco de información adicional, el iterador se puede usar para leer "la siguiente" hoja en solo O(1) tiempo, y cada hoja de un árbol en solo O( n ) tiempo. Las implementaciones de cuerdas normalmente almacenan en caché "información adicional" sobre toda la ruta desde la raíz hasta la posición del nodo actual en el iterador. Otras implementaciones de estructuras de datos de árbol a veces almacenan "información adicional" en el árbol mismo, almacenando un puntero en cada nodo a su padre o su sucesor (además de los punteros normales en cada nodo a sus hijos), y almacenando solo la posición actual del nodo en el iterador. [2] [3]
Si se puede realizar una búsqueda de dedos de manera iterativa en un tiempo O ( f ( d )), donde cada iteración toma O (1) tiempo, entonces al proporcionar c dedos diferentes, se puede realizar una búsqueda de dedos en un tiempo O ( c min{ d ( x , y 1 ), ..., d ( x , y c )}). Esto se logra iniciando la búsqueda de dedos para todos los c dedos e iterándolos hacia adelante un paso cada uno hasta que finalice el primero.
Dada cualquier secuencia A = [ a 1 , ..., a m ] de m accesos, se dice que una estructura tiene la propiedad de dedo estático para un dedo fijo f , si el tiempo para realizar A es . Los árboles splay tienen esta propiedad para cualquier elección de f sin procesamiento adicional en secuencias de accesos suficientemente grandes. [4]
La búsqueda con el dedo se puede utilizar para reutilizar el trabajo ya realizado en búsquedas anteriores. Por ejemplo, una forma de iterar sobre los elementos de una estructura de datos es simplemente buscarlos con el dedo en orden, donde el dedo de una consulta es la ubicación del resultado de la última. Se puede optimizar la estructura de datos haciendo esto internamente si se sabe que las búsquedas se realizan con frecuencia cerca de la última búsqueda.
Un árbol de búsqueda de dedos es un tipo de estructura de datos que permite especificar los dedos de modo que todas o algunas de las operaciones admitidas sean más rápidas cuando accedan o modifiquen una ubicación cercana a un dedo. A diferencia de las búsquedas de dedos descritas en este artículo, estos dedos no se proporcionan en el momento de la consulta, sino que se especifican por separado para que todas las operaciones futuras utilicen estos dedos. Una ventaja de esto es que el usuario no necesita manipular ni almacenar referencias internas a la estructura, sino que simplemente puede especificar un elemento en la estructura.
