Algoritmos de Busqueda Binaria Optima

BÚSQUEDA EN ÁRBOLES
Introducción
En programación es muy común usar Estructuras de Datos para poder ordenar y almacenar información. Ésta puede ser desde primitivas como números enteros hasta cadenas de texto hasta tipos definidos por el programador como productos, personas o estados de un juego.
Existen diversas Estructuras de Datos entre las cuales están los arrays, las listas, las colas,las pilas, los conjuntos, los árboles, los grafos, y este estudio se centrara en aquellas estructuras de datos necesarias para la búsqueda en anchura, la búsqueda en profundidad.
Marco Teórico
Un árbol es una estructura de datos compuesta por nodos y ramas. Un nodo es un elemento, el dato que queremos organizar. Una rama es una unión dirigida entre un par de nodos. Un nodo se dice que es padre siexiste alguna rama que le una con otro nodo, del mismo modo que un nodo es hijo si existe una rama que una a otro nodo con éste. Decimos que un nodo es hoja si no tiene hijos. Un grafo es una generalización de un árbol. Para entenderlo mejor, se consultara la siguiente figura:


Como toda estructura de datos, los árboles tienen tres operaciones básicas:
Inserción de nuevos elementos.Eliminación de elementos existentes.
Búsqueda de un elemento en la estructura.
Se partirá desde el siguiente árbol:



Búsqueda Primero En Anchura
La búsqueda en anchura, llamada Breadth First Search en inglés, es un algoritmo usado para recorrer o buscar elementos en una estructura de datos como los árboles y los grafos. Pertenece al grupo de las búsquedas no informadas. Su procedimiento consisteen ir visitando todos los nodos de un nivel antes de proceder con el siguiente nivel tal y como se muestra en la siguiente figura (los números en naranja indican el orden de exploración de los nodos):


De modo que lo primero que hará será visitar la raíz, luego los hijos de la raíz, luego los hijos de cada uno de estos hijos y así sucesivamente, usando una cola como estructura de datosauxiliar.
Una cola es una estructura FIFO (First In, First Out) en la que solo se dispone de dos operaciones: insertar al final de la cola y extraer del principio de la cola. Por tanto, el elemento que entra el último será el último en salir.
Implementación
Se inserta la raíz en la cola, como preparación.
Si la cola no está vacía, se saca el primer elemento (el primer nodo que haya en la cola) ycomprobamos si es el elemento que estamos buscando. Si es igual entonces acabamos, si no es igual obtenemos todos los hijos de dicho nodo y los insertamos en la cola (recordando que las inserciones son desde el final).
Repetimos hasta que hayamos encontrado el elemento o la cola sea vacía.
Algoritmo
//Se ingresa a Q como la cola.
PEA(grafo G, nodo_fuente s)
{ // recorremos todos los vérticesdel grafo inicializándolos a NO_VISITADO,
// distancia INFINITA y padre de cada nodo NULL
for u ∈ V[G] do
{
estado[u] = NO_VISITADO;
distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
padre[u] = NULL;
}
estado[s] = VISITADO;
distancia[s] = 0;
padre[s] = NULL;
CrearCola(Q); /* nos aseguramos quela cola está vacía */
Encolar(Q, s);
while !vacia(Q) do
{
// extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
u = extraer(Q);
for v ∈ adyacencia[u] do
{
if estado[v] == NO_VISITADO then
{
estado[v] = VISITADO;
distancia[v] = distancia[u] + 1;padre[v] = u;
Encolar(Q, v);
}
}
}
}
Búsqueda Primero En Profundidad

La busqueda en profundidad, llamada Depth First Search en inglés, es un algoritmo usado para recorrer o buscar elementos en un árbol o un grafo y pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en visitar todos los nodos de forma...