Arbol Binario de Busqueda

La búsqueda binaria utiliza un método de `divide y vencerás'para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.

En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este porceso, utilizando el elemento central de esa sublista.

Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son:

*

La lista debe estar ordenada en un orden específico de acuerdo al valor de la llave.
*

Debe conocerse el número de registros.

Algoritmo:
#

Se compara la llave buscada con la llave localizada al centro del arreglo.
#

Si la llave analizada corresponde a la buscada fin de búsqueda si no.
#

Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
#

El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero , lo cual implica que el valor de la llave buscada no esta en la lista.

El esfuerzo máximo para este algoritmo es de log2n. El mínimo de 1 y en promedio ½ log2 n.


Ventajas de la técnica.


La búsqueda binaria es un método eficiente siempre que el vector esté ordenado. En la práctica, esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria exige una ordenación previa del archivo.

La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista. Este método, sin embargo, exige que los datos estén ordenados.

Es mas rapido por su recursividad, su mayor ventaja es con los archivos extensos.

El codigo del procedimiento de esta busqueda es corto en comparacion con las demas tecnicas de busqueda.

En esencia, con una sola comparacion eliminamos la mitad de la tabla; este es el metodo mas eficiente de buscar en una lista ordenada sin emplear tablas o indices adicionales.


Desventajas de la técnica.


La búsqueda binaria tiene, sin embargo, inconvenientes a resaltar:

El archivo debe estar ordenado y el almacenamietno de un archivo ordenado suele plantear problemas en las inserciones y eliminaciones de elementos.

No revisa todos los elementos del archivo, requiere que todos los elementos esten ordenados

Esta busqueda mas de uno o dos accesos si el archivo es enorme;y mantener ese archivo ordenado es muy costoso.



Principales Aplicaciones.


Ejemplo: Árbol Binario de Búsqueda:

Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz del árbol.

Solución:

Cuando el elemento no se encuentra en la raíz, dividimos el árbol en 2 subarboles (izquierda y derecha) y aplicamos ABB, sobre aquel que nos interese (al estar ordenado solo debemos ir por una de las ramas).

La combinación de resultados es trivial: la solución del subproblema es también la del problema global.

Supongamos la lista:

1231

1473

1545

1834

1892

1898 elemento central

1983

2005

2446

2685

3200

Si está buscando el elemento 1983, se examina el número central 1898 en la sexta posición. Ya que 1983 es mayor que 1898, se desprecia la primera sublista y nos centramos en la segunda

1983

2005

2446 elemento central

2685

3200

El número central de esta sublista es 2446 y el elemento buscado es 1983 menos que 2446; eliminamos la segunda sublista y nos queda

1983

2005

Como no hay término central elegimos el término inmediatamente anterior al término central, 1983, que es el buscado.

Se han necesitado tres comparaciones, mientras que la búsqueda secuencial hubiese necesitado siete.



por ultimo de el primer video de un lista de reproduccion de videos de exposiciones acerca de lo arboles binarios

Bibliografia:

http://www.youtube.com/watch?v=Rr1t8UX_d10

http://www.elrincondelc.com/nuevorincon/index.php?pag=codigos&id=4

http://html.rincondelvago.com/algoritmos-de-busqueda.html