Fecha y hora actual: Miércoles 16 Abr 2014 19:56
Índice del Foro

Foros de programación informática, diseño gráfico y Web

En esta comunidad intentaremos dar soporte de programación a todos los niveles, desde principiantes a profesionales de la informática, desarrollo de programas, programación web y mucho más.

Lección 54: Árboles - Introducción a Árboles Binarios

Responder al Tema

Índice del Foro > Programación en general > Lección 54: Árboles - Introducción a Árboles Binarios

Autor Mensaje
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 894

Mensaje Publicado: Miércoles 11 Abr 2012 17:59

Título del mensaje: Lección 54: Árboles - Introducción a Árboles Binarios

Responder citando

Árboles:

Introducción:

Desde los inicios del curso cuando comenzamos con Pascal hasta ahora hemos visto muchísimas cosas y ustedes mismos podrán darse cuenta de cuánto pueden hacer hoy día que antes les era impensable, claro está, si han trabajado duro y han hecho los ejercicios y proyectos que les he ido proponiendo. Han aprendido a programar de forma estructurada a un muy buen nivel ya que manejan las estructuras básicas que tiene cualquier lenguaje moderno:

  • Manejo de tipos primitivos de un lenguaje dado, así como de variables de esos tipos, constantes y su uso en sentencias de asignaciones y comparaciones.
  • Condiciones booleanas simples y compuestas mediante los operadores AND, OR y NOT.
  • Selección simple y doble mediante estructuras IF...THEN e IF...THEN...ELSE.
  • Selección múltiple mediante anidación de las sentencias anteriores.
  • Selección múltiple mediante la estructura CASE...ELSE.
  • Secuencias de repetición, tanto predefinida con FOR como condicionales con WHILE y REPEAT, con su consecuente manejo de conceptos como repetición por centinela y por contador.
  • Modularización del código mediante la definición de subprogramas: Procedimientos y Funciones; con el consecuente manejo de pasaje de parámetros y sus implicaciones.
  • Manejo de estructuras complejas como son los arreglos, las listas encadenadas y los registros.
  • Manejo de memoria dinámica con punteros.


Existe un teorema llamado Teorema de la Programación Estructurada o Teorema del Programa Estructurado, propuesto por Corrado Böhm y Giuseppe Jacopini que demuestra que todo programa de computadora puede ser escrito usando solo tres estructuras lógicas:

  • Secuencia: Escribir instrucciones una tras otra, tal como lo hacemos nosotros.
  • Selección: Tomar distintos caminos según una condición.
  • Iteración: Repetición iterativa mediante FOR, WHILE y REPEAT.


Como ven, en ese teorema no se nombra la recursividad, que es un tipo de repetición, ni nada extraño. De este modo teóricamente ustedes estarían capacitados para escribir cualquier sistema computacional que se les planteara ya que conocen a fondo las tres estructuras nombradas más arriba. Sin embargo, a pesar de que lo que demuestra el teorema es cierto, dado un sistema complejo como el sistema Base de Productos que haremos juntos o los otros dos que les propondré, programarlo usando únicamente esas estructuras es una masacre, inhumano, incluso si nos ayudamos con arreglos, listas encadenadas y todo lo que conocemos. Resultaría un código muy complicado, extenso, difícil de mantener, propenso a miles de errores, difícil de depurar, etc., etc.

Es entonces que, agregando más herramientas a las tres mencionadas por el teorema, se comienza a facilitar la creación de sistemas complejos. De este modo la recursividad nos ayudará a resolver cosas que de otro modo serían muy difíciles de atacar, la programación modular nos ayuda a crear códigos más claros y mantenibles así como reutilizables, la programación orientada a objetos nos ayudará a diseñar sistemas complejos de un modo más intuitivo y fácil así como a crear códigos claros y fácilmente mantenibles. Todo esto, acompañado de estructuras complejas, diseñadas de manera inteligente, han hecho que programar y diseñar sistemas sea algo mucho más sencillo e interesante de lo que podría ser.

Día a día se va mejorando en este aspecto con el lanzamiento de nuevos paradigmas de programación, nuevas herramientas, nuevos lenguajes y demás. Es así, que hace tiempo atrás crear una ventana con tres botones era algo super complicado, que llevaba muchas líneas de código, y hoy día podemos hacerlo en una sola línea con lenguajes como Java o C#.
Todas las estructuras que nosotros conocemos hasta ahora son lineales:

  • Arreglos.
  • Listas encadenadas simples.
  • Listas encadenadas dobles.
  • Listas encadenadas circulares: simples y dobles.
  • Listas encadenadas indexadas: Implícita y Explícitametne.


Veremos entonces una estructura no lineal que nos ayudará a resolver problemas complejos que no podríamos atacar con ningún tipo de lista, al menos no usando las listas por sí solas: Árboles. Luego veremos otras estructuras lineales que ya he nombrado: Pilas y Colas, ya que ellas también ayudan a resolver ciertos problemas.

El uso sencillo de los Árboles se hace posible gracias a la recursión, sin embargo sería posible atacarlos mediante el uso de una Pila como estructura de ayuda, o incluso otras. Seguramente veremos ambas maneras.
===============================================

Ejemplos de Árboles:

¿Tienen idea de lo qué es un árbol o estructura arborescente? Piensen un poco en el típico dibujo de un árbol de directorios, tal como el que tenemos aquí:



Tenemos un directorio raíz, en este caso C:\, y luego a partir de él otros tantos directorios. Cada directorio puede tener otros directorios dentro o bien, archivos. Aquí no se muestran los archivos que estos directorios contienen, pero los hay.

¿Cómo podrían modelar eso con las estructuras que conocen? O mejor dicho ¿pueden modelar eso con las estructuras que conocen? Seguramente se podría, pero sería super complicado. Además, hay que tener en cuenta que para un árbol de directorios se espera además eficiencia, lo cual complica más aún las cosas.
Los invito primero a ver ese dibujo pero de otro modo:



Allí no se ven los archivos que pueden contener los directorios para simplificar el dibujo. Siempre un árbol tiene entonces una raíz. A diferencia de lo que pasa con un árbol real de la naturaleza donde la raíz está debajo, en las estructuras arborescentes en programación la raíz está en la punta, es decir, arriba del todo. Digamos que un árbol entonces nace desde arriba y crece hacia abajo.

En el primer dibujo nuestro árbol nace en el directorio C:\ también conocido normalmente como directorio raíz justamente porque es la raíz del árbol. Luego, cada nodo del árbol puede tener cero o más nodos, lo cual conforma las ramas. En nuestro primer ejemplo, el directorio raíz C tiene seis nodos: ArchivosModula, Docs, Grupos, JavaProyects, Mis imágenes y Modula.

Cuando un nodo no tiene más nodos hacia abajo, es decir, la rama llegó al final, decimos que ese nodo es una hoja del árbol porque ya no hay más nada por recorrer. De este modo los directorios ArchivosModula, Docs, Planilla, services, busyicons, Nuevas, DEF, OBJ, SRC y SYM son hojas de mi árbol. Todas las ramas de un árbol comienzan en su raíz y terminan en una de sus hojas, de este modo hay tantas ramas como hojas, más allá de que podría no querer recorrer una rama hasta el final. De este modo, las ramas completas de mi árbol serían estas:

  • C:\ArvhivosModula
  • C:\Docs
  • C:\Grupos\Planilla
  • C:\JavaProyects\DesktopAplication2\src\META-INF\services
  • C:\JavaProyects\DesktopAplication2\src\desktop\resources\busyicons
  • C:\Mis Imágenes\Nuevas
  • C:\Moula\Aplicacion\DEF
  • C:\Moula\Aplicacion\OBJ
  • C:\Moula\Aplicacion\SRC
  • C:\Moula\Aplicacion\SYM


Como ya dije, podríamos recorrer una rama hasta un punto intermedio, por ejemplo: C:\JavaProyects\DesktopAplication. No siempre se recorre una rama hasta alguna de sus hojas.

Dado un nodo, decimos que los nodos inmediatos inferiores son hijos y el nodo inmediato superior es el padre. De este modo si miramos el directorio Aplicacion decimos que el directotrio Modula es su padre y que DEF, OBJ, SRC y SYM son sus hijos.

Algo que cabe destacar, y que comienza a dar un énfasis recursivo al tema de árboles, es que dado un nodo podemos verlo como un árbol, de este modo podemos decir que todos los hijos de un nodo son subárboles de él. Entonces en realidad podemos ver a cada nodo como raíz de un árbol. Veamos esto con un ejemplo:



El árbol tiene como raíz al directorio 1. Decimos esto porque dicho nodo no tiene padre. Ahora bien, sus hijos son los nodos 2 y 3. Sin embargo, podríamos ver a dichos nodos como subárboles, es decir, como árboles más pequeños.



Tomemos el subárbol del lado izquierdo, es decir, vallamos hacia el nodo 2.



Como pueden observar tenemos un nuevo árbol pero más pequeño cuya raíz es el nodo 2. Este también podría ser dividido en dos subárboles más, los cuales tendrían como raíces los nodos 4 y 5 respectivamente. Podríamos continuar así hasta llegar a un nodo que se corresponde a una hoja del árbol ya que de ahí no tendremos más nada.

Si por ejemplo miramos el subárbol de raíz 5, vemos que tiene un único subárbol que en realidad es una hoja ya que no hay más nada. En ese ejemplo dicha hoja corresponde con un archivo ejecutable, lo cual tiene sentido, porque tomamos como árbol o subárbol a todo lo que corresponde a un directorio y por ende se puede recorrer, y como hojas a los archivos contendidos en esos directorios. Podría pasar que exista un directorio vacío, es decir, un directorio hoja, lo cual es totalmente normal en el uso cotidiano de un sistema operativo.

En este curso no veremos árboles tan complejos como lo son los árboles de directorios ya que nos enfocaremos en árboles binarios a fin de formar una base sólida en el manejo de estas estructuras.
===============================================

Árboles binarios:

Comencemos entonces a bajar de la ejemplificación a lo concreto. Los árboles que les mostré anteriormente se conocen como árboles finitarios, es decir, si no son vacíos (un árbol vacío es aquel que no tiene ningún nodo) tienen una cantidad finita de subárboles también finitarios. Dicho más claramente, cada nodo puede tener cero o más hijos ¿me siguen?.

Otra forma de árboles son los árboles n-arios. Estos, a diferencia de los anteriores, si no son vacíos, tienen a lo sumo n árboles n-arios. Por ejemplo, un árbol 3-ario, si no es vacío, tiene a lo sumo 3 subárboles 3-arios. Visto de otro modo, cada nodo puede tener entre 0 y 3 subárboles, tal como se ve en la siguiente figura:



En ese dibujo los cuadritos negros representan nodos vacíos, es decir, nodos inexistentes; bien podría no haber dibujado nada, pero quiero dejar bien clara la idea ya que luego para programar necesitaremos decir que un nodo es vacío. La raíz de ese árbol es el nodo 1, el cual tiene justamente tres subárboles: 2, 3 y 4. El subárbol de raíz 2 tiene un único subárbol, el de raíz 5, quién no tiene ningún subárbol. Del mismo modo el nodo 3 tiene tres subárboles y el nodo 4 tiene solo dos. Entonces, ¿cuáles son las hojas de ese árbol? Pues todo nodo que no tiene subárboles, es decir, los nodos 5, 11, 12, 14, 15, 17, 18 y 19.

Este tipo de estructuras resultan más amigables para el programador ya que, dado un nodo, sabemos el número máximo de hijos que puede tener y eso simplifica bastante las cosas. Sin embargo, siempre al trabajar con árboles se vuelve complicado insertar y eliminar nodos. Imaginen que quiero eliminar el nodo 9 del árbol de arriba, ¿qué hago con los nodos 15 y 16? ¿Los elimino también? Pues si fuera un árbol de directorios lo correcto sería eliminarlos ya que representarían el contenido del directorio 9 y por ende al eliminarlo se va con él todo lo que existiera dentro. Pero si no fuera así y por ejemplo ese árbol representara personas en un sistema dadas por su número ID y yo quiero dar de baja a la persona cuyo ID es 9 pero no quiero dar de baja a las personas con ID 15 y 16 ¿qué hago? Pues problemas como ese y otros muchos más se presentarán al trabajar con estructuras como esa, sin embargo y gracias a que existen personas dedicadas a su análisis, tenemos una basta gama de herramientas que resuelven muchos de los posibles problemas que podríamos tener.

Como ya dije, nosotros nos enfocaremos en árboles binarios, es decir, árboles 2-arios. Esto significa que dado un nodo, puede tener entre 0 y 2 hijos. No piensen que porque sea solamente binario la cosa será sencilla, absolutamente no lo será dado que las aplicaciones para estos arbolitos son muchas y muy complejas. Como adelanto les digo que existe una forma de representar cualquier árbol finitario con un árbol binario.

Veamos un ejemplo de aplicación concreta de un árbol binario: Dada la siguiente expresión matemática:

(10+1)*3-20+3*2

En el curso de Pascal había un ejercicio que pedía realizar una calculadora básica, la cual iba haciendo las operaciones en el orden en que aparecían. Si hacemos eso en este caso tendríamos el resultado 32, es decir, hacemos primero 10 + 1 (11), luego lo multiplicamos por 3 (33), le restamos 20 (13), le sumamos 3 (16) y multiplicamos por 2 (32). Estamos de acuerdo en que ese no es el resultado correcto sino que es 19.

Los paréntesis le dan precedencia la suma ante el producto, entonces debo evaluar 10+1 (11) y luego multiplicarlo por 3 (33). Luego puedo restarle 20 a ese valor (13) pero no puedo sumarle 3 al resultado, sino que debo hacer primero el producto 3*2 ya que dicha operación tiene precedencia ante la suma. De este modo termino haciendo 13+6 lo cual da 19.

Con las herramientas que tenemos no podemos hacer que un programa sepa diferenciar qué operación debe hacer primero y es por eso que no lo pedí en el curso de Pascal. Lo que se necesita para evaluar ese tipo de operaciones es un árbol binario armado de este modo:



Luego, al recorrer este árbol se pueden ir evaluando las distintas expresiones en el orden correcto. Ahora bien, cómo llegar a ese árbol desde la expresión inicial será algo que veremos luego, esto es un adelanto de una aplicación común para árboles binarios. Las calculadoras avanzadas utilizan justamente esta estructura para evaluar las expresiones que les escribimos.

===============================================

Hasta aquí llegamos por ahora. En la próxima lección comenzaremos a implementar árboles binarios tomando como base un tipo de árbol llamado Árbol Binario de Búsqueda.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Responder al Tema
Mostrar mensajes anteriores:   
Ir a:  
Todas las horas están en GMT + 1 Hora

Temas relacionados

Tema Autor Foros Respuestas Publicado
El foro no contiene ningún mensaje nuevo

Curso de Introducción al desarrollo de videojue...

Tesis Programación de juegos o videojuegos 2 Jueves 06 Mar 2014 20:40 Ver último mensaje
El foro no contiene ningún mensaje nuevo

CA0 001: Introducción y preparación.

Kyshuo Ayame Programación en general 0 Jueves 20 Feb 2014 20:36 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Lección 101: Lectura/Escritura de archivos de t...

Kyshuo Ayame Programación en general 3 Sábado 26 Oct 2013 02:04 Ver último mensaje
El foro no contiene ningún mensaje nuevo

ayuda con arboles

Kyshuo Ayame Programación en general 2 Lunes 07 Oct 2013 02:53 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Arboles Binarios-Recorrido por nivel- Pascal

nehuen Programación en general 1 Viernes 13 Sep 2013 00:47 Ver último mensaje
Panel de Control
No puede crear mensajes, No puede responder temas, No puede editar sus mensajes, No puede borrar sus mensajes, No puede votar en encuestas,