UNIVERSIDAD DE PANAMÁ
FACULTAD DE INFORMÁTICA ELECTRÓNICA Y COMUNICACIÓN

BUSQUEDA DE ÁRBOLES BINARIO
PROYECTO # 1
II SEMESTRE

PRESENTADO A:
PROF. DONNA ROPER


PREPARADO POR:
GIL, YAREMIS 8-783-1762
PEREZ, LUIS 8-795-1687

FECHA DE ENTREGA:
11 DE NOVIEMBRE 2008



INTRODUCCIÓN


En el siguiente proyecto estaremos hablando que son la búsqueda de árboles binarios su definición y su formación desde que empiezan hasta donde terminan, conociendo sus nodos, el grado de un árbol, la determinación de su altura. Teniendo en cuenta que todo árbol empieza desde la raíz y desde allí la formación de sus hojas, sus características más cocidas, su búsqueda así como el recorrido del un árbol binario en sus tres formas que son: inorden, preorden y posorden.
También les presentamos como insertar un árbol binario, el procedimiento adecuado de borrado de un árbol, su definición y ejemplo aplicado en lenguaje c++.















CONCEPTO DE ÁRBOLES BINARIOS

Un árbol es una estructura jerárquica no lineal en la que cada nodo puede apuntar a uno o varios nodos. Compuesta por un dato y varios árboles.
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)
A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
Árbol binario


CARACTERÍSTICAS DE ÁRBOLES BINARIOS

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Se añade un puntero: a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas.
Nodo raíz: es donde se parte el desarrollo de un árbol.
Peso: Es el número de nodos del árbol sin contar la raíz.
· Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.
· Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
· Nodo anterior: Es un nodo que no es raíz ni terminal.
Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
· Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
RECORRIDO DE LOS ÁRBOLES BINARIOS:
El recorrido en un árbol binario permite rescatar los datos en formas diferentes. Aunque existen varias maneras de hacerlo, aquí se verán las más conocidas: inorden, preorden, postorden.
Una de los recorridos más usados (inorden) es el que rescata los datos en forma ordenada (de menor a mayor).
La técnica que usualmente se usa para hacer el recorrido, es ir almacenando los datos en una estructura lineal: Cola, Lista o Pila.
Ø inorden: recorrer en inorden el subárbol izquierdo, visitar el elemento de la raíz y luego recorrer en inorden el subárbol derecho.
Ø preorden: visitar el elemento de la raíz, recorrer en preorden el subárbol izquierdo y luego recorrer en preorden el subárbol derecho.
Ø postorden: recorrer en postorden el subárbol izquierdo, luego recorrer en postorden el subárbol derecho y finalmente visitar el elemento de la raíz.

Como Buscar árboles:
La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.
Como Borra árboles:
Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.
Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.
Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos
Como insertar árboles:
La inserción es similar a la búsqueda, por tanto también es posible una versión iterativa con los mismos resultados que una recursiva. Se procede de la siguiente forma, si el árbol pasado como parámetro está vacío se crea un nuevo nodo para él cuyo contenido correspondiente sería el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que el de la raíz del árbol con lo que se inserta en el subárbol izquierdo, o mayor, insertándose en el subárbol derecho. Se observa que de este modo las inserciones se realizan en las hojas, es la forma más simple de llevar a cabo esta tarea, aunque no la única. Además, permite mantener la estructura (forma) del árbol anterior a la inserción.






EJEMPLO APLICADO



1. Búsqueda de arboles:
Ejemplo de versión iterativa en el lenguaje de programación C, suponiendo que estamos buscando una clave alojada en un nodo donde está el correspondiente "dato" que precisamos encontrar:data Buscar_ABB(abb t,clave k) { abb p; dato e; e=NULL; p=t; if (!estaVacio(p)) { while (!estaVacio(p) && (p->k!=k) ) { if (k <>k) { p=p->l; } if (p->k < p="p-">r; } } if (!estaVacio(p) &&(p->d!=NULL) ) { e=copiaDato(p->d); } } return e;}
2. Para insertar árboles: void insertar(tArbol **a, int elem){ if (*a == NULL) { *a = (tArbol *) malloc(sizeof(tArbol)); (*a)->clave = elem; (*a)->hIzquierdo = NULL; (*a)->hDerecho = NULL; } else if ((*a)->clave <>hDerecho, elem); else if ((*a)->clave > elem) insertar(&(*a)->hIzquierdo, elem);}

Para borrar árboles:
void borrar(tArbol **a, int elem){ void reemplazar(tArbol **a, tArbol **aux); tArbol *aux; if (*a == NULL) return; if ((*a)->clave <>hDerecho, elem); else if ((*a)->clave > elem) borrar(&(*a)->hIzquierdo, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->hIzquierdo == NULL) *a = (*a)->hDerecho; else if ((*a)->hDerecho == NULL) *a = (*a)->hIzquierdo; else reemplazar(&(*a)->hIzquierdo, &aux); free(aux); }} void reemplazar(tArbol **a, tArbol **aux){ if ((*a)->hDerecho == NULL) { (*aux)->clave = (*a)->clave; *aux = *a; *a = (*a)->hIzquierdo; } else reemplazar(&(*a)->hDerecho, aux);}




Recorido de árboles:

#include
#include

/* declaración de tipos */

typedef int TipoC;
typedef int TipoA;

/* archivos necesarios */

#include "tadCola.h"
#include "tadArbin.h"
#include "funcArbin.h"

/* función específica de comparación que
será pasada como parámetro a la función
insertarArbin */

int mayor(int a , int b)
{
return a > b;
}

int main()
{

Arbin a = arbinVacio();
Cola c = inicCola();

int arr[] = { 60, 30 , 80, 10 , 50 , 55 };

/* Se insertan los datos en el árbol*/

for(int i = 0; i < a =" insertarArbin(a,arr[i],mayor);" aux =" infoCola(c);" raiz =" raizArbin(a);" raiz =" raizArbin(a);" raiz =" raizArbin(a);">izq);
destruirArbin(a->der);
free(a);
}
}









































CONCLUSIÓN





En este proyecto podemos concluir que en la búsqueda de un árbol binario se debe llevar un orden empezando desde la raíz.
Se debe tener en cuenta y tener presente las partes en que están formados los árboles binarios sus nodos, hojas u hijos.
Al igual que los demás problemas en c++ un árbol tiene igual semejanza.
Concluimos también que para poder resolver un árbol binario se identificar primeros sus partes y que se quiere realizar, ya sea, una búsqueda, una inserción, o un borrado, etc.

tecnicas de busqueda por interpolación

Pertenece a:

• Christian Ruiz
• Melissa Garcia

Técnica de Búsqueda por Interpolación.

Descripción de la técnica:

Este método se puede aplicar solamente a tablas o archivos ordenados. Como su nombre lo indica se trata de llegar al elemento buscado por medio de la interpolación lineal.
El procedimiento es recursivo; como en el caso de la búsqueda binaria, en cada paso se van modificando los límites, disminuyendo el intervalo, hasta llegar al elemento buscado.

Si se determina que la clave buscada XX se encuentra dentro del intervalo INTABLA de la tabla, y que la variación en ese intervalo de la clave es INCLAVE, la siguiente posición a probar es:

PX = PI + ENTERO ((XX-XI) * (INTABLA / INCLAVE))

El algoritmo es similar al de búsqueda binaria, la diferencia está en que en vez de dividir el área en mitades, se delimita por medio de los valores resultantes de la interpolación.

En búsqueda binaria el espacio se corta siempre adentro a medias, las garantías de lo que desea el funcionamiento logarítmico.
Sin embargo, durante la búsqueda encontramos un valor que esté muy cerca del número z de la búsqueda, parece más razonable continuar la búsqueda en esa Área en vez de ocultar e ir a la media punta siguiente.
En detalle, si z es muy pequeño, debemos comenzar la búsqueda en alguna parte en el principio de la secuencia en vez de la punta intermedia Considere la manera que abrimos un libro cuando estamos buscando para cierta página. Diga que la página es 200 y el libro parece de 800 paginas.

La paginación 200 es así alrededor de la marca de un cuarto, y nosotros utilizamos este conocimiento como indicación de donde abrir el libro.
No golpearemos probablemente la paginación 200 en el primer intento; suponga que conseguimos la paginación 250 en lugar de otro.
Ahora cortamos la búsqueda a un rango de 250 paginas, y la paginación deseada está en alrededor la marca de 80 por ciento entre la paginación 1 y 250.
Ahora intentamos ir detrás de un quinto de la manera corta. Podemos continuar este proceso hasta que conseguimos bastante cercanos a la paginación 200, de que podemos mover de un tirón una pagina al mismo tiempo.

Ésta es exactamente la idea detrás de la búsqueda de la interpolación. En vez de cortar el espacio de la búsqueda por una mitad fija, la cortamos por una cantidad que se parezca la más probable tener éxito.
El funcionamiento de la búsqueda de la interpolación depende no solamente de la talla de la secuencia, pero también de la entrada de información misma. Hay entradas de información para los chequeos de la búsqueda de interpolación del deseado en cada número en la secuencia. Sin embargo, la búsqueda de la interpolación es muy eficiente para las entradas de información que consisten en elementos relativamente uniformemente distribuidos (las paginaciones de un libro, por supuesto, se distribuyen uniformemente).

Puede ser mostrado que el número medio de comparaciones se realizó por la búsqueda de interpolación, donde el promedio asume el control todas las secuencias posibles, es 0 (logn del registro). Aunque éste se parece ser un orden de la mejora magnitud concluída de el funcionamiento de la búsqueda binaria ( debido al logaritmo adicional).

Ventajas de la técnica.

La búsqueda de interpolación, es una búsqueda mucho mejor que la binaria en la práctica porque, a menos que no sea muy grande, el valor de log2n es bastante pequeño que el logaritmo de él no es mucho más pequeño.
Incluso a pesar de qe el calclo es de algun modo mas complejo, una busqueda con interpolacion puede proporcionar una mejoria importante a nuestra busqueda binaria en grandes conjuntos de datos con claves distribuidas de modo uniforme.

Desventajas de la técnica.

• La búsqueda de la interpolación requiere una aritmética más elaborada, a parte que los calculos que se necesitan para esta busqueda son muy lentos.
• Para lograr esta busqueda se requieren llaves, multiplicaciones y divisiones complejas, es decir, calculos de nivel alto.

Principales Aplicaciones.

En aplicaciones matematicas donde se busquen aproximaciones de alguna ecuacion, se utiliza este metodo pero sin su recursividad solo hace su primera para conseguir las aprox.
Tambien tiene las mismas aplicaciones que la busqueda binaria ya que son casi iguales.

Codificación.

#define MEDIO (x) ( ((x) + 1)/2 )
#define NO_ ENCONTRAD

int bus_bin (int datos [], int tamaño, int clave)

{
int delta,mitad;
delta =tamaño / 2;
while (clave := datos[mitad] ) {
if (delta ==0)
return (NO_ENCONTRADO);
else if(clave>datos[mitad]);
mitad + = medio (delta);
else
mitad -= MEDIO (delta);
delta=delta/2;
}
return (mitad);
}

METODOS DE ORDENAMIENTO Y BUSQUEDA

LOS METODOS DE ORDENAMIENTO Y BUSQUEDA

En la administración de arreglos unidimensionales y bidimensionales existen algunos procesos que son tradicionales para los programadores, ya que no escapan de actividades que son típica de las aplicaciones en los distintos lenguajes. Es por eso que estos métodos son independiente del lenguaje de programación utilizado.

Muchos de los estudiantes les parece difícil el trabajo con los arreglos, es una cuestión de visión y de imaginación.

En este blog vamos a hacer un compendio de las investigaciones realizadas por los estudiantes, presentando la parte conceptual y una aplicación fundamentada en las experiencias de cada uno de los estudiantes.