Recorrido y busqueda en arboles

1. INTRODUCCION

Los arboles corresponden a una de las subclases de grafos de uso mas amplio, particularmente en computacion. Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos. Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente. Por ejemplo, un arbol de definicion jerarquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.

En esta monografia se introducira los siguientes temas: recorrido en arboles , busqueda en arboles : su definicion , diferentes modos de recorrido y busqueda .Estos temas forman parte del programa de la asignatura Matematica Discreta, correspondiente al 3o an˜ o de la carrera Ingenieria de Sistemas.

2. ARBOLES

2.1. Conceptos previos:

Segun el libro Matematicas discretas de Elias Micha en la pagina 80 nos dice:

[1] Un arbol es un grafo conexo que no contiene circuitos. en la actualidad los arboles son las estructuras mas utiles de las matematicas discretas y constituyen una herramienta invaluable

… ya que muchas de las clasificaciones y busquedas que realizan las computadoras pueden ser modeladas .

Segun el libro Estructura de datos de T. Parajan nos dice:

[2] Una grafica conectada sin ningun circuito recibe el nombre de arbol , el define dos tipos de arboles : Arboles raiz y Arboles binarios.

Segun el libro Matematicas Discretas Richard JOHNSONBAUGH en la pagina 377 nos dice:

[4] Un arbol (libre) T , es una grafica simple que satisface : si V y W son vertices en T , entonces existe un unico camino simple de V a W.Un arbol con raiz es un arbol en el cual un vertice particular se designa como la raiz.

En la imagen se ilustra un arbol simple

3. ARBOLES BINARIOS

3.1. Concepto:

Segun el libro Estructura de datos de T. Parajan nos dice:

[2] Si todo vertice interno de todo arbol raiz tiene exactamente a lo mas 2 hijos , el arbol se denomina arbol binario completo o arbol binario.

Existen cuatro tipos de arbol binario:

3.1.1. A. B. Distinto:

Estructuras diferentes.

3.1.2. A. B. Similares:

Estructuras identicas, pero la informacion en sus nodos es diferente.

3.1.3. A. B. Equivalentes:

Son similares cuyos nodos contienen la misma informacion.

3.1.4. A. B. Completos:

Son aquellos en el que todos sus nodos tienen dos hijos , excepto los del ultimo nivel.

En la imagen se ilustra un arbol binario

4. Caracteristicas de los arboles:

En el libro de Elias Micha pag 84 nos dice que[1]

1.- En cualquier arbol dos vertices estan unidos por una unica trayectoria

2.- Todas las aristas no tiene direccion.

3.-Un arbol con n vertices tiene exactamente n-1 aristas.

4.-Cualquier grafica sin circuitos con n vertices y (n-1) aristas es un arbol.

5. Recorrido en Arboles

Segun el libro de T. Parajan nos dice que:

[2]El recorrido de un arbol es el proceso para recorrer (desplazarse a lo largo) un arbol de ma- nera sistematica a fin de que cada vertice se visite y procese exactamente una vez .Hay tres metodos para recorrer un arbol binario a saber recorridos de preorden , de inorden y de posorden.

Segun el libro de JOHNSONBAUGH Richard pag. 415 nos dice que :

[4]La busqueda a lo ancho y la busqueda a profundidad proporcionan formas de recorrer un arbol , es decir de recorrerlo de manera sistematica de modo que cada vertice sea visitado exactamente una vez.

5.1. Recorrido preorden :

Para recorrer un arbol binario no vacio en preorden, hay que realizar las siguientes opera- ciones recursivamente en cada nodo, comenzando con el nodo de raiz:

1.Visite la raiz

2.Atraviese el sub-arbol izquierdo

3.Atraviese el sub-arbol derecho

Preorden: ABDGEHICFJK

5.2. Recorrido inorden :

Para recorrer un arbol binario no vacio en inorden (simetrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.Atraviese el sub-arbol izquierdo

2.Visite la raiz

3.Atraviese el sub-arbol derecho

Inorden: GDBHEIACJKF

5.3. Recorrido posorden :

Para recorrer un arbol binario no vacio en postorden, hay que realizar las siguientes opera- ciones recursivamente en cada nodo:

1.Atraviese el sub-arbol izquierdo

2.Atraviese el sub-arbol derecho

3.Visite la raiz

Postorden: GDHIEBKJFCA

6. Busqueda en Arboles

Esto implica examinar cada parte del arbol hasta que el vertice o la arista deseada sea encon- trada.Podriamos profundizar moviendonos a un vertice siempre que sea posible o podriamos des plegarnos comprobando todos los vertices en un nivel antes de pasar al siguiente.

6.1. Busqueda en profundidad:

La idea basica de la busqueda en profundidad es penetrar tan profundamente como sea po- sible antes de desplegarse a otros vertices .Esto se consigue al tomar el nuevo vertice adyacente al ultimo de los posibles vertices anteriores.

6.2. Busqueda en anchura:

La idea basica de la busqueda en anchura es desplegarse a tantos vertices como sea posible antes de penetrar en profundidad dentro de un arbol.Esto significa que visitaremos todos los vertices adyacentes a uno dado antes de cambiar de nivel.

Referencias

[1] MICHA Elias (1890), Matematicas Discretas (Segunda edicion). Mexico

[2] T. Parajan (2005) Matematicas Discretas. USA

[3] ESPINOZA ARMENTA, Ramon (2010) Matematicas Discretas.Mexico

[4] JOHNSONBAUGH , Richard (2005) Matematicas Discretas (Cuarta Edicion). Mexico

AGRADECIMIENTO

Primero y antes que nada, dar gracias a Dios, por estar conmigo en cada paso que doy, por fortalecer mi corazon e iluminar mi mente y por haber puesto en mi camino a aquellas personas que han sido mi soporte y compan˜ia durante todo el periodo de estudio. Agradecer hoy y siempre a mi familia por el esfuerzo realizado por ellos. El apoyo en mis estudios, de ser asi no hubiese sido posible. A mis padres y demas familiares ya que me brindan el apoyo, la alegria y me dan la fortaleza necesaria para seguir adelante.

Un agradecimiento especial al Ingeniero Elmer Coyla Idme, por la colaboracion, paciencia y apoyo incondicional q me brinda dia a dia.

DEDICATORIA

La concepcion de este proyecto estadedicada a mis padres, pilares fundamentales en mi vida.

Sin ellos, jamas hubiese podido conseguir lo que hasta ahora logre. Su tenacidad y lucha insaciable han hecho de ellos el gran ejemplo a seguir y destacar, no solo para mi, sino para mis hermanos y familia en general.

A ellos este proyecto, que sin ellos, no hubiese podido ser.

Autor:

Lizbeth Llanos Tintaya

Puno – Peru

2013

UNIVERSIDAD NACIONAL DEL ALTIPLANO

FACULTAD DE INGENIERA MECANICA ELECTRICA, ELECTRONICA Y SISTEMAS ESCUELA PROFESIONAL DE INGENIERIA DE SISTEMAS