Modelo De Componentes

UNIVERSIDAD AUTONOMA DEL ESTADO DE HIDALGO |
APLICACIONES DE ARBOLES BINARIOS |
LICENCIATURA EN SISTEMA COMPUTACIONALES |
|
BUSTAMANTE ALVAREZ EMMANUEL |
08/02/2013 |

INTRODUCCION
los árboles se utilizan en distintos ámbitos. Por ejemplo, al organizar la información para facilitar la búsqueda en un disco duro, utilizamos una estructura de directorios y subdirectorios en forma deárbol. También se usan los árboles asociados a distintos esquemas para el desarrollo de los algoritmos, tales como la programación dinámica, la ramificación y poda, el esquema divide y vencerás, etc.
Si nos referimos a estructuras de datos, ya dijimos en el tema anterior que las pilas, colas y listas son estructuras lineales, puesto que en todas ellas cada elemento tiene un único elementoanterior y un único elemento posterior. Pero, además, existe estructuras de datos no lineales, en las que esta restricción desaparece. Esto es, en estas estructuras cada elemento puede tener varios anteriores y/o varios posteriores.

CONTENIDO
Una aplicación de un árbol binario esta en organizar la información para facilitar la búsqueda en un disco duro, utilizamos una estructura de directoriosy subdirectorios en forma de árbol. También se usan los árboles asociados a distintos esquemas para el desarrollo de los algoritmos, tales como la programación dinámica.
Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos unarreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.
Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene  elementos, se deben hacer comparaciones,claro, no es mucho problema si  es un número pequeño, pero el problema se va complicando más a medida que  aumenta.
Si usamos un árbol binario, el número de comparaciones se reduce bastante, veamos cómo.
El primer número del arreglo se coloca en la raíz del árbol (como en este ejemplo siempre vamos a trabajar con árboles binarios, simplemente diremos árbol, para referirnos a un árbol binario)con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio:
* Si el elemento del arreglo es igual que la información del nodo raíz, entonces notificar duplicidad.
* Si el elemento del arreglo es menor que la información del nodo raíz, entonces se crea un hijoizquierdo.
* Si el elemento del arreglo es mayor que la información del nodo raíz, entonces se crea un hijo derecho.

Una vez que ya está creado el árbol, se pueden buscar los elementos repetidos. Si x el elemento buscado, se debe recorrer el árbol del siguiente modo: Sea k la información del nodo actual p. Si  entonces cambiar el nodo actual a right(p), en caso contrario, en caso de que  informaruna ocurrencia duplicada y en caso de que x>=k cambiar el nodo actual a left(p).

El siguiente algoritmo
leer numero buscado >> n
tree=makeTree(n)
while(hay numeros en el arreglo){
leeSiguienteNumero >> k
p=q=tree;
while(k!=info(p)&&q!=NULL){p=q
if(k<info(p))
q=left(p)
else
q=right(p)
}
if(k==info(p))
despliega<<" el numero es duplicado";
else
if (k<info(p))
setLeft(p,k)
else...