En informática , una estructura de datos de búsqueda [ cita requerida ] es cualquier estructura de datos que permite la recuperación eficiente de elementos específicos de un conjunto de elementos, como un registro específico de una base de datos .
La estructura de búsqueda más simple, más general y menos eficiente es simplemente una lista secuencial desordenada de todos los elementos. Localizar el elemento deseado en dicha lista, mediante el método de búsqueda lineal , requiere inevitablemente una cantidad de operaciones proporcional al número n de elementos, tanto en el peor de los casos como en el caso promedio . Las estructuras de datos de búsqueda útiles permiten una recuperación más rápida; sin embargo, están limitadas a consultas de algún tipo específico. Además, dado que el costo de construir tales estructuras es al menos proporcional a n , solo son rentables si se deben realizar varias consultas en la misma base de datos (o en una base de datos que cambia poco entre consultas).
Las estructuras de búsqueda estáticas están diseñadas para responder a muchas consultas en una base de datos fija; las estructuras dinámicas también permiten la inserción, eliminación o modificación de elementos entre consultas sucesivas. En el caso dinámico, también se debe considerar el costo de corregir la estructura de búsqueda para tener en cuenta los cambios en la base de datos.
El tipo de consulta más simple es localizar un registro que tenga un campo específico (la clave ) igual a un valor especificado v . Otros tipos de consulta comunes son "encontrar el elemento con el valor de clave más pequeño (o más grande)", "encontrar el elemento con el valor de clave más grande que no exceda v ", "encontrar todos los elementos con valores de clave entre límites especificados v min y v max ".
En ciertas bases de datos, los valores de las claves pueden ser puntos en un espacio multidimensional . Por ejemplo, la clave puede ser una posición geográfica ( latitud y longitud ) en la Tierra . En ese caso, los tipos de consultas más comunes son "encontrar el registro con una clave más cercana a un punto v determinado ", "encontrar todos los elementos cuya clave se encuentre a una distancia determinada de v ", o "encontrar todos los elementos dentro de una región R especificada del espacio".
Un caso especial común de esto último son las consultas de rango simultáneas en dos o más claves simples, como "encontrar todos los registros de empleados con salarios entre 50.000 y 100.000 y contratados entre 1995 y 2007".
En esta tabla, la notación asintótica O ( f ( n )) significa "no exceder algún múltiplo fijo de f ( n ) en el peor caso".
Nota : La inserción en una matriz desordenada a veces se cita como O ( n ) debido a la suposición de que el elemento que se va a insertar debe insertarse en una ubicación particular de la matriz, lo que requeriría desplazar todos los elementos posteriores una posición. Sin embargo, en una matriz clásica, la matriz se utiliza para almacenar elementos arbitrarios desordenados y, por lo tanto, la posición exacta de cualquier elemento dado no tiene importancia, y la inserción se lleva a cabo incrementando el tamaño de la matriz en 1 y almacenando el elemento al final de la matriz, que es una operación O (1). [3] [4] Del mismo modo, la operación de eliminación a veces se cita como O ( n ) debido a la suposición de que los elementos posteriores deben desplazarse, pero en una matriz desordenada clásica el orden no es importante (aunque los elementos están ordenados implícitamente por tiempo de inserción), por lo que la eliminación se puede llevar a cabo intercambiando el elemento que se va a eliminar con el último elemento de la matriz y luego disminuyendo el tamaño de la matriz en 1, que es una operación O (1). [5]
Esta tabla es sólo un resumen aproximado; para cada estructura de datos existen situaciones y variantes especiales que pueden dar lugar a costes diferentes. También se pueden combinar dos o más estructuras de datos para obtener costes más bajos.
LIST-DELETE se ejecuta en
O(1) tiempo, pero si se desea eliminar un elemento con una
clave dada, se requiere Θ(n) tiempo en el peor de los casos porque primero debemos llamar a LIST-SEARCH.
Hay dos tipos de montículos binarios: montículos máximos y montículos mínimos. En ambos tipos, los valores en los nodos satisfacen unapropiedad
del montículo
... el elemento más grande en un montículo máximo se almacena en la raíz... El elemento más pequeño en un montículo mínimo está en la raíz... La operación HEAP-MAXIMUM devuelve el elemento máximo del montículo en Θ(1) tiempo simplemente devolviendo el valor
A
[1] en el montículo.
La inserción de un elemento en una matriz desordenada no depende de nada más que de colocar el nuevo elemento al final de la lista. Esto da como resultado la inserción en una matriz desordenada deO
(
1).
Encontrar el elemento con un valor dado es lineal. Como la matriz no está ordenada de todos modos, puedes realizar la eliminación en tiempo constante. Primero, cambia el elemento que quieres eliminar al final de la matriz y luego reduce el tamaño de la matriz en un elemento.