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. La localización del elemento deseado en dicha lista, mediante el método de búsqueda lineal , inevitablemente requiere un número de operaciones proporcional al número n de elementos, tanto en el peor de los casos como en el caso medio . Las estructuras de datos de búsqueda útiles permiten una recuperación más rápida; sin embargo, se limitan a consultas de algún tipo específico. Además, dado que el costo de construir tales estructuras es al menos proporcional an , solo se amortizan si se van a 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.
Clasificación
El tipo de consulta más simple es ubicar un registro que tiene un campo específico (la clave ) igual a un valor especificado v . Otros tipos comunes de consulta son "buscar el elemento con el valor clave más pequeño (o más grande)", "buscar el elemento con el valor clave más grande que no exceda v ", "buscar todos los elementos con valores clave entre los límites especificados v min y v max ".
En determinadas bases de datos, los valores clave pueden ser puntos en algún espacio multidimensional . Por ejemplo, la clave puede ser una posición geográfica ( latitud y longitud ) en la Tierra . En ese caso, los tipos comunes de consultas son encontrar el registro con una clave más cercana a un punto dado v ", o" encontrar todos los elementos cuya clave se encuentra a una distancia dada de v ", o" encontrar todos los elementos dentro de una región específica R de el espacio".
Un caso especial común de este último son las consultas de rango simultáneas en dos o más claves simples, como "buscar todos los registros de empleados con salario entre 50.000 y 100.000 y contratados entre 1995 y 2007".
Llaves ordenadas individuales
- Matriz si los valores clave abarcan un intervalo moderadamente compacto.
- Lista ordenada por prioridad; ver búsqueda lineal
- Matriz ordenada por clave; ver búsqueda binaria
- Árbol de búsqueda binaria autoequilibrado
- Tabla de picadillo
Encontrar el elemento más pequeño
Análisis asintótico amortizado del peor de los casos
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 de los casos".
Estructura de datos | Insertar | Borrar | Equilibrio | Llegar al índice | Buscar | Encontrar mínimo | Encuentra el máximo | Uso del espacio |
---|---|---|---|---|---|---|---|---|
Matriz sin clasificar | O (1) (ver nota) | O (1) (ver nota) | N / A | O (1) | O ( n ) | O ( n ) | O ( n ) | O ( n ) |
Matriz ordenada | O ( n ) | O ( n ) | N / A | O (1) | O (log n ) | O (1) | O (1) | O ( n ) |
Apilar | O (1) | O (1) | O ( n ) | O ( n ) | ||||
Cola | O (1) | O (1) | O ( n ) | O ( n ) | ||||
Sin ordenar lista enlazada | O (1) | O (1) [1] | N / A | O ( n ) | O ( n ) | O ( n ) | O ( n ) | O ( n ) |
Lista enlazada ordenada | O ( n ) | O (1) [1] | N / A | O ( n ) | O ( n ) | O (1) | O (1) | O ( n ) |
Lista de omisión | ||||||||
Árbol de búsqueda binaria autoequilibrado | O (log n ) | O (log n ) | O (log n ) | N / A | O (log n ) | O (log n ) | O (log n ) | O ( n ) |
Montón | O (log n ) | O (log n ) | O (log n ) | N / A | O ( n ) | O (1) para un montón mínimo O ( n ) para un montón máximo [2] | O (1) para un montón máximo O ( n ) para un montón mínimo [2] | O ( n ) |
Tabla de picadillo | O (1) | O (1) | O ( n ) | N / A | O (1) | O ( n ) | O ( n ) | O ( n ) |
Trie ( k = longitud promedio de la clave) | O ( k ) | O ( k ) | N / A | O ( k ) | O ( k ) | O ( k ) | O ( k ) | O ( k n ) |
Árbol cartesiano | ||||||||
Árbol B | O (log n ) | O (log n ) | O (log n ) | N / A | O (log n ) | O (log n ) | O (log n ) | O ( n ) |
Árbol rojo-negro | ||||||||
Árbol de extensión | ||||||||
Árbol AVL | O (log n ) | |||||||
árbol kd |
Nota : Insertar en una matriz no ordenada a veces se cita como O ( n ) debido a la suposición de que el elemento que se insertará debe insertarse en una ubicación particular de la matriz, lo que requeriría cambiar todos los elementos subsiguientes en una posición. Sin embargo, en una matriz clásica, la matriz se usa para almacenar elementos arbitrarios no ordenados y, por lo tanto, la posición exacta de cualquier elemento dado no tiene importancia, y la inserción se lleva a cabo aumentando 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 subsiguientes deben desplazarse, pero en una matriz clásica sin clasificar el orden no es importante (aunque los elementos están implícitamente ordenados por insert- time), por lo que la eliminación se puede llevar a cabo intercambiando el elemento que se 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 solo un resumen aproximado; para cada estructura de datos existen situaciones especiales y variantes que pueden generar costos diferentes. También se pueden combinar dos o más estructuras de datos para obtener costos más bajos.
Notas al pie
- ↑ a b Cormen, Leiserson, Rivest. Introducción a los algoritmos . La Facultad de Ciencias de la Información y Tecnología de Penn State. ISBN 9780262530910.
LIST-DELETE se ejecuta en tiempo O (1), pero si para eliminar un elemento con una clave dada, se requiere Θ (n) tiempo en el peor de los casos porque primero debemos llamar a LIST-SEARCH.
Mantenimiento de CS1: utiliza el parámetro de autores ( enlace ) - ^ a b Cormen, Leiserson, Rivest. Introducción a los algoritmos . La Facultad de Ciencias de la Información y Tecnología de Penn State. ISBN 9780262530910.
Hay dos tipos de montones binarios: max-montones y min-montones. En ambos tipos, los valores en los nodos satisfacen una propiedad del montón ... el elemento más grande en un montón máximo se almacena en la raíz ... El elemento más pequeño en un montón mínimo está en la raíz ... La operación HEAP -MAXIMUM devuelve el elemento de montón máximo en Θ (1) tiempo simplemente devolviendo el valor A [1] en el montón.
Mantenimiento de CS1: utiliza el parámetro de autores ( enlace ) - ^ Allen Sherrod (2007). Estructuras de datos y algoritmos para desarrolladores de juegos . Aprendizaje Cengage. ISBN 9781584506638.
La inserción de un elemento en una matriz desordenada no depende de nada más que colocar el nuevo elemento al final de la lista. Esto da la inserción en una matriz desordenada de O (1).
- ^ Cormen, Leiserson, Rivest. Introducción a los algoritmos . La Facultad de Ciencias de la Información y Tecnología de Penn State. ISBN 9780262530910.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ "Algoritmo - la complejidad del tiempo de eliminación en una matriz sin clasificar" .
Encontrar el elemento con un valor dado es lineal. Dado que la matriz no está ordenada de todos modos, puede realizar la eliminación en un tiempo constante. Primero cambie el elemento que desea eliminar al final de la matriz, luego reduzca el tamaño de la matriz en un elemento.
Ver también
- Lista de estructuras de datos
- Lista de omisión