Arboles Binarios

INDICE

BUSQUEDA SECUENCIAL INTERNA
BÚSQUEDA BINARIA
BÚSQUEDA HASH
ORDENAMIENTO
ORDENACIÓN POR EL MÉTODO DE LA BURBUJA
ORDENAMIENTO POR EL MÉTODO DE LA SACUDIDA (SHAKER SORT)

ORDENACIÓN POR EL MÉTODO RAPIDO (QUICKSORT)



BUSQUEDA SECUENCIAL INTERNA
Es la forma mas simple de los métodos de búsqueda, inicia el principio de la lista y va buscando el registro deseado en formasecuencial hasta que lo encuentra o hasta que ha llegado al fin de la lista y entonces termina. Este método es aplicable a tablas, arreglos, listas, archivos, etc. que se encuentran en desorden.
Algoritmo

1.- Empezar con el primer elemento de la lista e inicializar la variable que servirá de bandera.
2.- Efectuar la búsqueda mientras hay elementos en la lista y el valor de la llave no se haencontrado.
3.- Verificar si se encontró el elemento objeto de la búsqueda.
4.- fin
Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementos buscados, o hasta que se han mirado todos los elementos del array.

BÚSQUEDA BINARIA
Si la tabla de números está ordenada, por ejemplo, en orden creciente, es posible utilizar para la búsqueda un algoritmomás eficiente que se basa en un concepto muy utilizado en la programación: dividir para vencer.
Si está ordenada la tabla y miramos el número situado en la mitad para ver si es mayor o menor que el número buscado (o con suerte igual), sabremos si la búsqueda ha de proceder en la subtabla con la mitad de tamaño que está antes o después de la mitad. Si se repite recursivamente el algoritmo al finalo bien encontraremos el número sobre una tabla de un sólo elemento o estaremos seguros de que no se encuentra allí.
La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
int vector[10] = {2,4,6,8,10,12,14,16,18,20};

La clave que queremos buscar es 6. El algoritmofunciona de la siguiente manera
1. Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente.
2. Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5.
3. Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos Icentro.
4. Si son distintos, evaluamos sivector[Icentro] es mayor o menor que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 5 < 6, entonces la parte del arreglo vector[0…5] ya puede descartarse.
5. Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremosbuscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos que subir hasta 6, entonces quedaría Iarriba = 10, Iabajo = 6. Y volvemos al paso 2.

BÚSQUEDA HASH
En este método se requiere que los elementos estén ordenados.
El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamadafunción hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento.
La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el 1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedancon muchos espacios libres, para utilizar mejor el espacio se utilizan funciones mas complejas.
La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar. La...