Metodos de busqueda

Contenido
Introducción. Clasificación de la Búsqueda. Métodos de Búsqueda Interna. Búsqueda Secuencial. Análisis. Búsqueda Secuencial usando Bloques. Determinación del Bloque. Análisis. Búsqueda Secuencial usando Índices. Búsqueda Binaria. Análisis. Árbol Binario de Búsqueda. Búsqueda, Inserción y Eliminación. Análisis. Métodos de Búsqueda Externa.

Algorítmica III
Capítulo 6 Capí

Métodosde Búsqueda

Introducción Introducció
La búsqueda es una operación que nos permite recuperar información previamente almacenada. El resultado de la operación es el éxito en el caso de encontrar el elemento buscado y de fracaso en caso contrario. Ejemplos: Directorios de archivos ordenados. Ofertas laborales ordenados por tipo de trabajo. Libros de la biblioteca ordenados por autor y tema. Sepuede realizar sobre elementos ordenados ó sobre elementos desordenados.

Clasificación de la Búsqueda Clasificació Bú
Se pueden clasificar en: Búsqueda Interna: Cuando los elementos se encuentran en memoria principal. Búsqueda externa: Cuando todos los elementos se encuentran en memoria secundaria

Métodos de Búsqueda Interna Bú
Estos pueden ser almacenados en estructuras estáticas comoarreglos y estructuras dinámicas como listas enlazadas y árboles. Búsqueda Secuencial ó lineal Búsqueda Secuencial con Bloques Búsqueda con Índices. Búsqueda Binaria. Búsqueda por transformación de clave (hash). Árboles Binarios de Búsqueda.

Búsqueda Secuencial
Consiste en revisar elemento por elemento de la estructura de datos. Hasta encontrar el dato más buscado ó Hasta llegar al final de lalista de datos disponibles. Búsqueda Secuencial en Arreglo Desordenado. Búsqueda Secuencial en Arreglo Ordenado Búsqueda Secuencial en Lista Enlazada Desordenada Búsqueda Secuencial en Lista Enlazada Ordenada

1

Análisis de la Búsqueda Secuencial Aná Bú
Consiste en determinar cual es la operación elemental que más afecta al algoritmo. La comparación: es la operación que determina si un elementose encuentra en su posición respecto de otro. El movimiento: es la operación que permite el traslado de un elemento de una posición a otra. Determina la operación elemental, se tiene que definir los límites de dicha operación. Caso peor Caso medio Caso mejor

Análisis de la Búsqueda Secuencial Aná Bú en Arreglo Desordenado
La operación elemental seleccionada es la comparación. Caso Mejor: Elelemento buscado está en la primera posición. Caso Mejor = 1 Caso Peor: El elemento buscado no se encuentra en el arreglo. Caso Peor = n Caso Medio: El elemento buscado se encuentra en la posición i en el arreglo. Caso Medio = (1 + n) / 2

Análisis de la Búsqueda Secuencial en Aná Bú Arreglo Desordenado (Caso Medio)
Misma probabilidad de la distribución de los datos. Misma probabilidad deencontrar al elemento buscado en cualquier posición del arreglo. El número de comparaciones puede ser 1, 2, 3, ..., n y en cada paso debe darse una probabilidad de 1/n

Análisis de la Búsqueda Secuencial Aná Bú en Listas Enlazadas
La operación elemental seleccionada es la comparación. No existe una forma a para etiquetar los nodos de la lista. La forma más eficiente de representar una lista paraefectuar una búsqueda es en un matriz de dos columnas. El análisis debe ser exactamente igual a los anteriores ya efectuados.

CasoMedio CasoMedio CasoMedio

=1∗

n

1

+2∗

n

1

+3∗

n

1

+ ... + n ∗

= (1 + 2 + 3 + ... + n ) ∗

n +1 ⎛ n ∗ (n + 1 ) ⎞ 1 = ⎜ = ⎟∗ 2 2 ⎝ ⎠ n

n

1

n

1

Búsqueda Secuencial usando Bloques
El vector debe estar ordenado para estemétodo. Trabajar con bloque de elementos en vez de elementos aislados. Su tamaño depende del número de elementos del vector. Se realiza comparando la clave con el último elemento de cada bloque. Si la clave resulta menor, se busca secuencialmente en los elementos salteados del bloque

Determinación del Bloques Determinació
El vector debe estar ordenado para este método. El tamaño del bloque debe...